# Fermat's Little Theorem/Proof 4

## 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$