> [!NOTE] **Theorem** (FLT) > Let $p$ be a [[Prime Numbers|prime number]]. Let $a\in \mathbb{Z}$ such that $p \nmid a$. Then $a^{p-1} \equiv 1 \pmod{p}$ ###### Proof The first $(p-1)$ multiples of $a$ are $a,2a,3a,\dots,(p-1)a \tag{1}$We claim that they are all distinct modulo $p.$ Suppose not then $ra \equiv sa \pmod{n}$ for some $r,s.$ Thus $(r-s)a\equiv0 \pmod{n}.$ Since $a$ is not a multiple of $p,$ it has an inverse $a^{-1} \pmod{p}$ by [[Unit modulo n iff Coprime to n|unit modulo p]] so $r \equiv s \pmod{p}.$ But all numbers $1,\dots,(p-1)$ are different modulo $p$ so $r=s$ and the numbers in $(1)$ are congruent to $1,2,3,\dots,p-1$in some order. Multiplying them together gives $(p-1)!\;a^{p-1}\equiv (p-1)! \pmod{p}$Now $\gcd((p-1)!,p)=1$ so $(p-1)!$ it has a multiplicative inverse modulo $p.$ Multiplying both sides by this gives $a^{p-1} \equiv 1 \pmod{p}.$ ###### Proof by induction on $a$ STS $n^{p}\equiv n \pmod{p}$ for all positive integers $n$ since if $p \not \mid n,$ then multiplying both sides by the inverse of $n$ gives $n^{p-1} \equiv 1 \pmod{p}.$ Also, clearly $n^{p-1}\equiv (-n)^{p-1}\pmod{p}$ for all odd primes $p$ and $-1 \equiv 1 \pmod{2}.$ The equality holds for $n=1.$ Suppose the equality holds for $n=k$ where $k$ is some positive integer: that is, $k^p - k \equiv 0 \pmod{p}.$ Then we have $\begin{align} (k+1)^p - (k+1) &\equiv k^p + 1 - k -1 + \sum_{i=1}^{p-1} {p \choose i} k^i ) \pmod{p} \\ &\equiv \sum_{i=1}^{p-1} {p \choose i}k^i \pmod{p} \end{align} $Observe that ${p \choose i}= \frac{p(p-1) \cdots (p-i+1)}{1 \cdot 2 \cdots i}$ is divisible by $p$ for $1\leq i \leq p-1$ since the numerator is divisible by $p$ while the denominator is not. Therefore $(k+1)^p -k+1 \equiv 0 \pmod{p}.$ Thus by [[Induction Principle|mathematical induction]], the congruence holds for all positive integers $n.$ ###### Proof The order of any member of a finite group divides the order of the group by [[Order of Element of Finite Group Divides Order of The Group|Lagrange's theorem]]. If $p \not \mid a,$ then $a\in(\mathbb{Z}/p\mathbb{Z})^{\times}$ (the [[Unit Group of Integers Modulo n|unit group modulo p]]) since $\gcd(a,p)=1.$ Now $(\mathbb{Z}/p\mathbb{Z})^\times$ has order $p-1=\varphi(p)$ by the definition of the [[Euler Totient Function|Euler totient function]] so the order of $a$ divides $p-1$ and $a^{p-1}=1.$ ###### Proof This follows from [[Euler's Theorem (Number Theory)]], with $m=p$ since $\varphi(p)=p-1.$