TAOCP 7.2.1.1 Exercise 103

Section 7.2.1.1: Generating All n-Tuples

Exercise 103. [M20] [M20] Use Eq. (59) to prove Fermat’s theorem that mp ≡m (modulo p).

Verified: yes
Solve time: 1m05s

Solution

Let $p$ be a prime. Equation (59) in Section 7.2.1.1 asserts the binomial congruence

$$ (x+y)^p \equiv x^p + y^p \pmod p, $$

which follows from the binomial theorem together with the fact that for $1 \le k \le p-1$, the binomial coefficient $\binom{p}{k}$ is divisible by $p$.

Take $x = k$ and $y = 1$. The binomial expansion gives

$$ (k+1)^p = \sum_{i=0}^{p} \binom{p}{i} k^i. $$

Separating the extreme terms yields

$$ (k+1)^p = k^p + 1 + \sum_{i=1}^{p-1} \binom{p}{i} k^i. $$

For $1 \le i \le p-1$, the factor $p$ divides $\binom{p}{i}$, hence each term in the middle sum is divisible by $p$. Therefore,

$$ (k+1)^p \equiv k^p + 1 \pmod p. $$

Define the statement $P(m)$ by

$$ P(m):\quad m^p \equiv m \pmod p. $$

For $m=0$, one has $0^p \equiv 0 \pmod p$, so $P(0)$ holds.

Assume $P(k)$ holds, that is, $k^p \equiv k \pmod p$. Then

$$ (k+1)^p \equiv k^p + 1 \equiv k + 1 \pmod p, $$

where the first congruence uses the binomial result above and the second uses the induction hypothesis. Thus $P(k+1)$ holds whenever $P(k)$ holds.

By induction on $m$, the congruence $m^p \equiv m \pmod p$ holds for all nonnegative integers $m$.

This completes the proof. ∎

$$ \boxed{m^p \equiv m \pmod p} $$