Trouble with proof of Euler's theorem using Multiplicative Inverses I am trying to understand a proof of Euler's theorem, namely the one that states $\gcd(a,n)=1 \implies a^{\phi(n)} = 1 \pmod n$. Here is how my teacher proved an important lemma that leads to the proof of Euler's theorem.
Define set $X = \left\{ m \in \mathbb{N} : m \leq n, \gcd(m,n)=1 \right\}$. Now choose $a \in X$. Define $aX = \left\{ ax \pmod n : x \in X \right\}$.
Lemma: $aX = X$. Proof: 
(i) $X \subseteq aX$: Given $x \in X$ we must show $x \in aX$. Consider the number $a^{-1}x \mod n$ ($a^{-1}$ is the multiplicative inverse of $a$ and exists since $a$ is relatively prime to $n$). We claim that $a^{-1}x \mod n \in X$ since it has the multiplicative inverse $x^{-1}a$. Thus $a(a^{-1}x) \equiv x \pmod n \in aX$.
...
I'll leave out part two of the lemma, because there is already something I'm not getting.
"We claim that $a^{-1}x \mod n \in X$ since it has the multiplicative inverse $x^{-1}a$."
How does the right half of that sentence imply the left half? I simply don't understand it at all. Would someone care to explain?
 A: Note $\rm\: a^{-1}x \equiv m\:$ invertible $\rm\,mod\ n\:\Rightarrow\: gcd(m,n) = 1\:\Rightarrow\:m\in X,\:$ by definition of $\rm\,X.$ Indeed  $\rm\:mod\ n\!:\ jm\equiv 1\:\Rightarrow\: jm = 1 + kn,\ k\in \Bbb Z,\:$ so $\rm\:d\mid m,n\:\Rightarrow\:d\mid jm-kn = 1,\:$ so $\rm\:gcd(m,n)=1.$
The invertible elements $\rm\,mod\ n\:$ are, by Bezout, precisely the set of elements coprime to $\rm\,n,\,$ which is called unit group of $\rm\,\Bbb Z/n\Bbb Z\ $ (unit means invertible element in rings/semigroups/monoids).
A: I now have a better understanding and would like to provide the answer that would have clarified this for me immediately.
Since $X$ consists of elements $x$ such that $\gcd(x, n) = 1$, by definition, the elements in $X$ are those with multiplicative inverses $\pmod n$. First we pick an element $x \in X$. If we consider $a^{-1}x \mod n$, then we know two things: $a^{-1}$ exists by definition since $\gcd (a,n) = 1$, and $x^{-1}$ exists because $x$ is in $X$, all elements of which have multiplicative inverses $\mod n$. Because $a^{-1}x$ is invertible $\mod n$, we can say that it is in $X$.  
