IMO 2003 SL N6

Origin: FRA | Category: Number Theory

Problem

Let p be a prime number. Prove that there exists a prime number q such that for every integer n, the number np −p is not divisible by q.

Solution

Suppose that for every prime q, there exists an n for which np \equivp (mod q). Assume that q = kp + 1. By Fermat’s theorem we deduce that pk \equiv nkp = nq−1 \equiv1 (mod q), so q | pk −1. It is known that any prime q such that q | pp−1 p−1 must satisfy q \equiv1 (mod p). Indeed, from q | pq−1 −1 it follows that q | pgcd(p,q−1) −1; but q ∤p −1 because pp−1 p−1 \equiv1 (mod p−1), so gcd(p, q−1) ̸= 1. Hence gcd(p, q−1) = p. Now suppose q is any prime divisor of pp−1 p−1 . Then q | gcd(pk −1, pp −1) = pgcd(p,k)−1, which implies that gcd(p, k) > 1, so p | k. Consequently q \equiv1 (mod p2). However, the number pp−1 p−1 = pp−1 + \cdot \cdot \cdot + p + 1 must have at least one prime divisor that is not congruent to 1 modulo p2. Thus we arrived at a contradiction. Remark. Taking q \equiv1 (mod p) is natural, because for every other q, np takes all possible residues modulo q (including p too). Indeed, if p ∤q −1, then there is an r \inN satisfying pr \equiv1 (mod q −1); hence for any a the congruence np \equiva (mod q) has the solution n \equivar (mod q). The statement of the problem itself is a special case of the Chebotarev’s theorem.