APMO 97/2 solution

9th APMO 1997

Problem 2

Find an n in the range 100, 101, ... , 1997 such that n divides 2ⁿ + 2.

Solution

Answer: the only such number is 946.

We have 2^p-1 = 1 mod p for any prime p, so if we can find h in {1, 2, ... , p-2} for which 2^h = -2 mod p, then 2^k= -2 mod p for any h = k mod p. Thus we find that 2^k = -2 mod 5 for k = 3 mod 4, and 2^k = -2 mod 11 for k = 6 mod 10. So we might then hope that 5·11 = 3 mod 4 and = 6 mod 10. Unfortunately, it does not! But we try searching for more examples.

The simplest would be to look at pq. Suppose first that p and q are both odd, so that pq is odd. If k = h mod p-1, then we need h to be odd (otherwise pq would have to be even). So the first step is to get a list of primes p with 2^h = -2 mod p for some odd h < p. We always have 2^p-1 = 1 mod p, so we sometimes have 2^(p-1)/2 = -1 mod p and hence 2^(p+1)/2 = -2 mod p. If (p+1)/2 is to be odd then p =1 mod 4. So searching such primes we find 3 mod 5, 7 mod 13, 15 mod 29, 19 mod 37, 27 mod 53, 31 mod 61. We require pq to lie in the range 100-1997, so we check 5·29 (not = 3 mod 4), 5·37 (not = 3 mod 4), 5·53 (not = 3 mod 4), 5·61 (not = 3 mod 4), 13·29 (not = 7 mod 12), 13·37 (not = 7 mod 12), 13.53 (not = 7 mod 12), 13·61 (not = 7 mod 12), 29·37 (not = 15 mod 28), 29·53 (not = 15 mod 28), 29·61 (not = 15 mod 28), 37·53 (not = 19 mod 36). So that does not advance matters much!

2p will not work (at least with h = (p+1)/2) because we cannot have 2p = (p+1)/2 mod p-1. So we try looking at 2pq. This requires that p and q = 3 mod 4. So searching for suitable p we find 6 mod 11, 10 mod 19, 22 mod 43, 30 mod 59, 34 mod 67, 42 mod 83. So we look at 2·11·43 = 946, which works.

Proving that it is unique is harder. The easiest way is to use a computer to search (approx 5 min to write a Maple program or similar and a few seconds to run it).

9th APMO 1997