Fermat's Little Theorem/Proof 3
Jump to navigation
Jump to search
Theorem
Let $p$ be a prime number.
Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.
Then:
- $n^{p - 1} \equiv 1 \pmod p$
Proof
Let $\struct {\Z'_p, \times}$ denote the multiplicative group of reduced residues modulo $p$.
From the corollary to Reduced Residue System under Multiplication forms Abelian Group, $\struct {\Z'_p, \times}$ forms a group of order $p - 1$ under modulo multiplication.
By Element to Power of Group Order is Identity, we have:
- $n^{p - 1} \equiv 1 \pmod p$
$\blacksquare$
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $7$: Cosets and Lagrange's Theorem: Exercise $16 \ \text{(ii)}$