Determine all integers greater than 1 such that (2n + 1)/n2 is an integer.
Solution
by Gerhard Wöginger, Technical University, Graz
Answer: n = 3.
Since 2n + 1 is odd, n must also be odd. Let p be its smallest prime divisor. Let x be the smallest positive integer such that 2x = -1 (mod p), and let y be the smallest positive integer such that 2y = 1 (mod p). y certainly exists and indeed y < p, since 2p-1 = 1 (mod p). x exists since 2n = -1 (mod p). Write n = ys + r, with 0 ≤ r < y. Then - 1 = 2n = (2y)s2r = 2r (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 = 2n = (-1)h2k (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 3m 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) 32 + ... = 3n - (n - 1)/2 n 32 + ... . Evidently 3n is divisible by 3m+1, but not 3m+2. We show that the remaining terms are all divisible by 3m+2. It follows that 3m+1 is the highest power 3 dividing 2n + 1. But 2n + 1 is divisible by n2 and hence by 32m, so m must be 1.
The general term is (3ma)Cb 3b, for b ≥ 3. The binomial coefficients are integral, so the term is certainly divisible by 3m+2 for b ≥ m+2. We may write the binomial coefficient as (3ma/b) (3m - 1)/1 (3m - 2)/2 (3m - 3)/3 ... (3m - (b-1)) / (b - 1). For b not a multiple of 3, the first term has the form 3m 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 3m, since b > 3, this means that the whole term is divisible by at least 3m+3. Similarly, for b a multiple of 3, the whole term has the same maximum power of 3 dividing it as 3m 3b/b. But b is at least 3, so 3b/b is divisible by at least 9, and hence the whole term is divisible by at least 3m+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 2w = -1 (mod q), and v the smallest positive integer for which 2v = 1 (mod q). v certainly exists and < q since 2q-1 = 1 (mod q). 2n = -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 23 = -1 (mod q) and again q =3, whereas we know that q > 3.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
7 Sep 1999