IMO shortlist 1998/N5 solution

39th IMO 1998 shortlist

Problem N5

Find all positive integers n for which there is an integer m such that m² + 9 is a multiple of 2ⁿ - 1.

Solution

Answer: n = 2^k for k = 0, 1, 2, ... .

Suppose 2ⁿ - 1 divides m² + 9 and n has an odd divisor k > 1. Then 2^k - 1 divides 2ⁿ - 1 and so 2^k - 1 divides m² + 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² = -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ⁿ - 1 as (2² - 1)(2² + 1)(2⁴ + 1)(2⁸ + 1) ... (2^n/2 + 1) = 3(2² + 1)(2⁴ + 1)(2⁸ + 1) ... (2^n/2 + 1). We will find c such that (2² + 1)(2⁴ + 1)(2⁸ + 1) ... (2^n/2 + 1) divides c² + 1. Then 2ⁿ - 1 divides 3(c² + 1) and hence 9(c² + 1) = (3c)² + 9.

The key is that (2² + 1), (2⁴ + 1), (2⁸ + 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² + 1), 2² mod (2⁴ + 1), ... , 2^n/4 mod (2^n/2 + 1). Hence c² + 1 is divisible by each of 2² + 1, 2⁴ + 1, ... , 2^n/2 + 1 and hence by their product as required.

39th IMO shortlist 1998