Theorem 02   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. 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=(\Ints/n\Ints)^\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=(\Ints/n\Ints)^\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.