IMO 1999 SL N1

Origin: TWN | Category: Number Theory

Problem

Find all pairs of positive integers (x, p) such that p is a prime, x \leq2p , and xp−1 is a divisor of (p −1)x + 1.

Solution

Obviously (1, p) (where p is an arbitrary prime) and (2, 2) are solutions and the only solutions to the problem for x < 3 or p < 3. Let us now assume x, p \geq3. Since p is odd, (p−1)x+1 is odd, and hence x is odd. Let q be the largest prime divisor of x, which also must be odd. We have q | x | xp−1 | (p−1)x+1 ⇒(p−1)x \equiv−1 (mod q). Also from Fermat’s little theorem (p−1)q−1 \equiv1 (mod q). Since q−1 and x are coprime, there exist integers \alpha, \beta such that x\alpha = (q −1)\beta + 1. We also note that \alpha must be odd. We now have p −1 \equiv(p −1)(q−1)\beta+1 \equiv(p −1)x\alpha \equiv−1 (mod q) and hence q | p ⇒q = p. Since x is odd, p | x, and x \leq2p, it follows x = p for all x, p \geq3. Thus pp−1 | (p −1)x + 1 = p2 \cdot  pp−2 − p  pp−1 + \cdot \cdot \cdot −  p p −2 

• 1  . Since the expression in parenthesis is not divisible by p, it follows that pp−1|p2 and hence p \leq3. One can easily verify that (3, 3) is a valid solution. We have shown that the only solutions are (1, p), (2, 2), and (3, 3), where p is an arbitrary prime.