# proof of Euler-Fermat theorem using Lagrange’s theorem

###### Theorem.

Given $a,n\in\mathbb{Z}$, $a^{\phi(n)}\equiv 1\pmod{n}$ when $\mbox{gcd}(a,n)=1$, where $\phi$ is the Euler totient function.

###### Proof.

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},\ldots\}$). 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 1\mod n$. Also, recall that the order of $G=(\mathbb{Z}/n\mathbb{Z})^{\times}$ is $\phi(n)$, where $\phi$ is the Euler $\phi$ function.

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

 $a^{\phi(n)}=(a^{h})^{m}\equiv 1^{m}\equiv 1\mod n$

as claimed. ∎

Title proof of Euler-Fermat theorem using Lagrange’s theorem ProofOfEulerFermatTheoremUsingLagrangesTheorem 2013-03-22 14:24:03 2013-03-22 14:24:03 alozano (2414) alozano (2414) 4 alozano (2414) Proof msc 11-00 LagrangesTheorem FermatsLittleTheorem FermatsTheoremProof