IMO 1998 SL 18

Origin: BUL

Problem

Determine all positive integers n for which there exists an integer m such that 2n −1 is a divisor of m2 + 9.

Solution

We claim that, if 2n −1 divides m2 + 9 for some m \inN, then n must be a power of 2. Suppose otherwise that n has an odd divisor d > 1. Then 2d −1 | 2n −1 is also a divisor of m2 + 9 = m2 + 32. However, 2d −1 has some prime divisor p of the form 4k −1, and by a well-known fact, p divides both m and 3. Hence p = 3 divides 2d −1, which is impossible, because for d odd, 2d \equiv2 (mod 3). Hence n = 2r for some r \inN. Now let n = 2r. We prove the existence of m by induction on r. The case r = 1 is trivial. Now for any r > 1 note that 22r −1 = (22r−1 −1)(22r−1 + 1). The induction hypothesis claims that there exists an m1 such that 22r−1 −1 | m2 1 + 9. We also observe that 22r−1 + 1 | m2 2 + 9 for simple m2 = 3\cdot22r−2. By the Chinese remainder theorem, there is an m \inN that satisfies m \equivm1 (mod 22r−1 −1) and m \equivm2 (mod 22r−1 + 1). It is easy to see that this m2 + 9 will be divisible by both 22r−1 −1 and 22r−1 + 1, i.e., that 22r −1 | m2 + 9. This completes the induction.