Fermat's Little Theorem

Fermats Little Theorem

• Let p be a prime and a be an integer such that $p\nmid a$, then

$$\begin{array}{r}{a}^{p-1}\equiv 1(\mathrm{mod}p)\end{array}$$

Proof $a^p\equiv a(\mathrm{mod}p)$. Primes and the Binomial Theorem will be helpful for lying this out: Base Case:

$$\begin{array}{rl}{0}^p& \equiv 0(\mathrm{mod}p)\\ 1^p& \equiv 1(\mathrm{mod}p)\\ 2^p=(1+1{)}^p& \equiv 1^p+1^p\equiv 1+1=2(\mathrm{mod}p)\\ 3^p=(2+1{)}^p& \equiv 2^p+1^p\equiv 2+1=3(\mathrm{mod}p)\\ & ⋮\end{array}$$

Inductive Step: Suppose that $a^p\equiv a(\mathrm{mod}p)$, then $(a+1{)}^p\equiv a^p+1^p\equiv a+1(\mathrm{mod}p)$ And since p is prime, a has an inverse, giving us: $a^{p-1}=a^{-1}\cdot a^p\equiv a^{-1}\cdot a\equiv 1(\mathrm{mod}p)$