Fermat's Little Theorem/Proof 3

From ProofWiki
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