Let n > 6 be an integer and let a1, a2, ... , ak be all the positive integers less than n and relatively prime to n. If a2 - a1 = a3 - a2 = ... = ak - ak-1 > 0, prove that n must be either a prime number or a power of 2.
Solution
by anon
If n is odd, then 1 and 2 are prime to n, so all integers < n are prime to n, and hence is prime.
If n = 4k, then 2k-1 and 2k+1 are prime to n, so all odd integers < n are prime to n, and hence n must be a power of 2.
If n = 4k+2, then 2k+1 divides n, but 2k+3 and 2k+5 are prime to n. But if n > 6, then 2k+5 < n, so this cannot be a solution.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
7 Sep 1999