Fermat's Little Theorem/Proof 4
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
Proof by induction over $n$.
Induction base:
- $1^p \equiv 1 \pmod p$
Induction step:
Assume $n^p \equiv n \pmod p$
\(\ds \paren {n + 1}^p\) | \(=\) | \(\ds \sum_{k \mathop = 0}^p {p \choose k} n^{p - k} \cdot 1^k\) | Binomial Theorem | |||||||||||
\(\ds \forall k: 0 < k < p: \, \) | \(\ds {p \choose k}\) | \(\equiv\) | \(\ds 0 \pmod p\) | Binomial Coefficient of Prime |
and so:
\(\ds \sum_{k \mathop = 0}^p {p \choose k} n^{p - k}\) | \(\equiv\) | \(\ds n^p + n^0 \pmod p\) | ||||||||||||
\(\ds \) | \(\equiv\) | \(\ds n^p + 1 \pmod p\) | ||||||||||||
\(\ds \) | \(\equiv\) | \(\ds n + 1 \pmod p\) | Induction Step |
Dividing by $n$:
- $\forall n: n^p \equiv n \pmod p \implies n^{p - 1} \equiv 1 \pmod p$
$\blacksquare$