Fermat's Little Theorem
For prime : for all , equivalently whenever .
Theorem 4.31 (Fermat's Little Theorem)
Let be a prime. Then for all . Equivalently, for all .
Proof
If , then is a unit modulo , so iff , by cancelling . Hence the numbers are pairwise incongruent and not congruent to modulo ; they must therefore be congruent to in some order. Multiplying,
that is,
Since is a product of units, it is itself a unit modulo , so it can be cancelled to give . Multiplying by yields the equivalent form .
Related
Stated in
- Theorem 4.31 (Fermat's Little Theorem)§4.7 Prime Modular Arithmetic