39th IMO 1998 shortlist Problem N5 Find all positive integers n for which there is an integer m such that m 2 + 9 is a multiple of 2 n - 1. Solution
: n = 2 k for k = 0, 1, 2, ... . Suppose 2 n - 1 divides m 2 + 9 and n has an odd divisor k > 1. Then 2 k - 1 divides 2 n - 1 and so 2 k - 1 divides m 2 + 9. But 2 k - 1 = 3 mod 4, so 2 k - 1 must have a prime divisor p which is 3 mod 4. But 2 k - 1 = (3 - 1) k - 1 = 1 mod 3, so 2 k - 1 cannot be divisible by 3. So p > 3. Now m 2 = -9 mod p, so 1 = m p-1 = (-9) (p-1)/2 = 3 p-1 (-1) odd = -1 mod p (using Fermat's theorem). Contradiction. So n cannot have an odd divisor and so must be a power of 2. Now suppose n is a power of 2. Put n = 2 k . Note that we can factorise 2 n - 1 as (2 2 - 1)(2 2 + 1)(2 4 + 1)(2 8 + 1) ... (2 n/2 + 1) = 3(2 2 + 1)(2 4 + 1)(2 8 + 1) ... (2 n/2 + 1). We will find c such that (2 2 + 1)(2 4 + 1)(2 8 + 1) ... (2 n/2 + 1) divides c 2 + 1. Then 2 n - 1 divides 3(c 2 + 1) and hence 9(c 2 + 1) = (3c) 2 + 9. The key is that (2 2 + 1), (2 4 + 1), (2 8 + 1), ... , (2 n/2 + 1) are all relatively prime. For suppose h divides 2 A + 1 and 2 B + 1, where A = 2 a , B = 2 b and a > b. Then 2 A = (2 B ) C , where C = 2 a-b , so 2 A = (2 B ) C = (-1) C = 1 mod h. But 2 A = -1 mod h, so 1 = -1 mod h, and hence h = 1 or 2. But 2 A + 1 is odd, so h must be odd and hence h = 1. Now by the Chinese Remainder theorem we can find c such that c = 2 mod (2 2 + 1), 2 2 mod (2 4 + 1), ... , 2 n/4 mod (2 n/2 + 1). Hence c 2 + 1 is divisible by each of 2 2 + 1, 2 4 + 1, ... , 2 n/2 + 1 and hence by their product as required. 39th IMO shortlist 1998 © John Scholes jscholes@kalva.demon.co.uk 30 Aug 2002