IMO 1991 SL 16

Origin: ROM

Problem

Let n > 6 and a1 < a2 < \cdot \cdot \cdot < ak be all natural numbers that are less than n and relatively prime to n. Show that if a1, a2, . . . , ak is an arithmetic progression, then n is a prime number or a natural power of two.

Solution

Let p be the least prime number that does not divide n: thus a1 = 1 and a2 = p. Since a2−a1 = a3−a2 = \cdot \cdot \cdot = r, the ai’s are 1, p, 2p−1, 3p−2, . . .. We have the following cases: p = 2. Then r = 1 and the numbers 1, 2, 3, . . ., n −1 are relatively prime to n, hence n is a prime. p = 3. Then r = 2, so every odd number less than n is relatively prime to n, from which we deduce that n has no odd divisors. Therefore n = 2k for some k \inN. p > 3. Then r = p −1 and ak+1 = a1 + k(p −1) = 1 + k(p −1). Since n −1 also must belong to the progression, we have p −1 | n −2. Let q be any prime divisor of p −1. Then also q | n −2. On the other hand, since q < p, it must divide n too, therefore q | 2, i.e. q = 2. This means that p −1 has no prime divisors other than 2 and thus p = 2l + 1 for some l \geq2. But in order for p to be prime, l must be even (because 3 | 2l + 1 for l odd). Now we recall that 2p −1 is also relatively prime to n; but 2p −1 = 2l+1 + 1 is divisible by 3, which is a contradiction because 3 | n.