IMO 1990

------
 
 
Problem 3

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.

 


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.

 

31st IMO 1990

(C) John Scholes
jscholes@kalva.demon.co.uk
7 Sep 1999