# 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?

-

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).

-
But how can we be sure, in your example, that $m \leq n$, also required per definition of $X$? That might be a dumb question, but I'm just not seeing the big picture, and that final piece of the puzzle might help. Also, thanks for the additional insight at the end there. –  Intredasting Mar 11 '13 at 22:45
Reduce it mod $\rm,n,$ so that is lies in $[0,n\!-\!1].$ Are you not familiar with properties of congruences, they can be multiplied and added? –  Math Gems Mar 11 '13 at 22:55
Ah, thanks for that! I know of the rules you mentioned, but it's hard for me to consider all these things at the same time, especially since I'm seeing a lot of new notation here. (I'm a CS major, not Maths). With that said, I'll think a bit more before posting such silly followups next time. –  Intredasting Mar 12 '13 at 0:51

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$.

-
"By definition" is the wrong phrase. $a^{-1}$ would exist by definition if you knew there existed a solution for $x$ to $$ax\equiv 1 \pmod n$$ However, it is 'close enough', as (IMO) you should mentally equate the two ideas "$a$ is invertbile mod $n$" and "$a$ is relatively prime to $n$". –  Hurkyl Mar 13 '13 at 23:24