Euler's theorem

My cumbersome proof.

For $a,n\in\mathbb{N}$ which are coprime $$a^{\varphi(n)}\equiv1\left(\mod n\right)$$ where $\varphi(n)$, Euler's totient function, counts the positive integers up to $n$ that are coprime to $n$.

With Chinese remainder theorem, it suffices to show that for $q\in\mathbb{N}$, prime $p$, and $a \in\mathbb{N}$ that is coprime to $p$, $$a^{(p-1)p^{q-1}}\equiv1\left(\mod p^q\right).$$

Proof

Define $$L:=\left\{x\in\mathbb{Z}_{p^q}:x\equiv1\left(\mod p\right)\right\},$$ which has size $p^{q-1}$. It could be checked that $L$ is a multiplicative group. Consider $$b\equiv a^{p-1}\left(\mod p^q\right),$$ which by Fermat's little theorem is in $L$. Let $m$ be the smallest positive integer s.t. $b^m\equiv1\left(\mod p^q\right)$. Then $$L_1:=\left\{1,b,b^2,\dots,b^{m-1}\right\}$$ is a set. Pick an element $$c_1\in L\setminus L_1.$$It could be seen that $$\left\{c_1,c_1b,\dots,c_1b^{m-1}\right\}$$ is a set. Similarly pick an element $$c_2\in L\setminus L_1\setminus L_2.$$It could be seen that $$\left\{c_2,c_2b,\dots,c_2b^{m-1}\right\}$$ is a set. The process terminates eventually, and we have $m$ divides $p^{q-1}$, the size of $L$. Hence $$a^{(p-1)p^{q-1}}=b^{p^{q-1}}\equiv1\left(\mod p^q\right).$$