# Understanding Proof of Euler's Theorem

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?

• I've added to my post, which I hope answers the last part of your question. Sep 9, 2018 at 15:04
• In my opinion the proof needs a re-write to put the argument in proper order. Let $U(n)=\{m: 1\leq m\leq n\land \gcd(m)=1\}.$ Then $U(n)$ is a group under multiplication mod $n$. A result often called Lagrange's theorem is that if $U$ is a finite group with identity $1$ then for all $m\in U$ we have $m^{|U|}=1.$ Therefore mod $p$ we have $1\equiv m^{|U(n)|}=m^{\phi(n)}$ for all $m\in U(n).$ Sep 9, 2018 at 17:33

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).
• Thank you for taking the time to reply. Your response has helped me connect the pieces of the proof. I rewrote the proof the following way based on your answer: "By Lagrange's theorem, since $|U(n)|=\phi (n)$ and $gcd(a,n)=1$, then $a^{\phi (n)}=a^{|U(n)|}=1$ for any $a\in U(n)$. Then $a^{\phi (n)} \equiv 1$ (mod $n$) iff there exists an integer $k$ such that $a^{\phi (n)}-1=nk$. Letting $k=0$ satisfies this equation." What do you think?
• You have that $a^{\phi(n)} = a^{|U(n)|} = 1$ for all $a \in U(n)$ (this is happening inside $U(n))$. This implies that $a^{\phi(n)}$ is in the same class as $1$, that is, $a^{\phi(n)} \equiv 1 \mod n$. This is what you wanted to prove, so you can stop here. Also, notice that in your last sentence you can't just make $k$ anything you want since it depends on $a$. Sep 10, 2018 at 5:19