Ground Plan - Prove Fermat-Euclid's Totient Theorem with Lagrange's Theorem

Question

If $\gcd(a,n) = 1$, then $a^{\phi(n)}\equiv 1\pmod n$. Here's a three-step proof.

1. An integer a is invertible means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod n$. By cause of Jones p84 lemma 5.1 and the Linear Congruence Theorem, an integer $a$ is invertible modulo $n \iff ax \equiv 1 \pmod n \iff \gcd(a,n) \mid 1 \iff \gcd(a,n) = 1.$

2. Consider the Abelian group of all positive integers less than $n$ which are invertible modulo $n$. This is dubbed $U_n$ in Jones p85 or $\langle(Z_n',{\times})\rangle$ at Proofwiki.
   $ \phi(n)$ simply counts the number of positive integers $a$ coprime to a. So by 1., there are $\phi(n)$ elements in $G$. Tthe order of $G$ is $\phi(n)$.

3. Lagrange's Theorem occasions Order of Group Element Divides ORder of Finite Group. Thence there must be some $k$ such that $a^{k}=1$ where $k$ divides the order of the group $\langle (Z_n',{\times})\rangle$. This is just $\phi(n)$. Let's say $km=\phi(n)$ Then $a^{\phi(n)}=(a^k)^m=1^m=1$.

(1) Is the last paragraph errorless? The last sentence contains equalities, but Proofwiki's last steps are congruences modulo $m$.

(2) What's the ground plan of the proof? It feels 'oracular' to me - how can you preconceive to consider this uncanny Abelian group, and then to use a corollary of Lagrange's Theorem?

Answer 1

Nothing special about the finite group is really being used, just its order, which you've already determined is $\phi(n)$. Step 3 would hold for any finite group $G$, with $\phi(n)$ replaced with $|G|$.

The last paragraph is fine: the operation in $(Z'_n,\times)$ is just multiplication modulo $n$. Two units $x,y$ modulo $n$ (elements in $\mathbb Z$) are congruent modulo $n$ just if their classes $\bar x, \bar y$ are equal in $(Z'_n,\times)$.

Answer 2

Here is a simple proof that does not depend on Lagrange's theorem:

Consider the map $x\mapsto ax$ on $U_n$. This map is injective because $\gcd(a,n)=1$. Since $U_n$ is finite, the map is surjective, and so is a permutation of $U_n$. Hence $(ax_1)(ax_2)\cdots (ax_m)=x_1x_2\cdots x_m$, where $x_1, x_2,\cdots x_m$ are the elements of $U_n$. Hence $a^m x_1x_2\cdots x_m = x_1x_2\cdots x_m $ and so $a^m=1$, by cancellation. Finally, $m=\phi(n)$.

This proof actually works for all finite abelian groups.