Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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

share|improve this answer
    
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
up vote 1 down vote accepted

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

share|improve this answer
    
"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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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