proof of Euler-Fermat theorem using Lagrange’s theorem

Theorem.

Given $a\mathrm{,}n\mathrm{\in }\mathrm{Z}$, $a^{\varphi \mathit{}\mathrm{(}n\mathrm{)}}\mathrm{\equiv }\mathrm{1}\mathrm{(}\mathrm{mod}n\mathrm{)}$ when $\text{𝑔𝑐𝑑}\mathit{}\mathrm{(}a\mathrm{,}n\mathrm{)}\mathrm{=}\mathrm{1}$, where $\varphi$ is the Euler totient function.

Proof.

We will make use of Lagrange’s Theorem: Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then the order of $H$ divides the order of $G$.

Let $G={(\mathbb{Z}/n\mathbb{Z})}^{\times }$ and let $H$ be the multiplicative subgroup of $G$ generated by $a$ (so $H=\{1,a,a^2,\mathrm{\dots }\}$). The fact that $\gcd (a,n)=1$ ensures that $a\in G$. Notice that the order of $H$, $h=|H|$ is also the order of $a$, i.e. the smallest natural number $n>1$ such that $a^n$ is the identity in $G$, i.e. $a^h\equiv 1modn$. Also, recall that the order of $G={(\mathbb{Z}/n\mathbb{Z})}^{\times }$ is $\varphi (n)$, where $\varphi$ is the Euler $\varphi$ function.

By Lagrange’s theorem $h\mid |G|=\varphi (n)$, so $\varphi (n)=h\cdot m$ for some $m$. Thus:

$$a^{\varphi (n)}={(a^h)}^m\equiv 1^m\equiv 1modn$$

as claimed.∎