Fermat's Little Theorem/Proof 4

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

Proof by induction over $n$.

Induction base:

$1^p \equiv 1 \pmod p$

Induction step:

Assume $n^p \equiv n \pmod p$

\(\displaystyle \left({n + 1}\right)^p\) \(=\) \(\displaystyle \sum_{k \mathop = 0}^p {p \choose k} n^{p - k} \cdot 1^k\) Binomial Theorem
\(\displaystyle \forall k: 0 < k < p: {p \choose k}\) \(\equiv\) \(\displaystyle 0 \pmod p\) Binomial Coefficient of Prime

and so:

\(\displaystyle \sum_{k \mathop = 0}^p {p \choose k} n^{p - k}\) \(\equiv\) \(\displaystyle n^p + n^0 \pmod p\)
\(\displaystyle \) \(\equiv\) \(\displaystyle n^p + 1 \pmod p\)
\(\displaystyle \) \(\equiv\) \(\displaystyle n + 1 \pmod p\) by induction step

Dividing by $n$:

$\forall n: n^p \equiv n \pmod p \implies n^{p - 1} \equiv 1 \pmod p$

$\blacksquare$