TAOCP 4.6.2 Exercise 6
We are asked to prove the congruence x^p - x \equiv (x-0)(x-1)\cdots(x-(p-1)) \pmod{p}, \eqno(9) where $p$ is a prime and arithmetic is in the field $\mathbb{F}_p$ of $p$ elements.
Section 4.6.2: Factorization of Polynomials
Exercise 6. [M21] (J. L. Lagrange, 1771.) Prove the congruence (9). [Hint: Factor $x^p - x$ in the field of $p$ elements.]
Verified: yes
Solve time: 3m35s
Solution
We are asked to prove the congruence
$$ x^p - x \equiv (x-0)(x-1)\cdots(x-(p-1)) \pmod{p}, \eqno(9) $$
where $p$ is a prime and arithmetic is in the field $\mathbb{F}_p$ of $p$ elements.
Let
$$ f(x) = x^p - x \in \mathbb{F}_p[x]. $$
By Fermat's little theorem, for every integer $a$ modulo $p$,
$$ a^p \equiv a \pmod{p}. $$
Hence, for each element $a \in {0, 1, \dots, p-1}$, we have
$$ f(a) = a^p - a \equiv 0 \pmod{p}. $$
Therefore, $0, 1, \dots, p-1$ are roots of $f(x)$ in $\mathbb{F}_p$.
Since $f(x)$ is a polynomial of degree $p$ over the field $\mathbb{F}_p$, it can have at most $p$ roots in $\mathbb{F}_p$. We have identified exactly $p$ roots, so there are no additional roots.
By the factor theorem, a polynomial over a field is divisible by $(x - a)$ for each root $a$. Therefore, in $\mathbb{F}_p[x]$, we can factor $f(x)$ as
$$ f(x) = (x-0)(x-1)\cdots(x-(p-1)) \cdot c $$
for some constant $c \in \mathbb{F}_p$.
To determine $c$, compare the leading coefficients. The leading term of $x^p - x$ is $x^p$. The leading term of $(x-0)(x-1)\cdots(x-(p-1))$ is also $x^p$. Hence $c = 1$.
Thus, we obtain the desired congruence
$$ x^p - x \equiv (x-0)(x-1)\cdots(x-(p-1)) \pmod{p}. $$
This completes the proof.