IMO 1999 · Problem 4

Determine all pairs \((n,p)\) of positive integers such that

\(p\) is a prime,
\(n\) not exceeded \(2p\), and
\((p-1)^n+1\) is divisible by \(n^{p-1}\).

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

Answer

\[ \boxed{(n,p)=(1,p)\text{ for every prime }p,\quad (2,2),\quad (3,3).} \]

Solution

If \(n=1\), the divisibility condition holds for every prime \(p\).

If \(p=2\), the condition becomes \(n\mid 2\), so \(n=1\) or \(n=2\). Both satisfy \(n\le 2p\).

Henceforth assume that \(p\) is odd and \(n>1\). Since \((p-1)^n+1\) is odd, its divisor \(n^{p-1}\) is odd, so \(n\) is odd.

Let \(q\) be the smallest prime divisor of \(n\). We have \[ \gcd(n,q-1)=1, \] because any prime dividing both numbers would be a prime divisor of \(n\) smaller than \(q\).

The given divisibility implies \[ (p-1)^n\equiv-1\pmod q. \] Since \(n\) is odd, putting \(a=1-p\) gives \[ a^n\equiv1\pmod q. \] In particular, \(q\nmid a\), so Fermat’s little theorem gives \(a^{q-1}\equiv1\pmod q\). As \(\gcd(n,q-1)=1\), there are integers \(u\ge1\) and \(v\ge0\) such that \(nu=1+v(q-1)\). Therefore \[ 1\equiv(a^n)^u =a^{1+v(q-1)} \equiv a\pmod q. \] Thus \(1-p\equiv1\pmod q\), so \(q\mid p\). Since \(p\) is prime, \(q=p\).

Consequently \(p\mid n\). The bound \(n\le2p\) leaves only \(n=p\) or \(n=2p\); the latter is even. Hence \(n=p\).

We now require \[ p^{p-1}\mid(p-1)^p+1. \] For an odd prime \(p\), the binomial theorem gives \[ (p-1)^p+1 =p^2+\sum_{k=2}^{p}\binom pk p^k(-1)^{p-k} \equiv p^2\pmod{p^3}. \] Indeed, the term with \(k=2\) is divisible by \(p^3\), since \(\binom p2=p(p-1)/2\), and every term with \(k\ge3\) contains a factor \(p^3\).

Thus \((p-1)^p+1\) is divisible by \(p^2\) but not by \(p^3\). The required divisibility forces \(p-1\le2\), and therefore \(p=3\). This gives \(n=3\).

Finally, the remaining candidates do satisfy all conditions: \(n=1\) always works, and \[ (2-1)^2+1=2=2^{2-1},\qquad (3-1)^3+1=9=3^{3-1}. \] This proves the stated answer.

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