TAOCP 1.2.4 Exercise 25
By Theorem F, if $p$ is prime then a^p \equiv a \pmod p.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 25. [M02] Show that, according to Theorem F, $a^{p-1} \bmod p = [a \text{ is not a multiple of } p]$ whenever $p$ is a prime number.
Verified: yes
Solve time: 1m18s
By Theorem F, if $p$ is prime then
$$ a^p \equiv a \pmod p. $$
If $a$ is not a multiple of $p$, then $a \perp p$ since $p$ is prime. Hence Law B permits cancellation of the factor $a$ from
$$ a^p \equiv a \pmod p, $$
yielding
$$ a^{p-1} \equiv 1 \pmod p. $$
Therefore $a^{p-1} \bmod p = 1$ when $a$ is not a multiple of $p$.
If $a$ is a multiple of $p$, then $a \equiv 0 \pmod p$, so by repeated application of Law A,
$$ a^{p-1} \equiv 0 \pmod p. $$
Hence $a^{p-1} \bmod p = 0$ when $a$ is a multiple of $p$. Combining the two cases,
$$ a^{p-1} \bmod p = \begin{cases} 1, & \text{if } a \text{ is not a multiple of } p,\ 0, & \text{if } a \text{ is a multiple of } p. \end{cases} $$
Thus
$$ \boxed{a^{p-1} \bmod p = [a \text{ is not a multiple of } p].} $$