Fermat's Little Theorem

$a^{p-1}\equiv 1{\pmod {p}}$
where $a$ is an integer and $p$ is a prime number.

Proof 1: Inductive Algebraic

Basis. The assertion holds for $a=0$ and $a=1$.

Induction. Assuming the assertion is true for $a$, we can show that the claim holds for $a+1$:

${\begin{aligned}(a+1)^{p}&=\sum _{k=0}^{p}{\binom {p}{k}}a^{k}1^{p-k}\\&\equiv a^{p}+1\mod {p}\\&\equiv a+1\mod {p}\\\end{aligned}}$

Therefore, the claim holds by induction on $a$.

quod erat demonstrandum

Proof 2: Group Theory

$\mathbb {Z} _{p}^{*}=\mathbb {Z} _{p}\setminus \left\{0\right\}$ (nonzero integers modulo $p$) forms a group over multiplication modulo $p$ with order $p-1$. Therefore, $a^{p-1}$ is equal to the identity element $1$ for any $a\in \mathbb {Z} _{p}^{*}$.

quod erat demonstrandum

Corollary

$a^{p}\equiv a{\pmod {p}}$