IMO 2000 SL N4

Origin: BRA | Category: Number Theory

Problem

Determine all triples of positive integers (a, m, n) such that am + 1 divides (a + 1)n.

Solution

Trivially all triples (a, 1, n) and (1, m, n) are solutions. Assume now that a > 1 and m > 1. If m is even, then am + 1 \equiv(−1)m + 1 \equiv2 (mod a + 1), which implies that am + 1 = 2t. In particular, a is odd. But this is impossible, since 2 < am + 1 = (am/2)2 + 1 \equiv2 (mod 4). Hence m is odd. Let p be an arbitrary prime divisor of m and m = pm1. Then am + 1 | (a + 1)n | (am1 + 1)n, so bp + 1 | (b + 1)n for b = am1. It follows that P = bp + 1 b + 1 = bp−1 −bp−2 + \cdot \cdot \cdot + 1 | (b + 1)n. Since P \equivp (mod b + 1), we deduce that P has no prime divisors other than p; hence P is a power of p and p | b+1. Let b = kp−1, k \inN. Then by

the binomial formula we have bi = (kp−1)i \equiv(−1)i+1(ikp−1) (mod p2), and therefore P \equiv−kp((p −1) + (p −2) + \cdot \cdot \cdot + 1) + p \equivp (mod p2). We conclude that P \leqp. But we also have P \geqbp−1 −bp−2 \geqbp−2 > p for p > 3, so we must have P = p = 3 and b = 2. Since b = am1, we obtain a = 2 and m = 3. The triple (2, 3, n) is indeed a solution if n \geq2. Hence the set of solutions is {(a, 1, n), (1, m, n) | a, m, n \inN} \cup{(2, 3, n) | n \geq2}. Remark. This problem is very similar to (SL97-14).