IMO 1971 SL 10

Origin: POL

Problem

Prove that the sequence 2n −3 (n > 1) contains a subse- quence of numbers relatively prime in pairs.

Solution

We use induction. Suppose that every two of the numbers a1 = 2n1 − 3, a2 = 2n2 −3, . . . , ak = 2nk −3, where 2 = n1 < n2 < \cdot \cdot \cdot < nk, are coprime. Then one can construct ak+1 = 2nk+1 −3 in the following way:

Set s = a1a2 . . . ak. Among the numbers 20, 21, . . . , 2s, two give the same residue upon division by s, say s | 2\alpha −2\beta. Since s is odd, it can be assumed w.l.o.g. that \beta = 0 (this is actually a direct consequence of Euler’s theorem). Let 2\alpha −1 = qs, q \inN. Since 2\alpha+2 −3 = 4qs + 1 is then coprime to s, it is enough to take nk+1 = \alpha+2. We obviously have nk+1 > nk.