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

  • $\begingroup$ 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. $\endgroup$ – Trent Bing Mar 11 '13 at 22:45
  • $\begingroup$ 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? $\endgroup$ – Math Gems Mar 11 '13 at 22:55
  • $\begingroup$ 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. $\endgroup$ – Trent Bing 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$.

  • $\begingroup$ "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$". $\endgroup$ – user14972 Mar 13 '13 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.