IMO 1964/A1 solution

IMO 1964

Problem A1

(a) Find all natural numbers n for which 7 divides 2ⁿ - 1.
(b) Prove that there is no natural number n for which 7 divides 2ⁿ + 1.

Solution

2³ = 1 (mod 7). Hence 2^3m = 1 (mod 7), 2^3m+1 = 2 (mod 7), and 2^3m+2 = 4 (mod 7). Hence we never have 7 dividing 2ⁿ + 1, and 7 divides 2ⁿ - 1 iff 3 divides n.

Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.