IMO 1990 SL 23

Origin: ROM

Problem

Find all positive integers n having the property that 2n+1 n2 is an integer.

Solution

Let us assume n > 1. Obviously n is odd. Let p \geq3 be the smallest prime divisor of n. In this case (p −1, n) = 1. Since 2n + 1 | 22n −1, we have that p | 22n −1. Thus it follows from Fermat’s little theorem and elementary number theory that p | (22n −1, 2p−1 −1) = 2(2n,p−1) −1. Since (2n, p −1) \leq2, it follows that p | 3 and hence p = 3. Let us assume now that n is of the form n = 3kd, where 2, 3 ∤d. We first prove that k = 1. Lemma. If 2m −1 is divisible by 3r, then m is divisible by 3r−1. Proof. This is the lemma from (SL97-14) with p = 3, a = 22, k = m, \alpha = 1, and \beta = r. Since 32k divides n2 | 22n −1, we can apply the lemma to m = 2n and r = 2k to conclude that 32k−1 | n = 3kd. Hence k = 1. Finally, let us assume d > 1 and let q be the smallest prime factor of d. Obviously q is odd, q \geq5, and (n, q −1) \in{1, 3}. We then have q | 22n −1 and q | 2q−1 −1. Consequently, q | 2(2n,q−1) −1 = 22(n,q−1) −1, which divides 26 −1 = 63 = 32 \cdot 7, so we must have q = 7. However, in that case we obtain 7 | n | 2n + 1, which is a contradiction, since powers of two can only be congruent to 1,2 and 4 modulo 7. It thus follows that d = 1 and n = 3. Hence n > 1 ⇒n = 3. It is easily verified that n = 1 and n = 3 are indeed solutions. Hence these are the only solutions.