= Solution
<Lagrange theorem for polynomial congruences> says that a nonzero <polynomial> of <degree of a polynomial>[degree] $d$ over the <finite field> $\mathbb F_p$ has at most $d$ roots. To prove it, use <mathematical induction> on $d$. A constant nonzero polynomial has no roots. If $f(a)=0$, <polynomial division> in the field $\mathbb F_p$ gives $f(X)=(X-a)q(X)$ with $\deg q=d-1$. Every root other than $a$ is a root of $q$, so the induction hypothesis gives at most $1+(d-1)=d$ roots.
Every nonzero <residue class> modulo $p$ has a unique <modular multiplicative inverse>[multiplicative inverse]. In the product $(p-1)!$, pair each class with its inverse. The unpaired classes satisfy $x=x^{-1}$, hence $x^2-1=0$. By the theorem these are exactly $1$ and $-1$, and therefore
$$
(p-1)!\equiv1\cdot(-1)\equiv-1\pmod p.
$$
This is <Wilson theorem>.
Now write $p-1=kq$. By <Fermat's little theorem>, every nonzero class is a root of
$$
X^{p-1}-1=(X^k-1)(1+X^k+\cdots+X^{(q-1)k}).
$$
The second factor has degree $p-1-k$ and hence at most $p-1-k$ roots. Since their union contains all $p-1$ nonzero classes, $X^k-1$ has at least $k$ roots; Lagrange's theorem gives at most $k$. Thus $x^k\equiv1\pmod p$ has exactly $k$ solutions.
Back to article page
