> [!NOTE] Theorem (Euler) >Let $a,n\in\mathbb{Z}$ be [[Coprime Integers|coprime integers]]. Then $a^{\varphi(n)} \equiv 1 \pmod{n}$where $\varphi$ denotes the [[Euler Totient Function|Euler totient function]]. *Proof*. List the numbers of the form $ka$ where $1\leq k\leq n$ and $\gcd(k,n)=1.$ Check that they will all be distinct modulo $n.$ Multiplying them them together gives $\prod_{k=1}^{n} (ka) \equiv a^{\varphi(n)} \times \prod_{\substack{k=1,\dots, n\\ \gcd(k,n)=1}} k \equiv \prod_{\substack{k=1,\dots, n\\ \gcd(k,n)=1}} k \pmod{n}$Now $\prod_{\substack{k=1,\dots, n\\ \gcd(k,n)=1}}k$ is coprime to $n$ so has a multiplicative inverse modulo $n.$ Multiplying both sides by this give $a^{\varphi(n)}\equiv 1 \pmod{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 $\gcd(a,n)=1$ then $a\in(\mathbb{Z}/n\mathbb{Z})^{\times}$ (the [[Unit Group of Integers Modulo n|unit group modulo p]]). Now $(\mathbb{Z} /n\mathbb{Z})^\times$ has order $\varphi(n)$ by its definition so the order of $a$ divides $\varphi(n)$ and $a^{\varphi(n)}=1.$ # Applications **Corollaries**: [[Fermat's Little Theorem]]. **Examples**: ...