Fermat's Little Theorem

$a^{p-1}\equiv 1(\mathrm{mod}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{array}{rl}(a+1{)}^p& =\sum _{k=0}^p(\genfrac{}{}{0ex}{}{p}{k})a^k{1}^{p-k}\\ & \equiv a^p+1modp\\ & \equiv a+1modp\\ \end{array}$

Therefore, the claim holds by induction on

$a$

.

quod erat demonstrandum

Proof 2: Group Theory

${\mathbb{\mathbb{Z}}}_p^{*}={\mathbb{\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{\mathbb{Z}}}_p^{*}$

.

quod erat demonstrandum

Corollary

$a^p\equiv a(\mathrm{mod}p)$