For a prime p, every integer a satisfies a^p ≡ a (mod p); when p does not divide a, this becomes a^(p−1) ≡ 1 (mod p). section 8.2.2
The theorem supports probabilistic primality testing: test randomly chosen values of a against the congruence. One failure proves that p is composite; repeated successes increase confidence but cannot guarantee primality, because some composite Carmichael numbers also pass these checks. section 8.2.2
A practical testing workflow follows:
- Choose random values of a for the candidate p. section 8.2.2
- Reject p immediately when any value violates the congruence. section 8.2.2
- Treat repeated successes as probabilistic evidence rather than proof. section 8.2.2
Equation 8.4
\[\begin{aligned} \label{equation:fermats-little-theorem-2} \begin{aligned} a^{p-1} - 1 &= 0 \pmod{p} \\ a^{p-1} &= 1 \pmod{p} \end{aligned} \end{aligned}\]Use the equivalent a^(p−1) ≡ 1 (mod p) form when checking bases that are not divisible by p. section 8.2.2
