Determine all integers greater than 1 such that (2^{n} + 1)/n^{2} is an integer.

**Solution**

*by Gerhard Wöginger, Technical University, Graz*

Answer: n = 3.

Since 2^{n} + 1 is odd, n must also be odd. Let p be its smallest prime divisor. Let x be the smallest positive integer such that 2^{x} = -1 (mod p), and let y be the smallest positive integer such that 2^{y} = 1 (mod p). y certainly exists and indeed y < p, since 2^{p-1} = 1 (mod p). x exists since 2^{n} = -1 (mod p). Write n = ys + r, with 0 <= r < y. Then - 1 = 2^{n} = (2^{y})^{s}2^{r} = 2^{r} (mod p), so x <= r < y (r cannot be 0, since - 1 is not 1 (mod p) ).

Now write n = hx + k, with 0 <= k < x. Then -1 = 2^{n} = (-1)^{h}2^{k} (mod p). Suppose k > 0. Then if h is odd we contradict the minimality of y, and if h is even we contradict the minimality of x. So k = 0 and x divides n. But x < p and p is the smallest prime dividing n, so x = 1. Hence 2 = -1 (mod p) and so p = 3.

Now suppose that 3^{m} is the largest power of 3 dividing n. We show that m must be 1. Expand (3 - 1)^{n} + 1 by the binomial theorem, to get (since n is odd): 1 - 1 + n.3 - 1/2 n(n - 1) 3^{2} + ... = 3n - (n - 1)/2 n 3^{2} + ... . Evidently 3n is divisible by 3^{m+1}, but not 3^{m+2}. We show that the remaining terms are all divisible by 3^{m+2}. It follows that 3^{m+1} is the highest power 3 dividing 2^{n} + 1. But 2^{n} + 1 is divisible by n^{2} and hence by 3^{2m}, so m must be 1.

The general term is (3^{m}a)Cb 3^{b}, for b >= 3. The binomial coefficients are integral, so the term is certainly divisible by 3^{m+2} for b >= m+2. We may write the binomial coefficient as (3^{m}a/b) (3^{m} - 1)/1 (3^{m} - 2)/2 (3^{m} - 3)/3 ... (3^{m} - (b-1)) / (b - 1). For b not a multiple of 3, the first term has the form 3^{m} c/d, where 3 does not divide c or d, and the remaining terms have the form c/d, where 3 does not divide c or d. So if b is not a multiple of 3, then the binomial coefficient is divisible by 3^{m}, since b > 3, this means that the whole term is divisible by at least 3^{m+3}. Similarly, for b a multiple of 3, the whole term has the same maximum power of 3 dividing it as 3^{m} 3^{b}/b. But b is at least 3, so 3^{b}/b is divisible by at least 9, and hence the whole term is divisible by at least 3^{m+2}.

We may check that n = 3 is a solution. If n > 3, let n = 3 t and let q be the smallest prime divisor of t. Let w be the smallest positive integer for which 2^{w} = -1 (mod q), and v the smallest positive integer for which 2^{v} = 1 (mod q). v certainly exists and < q since 2^{q-1} = 1 (mod q). 2^{n} = -1 (mod q), so w exists and, as before, w < v. Also as before, we conclude that w divides n. But w < q, the smallest prime divisor of n, except 3. So w = 1 or 3. These do not work, because then 2 = -1 (mod q) and so q = 3, or 2^{3} = -1 (mod q) and again q =3, whereas we know that q > 3.

The solutions given on this site are not always complete, they are designed to be sufficient for anyone who has thought hard about the problem.

(C) John Scholes

jscholes@kalva.demon.co.uk

7 Sep 1999