Here is Euler’s theorem:
Let $a$ and $n$ be integers such that $n>0$ and $\gcd\{a,n\}=1$. Then $a^{\phi(n)} \equiv 1 \pmod n$.
Here is the proof:
Since $\lvert U(n)\rvert = \phi(n)$ and $\gcd\{a,n\}=1$ for all $a\in U(n)$, then $\color{red}{a^{\phi(n)}=a^{\lvert U(n)\rvert}=1}$. Since $U(n)$ is a group under modulo multiplication, $a^{\lvert U(n)\rvert}\equiv 1\pmod n$. Then $n \mid \left( a^{\lvert U(n)\rvert} -1\right)$ or $n \mid \left(a^{\phi(n)}-1\right)$ or $a^{\phi(n)}\equiv 1\pmod n$.
Can someone please explain to me the part in red? Is it saying that $\lvert a\rvert=\lvert U(n)\rvert$? And why is $a$ a generator of $U(n)$? Should $a$ be defined as a positive integer then?
Best Answer
Remember, if $G$ is a finite group of order $n$, then for all $g \in G$ we have $g^n = e$. Since the order of $U(n)$ is $\phi(n)$, then $a^{\phi(n)} = 1$ for all $a \in U(n)$.
Notice that $\mathbb{Z}/n\mathbb{Z}$ consists of equivalence classes and $U(n) = \{ \overline{a} \in \mathbb{Z}/n\mathbb{Z} \,:\, \gcd(a,n) = 1\}$. So the elements of $U(n)$ can be viewed as integers as long as you understand that we are really identifying the classes with representatives from each class (which are integers). For instance, in $U(12)$ we consider $5$ and $17$ to be the same element since they represent the same equivalence class in $\mathbb{Z}/12\mathbb{Z}$.
Also, if $n$ is not prime then $U(n)$ may not be cyclic (hence does not have a generator).