IMO 2003 · Problem 6

Show that for each prime \(p\), there exists a prime \(q\) such that \(n^p-p\) is not divisible by \(q\) for any positive integer \(n\).

Official text of the problem. Official problem paper (PDF)

Solution

Let \(p\) be any prime, and put \[ N=1+p+p^2+\cdots+p^{p-1}. \] Since \(p\ge 2\), we have \(N>1\) and \[ N\equiv 1+p\not\equiv 1\pmod{p^2}. \] Consequently, \(N\) has a prime divisor \(q\) such that \[ q\not\equiv 1\pmod{p^2}. \] Indeed, if every prime divisor of \(N\) were congruent to \(1\) modulo \(p^2\), their product, counted with multiplicity, would also be congruent to \(1\).

We claim that this \(q\) works. From \[ (p-1)N=p^p-1 \] we obtain \(p^p\equiv 1\pmod q\). Moreover, \(p\not\equiv 1\pmod q\): otherwise the \(p\) summands defining \(N\) would give \[ N\equiv p\equiv 1\pmod q, \] contrary to \(q\mid N\).

Suppose now that some positive integer \(n\) satisfies \(n^p\equiv p\pmod q\). Then \[ n^{p^2}\equiv p^p\equiv 1\pmod q, \qquad n^p\not\equiv 1\pmod q. \] Thus the multiplicative order \(d\) of \(n\) modulo \(q\) divides \(p^2\) but does not divide \(p\). Since \(p\) is prime, this forces \(d=p^2\).

On the other hand, Fermat’s little theorem gives \(n^{q-1}\equiv 1\pmod q\), so \(d\mid q-1\). Here the order divides any exponent giving residue \(1\), as follows immediately by dividing that exponent by \(d\) and using the minimality of \(d\). Therefore \[ p^2\mid q-1, \] contradicting our choice of \(q\).

Hence \(q\nmid n^p-p\) for every positive integer \(n\), as required. \(\square\)

The solution was checked against Evan Chen's published IMO solution notes.