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.

Prove that $(a,m)=1$ iff there exists an integer $n$ such that $na \equiv 1 \pmod m$

How do I go about this problem?

share|improve this question
1  
What? How do you expect a condition on $x$ and $y$ to be equivalent to one on $a$ and $m$? –  Chris Eagle Feb 17 '13 at 17:48
    
What is a? What is m? –  Ludolila Feb 17 '13 at 17:48
    
Shosh, be more careful when copying questions: you seem to have mixed up a,m,x,y... –  DonAntonio Feb 17 '13 at 17:49
    
Shosh, it looks as though if you're given $na \equiv 1 \mod m$ that $n$ and $a$ are modular inverses of each other modulo $m$. I'm assuming you meant to show that $(n,a) = 1$? –  user39898 Feb 17 '13 at 17:51
    
sorry, now i fixed it –  shosh Feb 17 '13 at 17:53

3 Answers 3

up vote 2 down vote accepted

Be sure you can prove the following steps:

$$(a,m)=1\Longleftrightarrow \,\,\exists\,\,n,y\in\Bbb Z\,\,\,s.t.\,\,\,na+ym=1\Longleftrightarrow na=1-ym\Longleftrightarrow na=1\pmod m$$

share|improve this answer
    
Remark that one way to prove the first equivalence is to note that it is a special case of the Bezout identity for the gcd. There are also other methods. What works best depends on how one's number theory course is organized. –  Math Gems Feb 17 '13 at 18:48

As Don wrote, one way is by Bezout's gcd identity. Another is by Euclid's Lemma and pigeonholes.

$\rm(1)\,\ \ (a,m) = 1\Rightarrow\,$ the map $\rm\,x\to ax\,$ is $\,1$-$1\,$ on $\,\rm\Bbb Z/m\, = $ integers $\rm\,mod\ m,\,$ since $\rm\,ax \equiv ay\:\Rightarrow\:m\mid a(x-y)\:\Rightarrow\:m\mid x-y\Rightarrow x\equiv y,\:$ by Euclid's Lemma.

$\rm(2) \ \ x\to ax\:$ is $\,1$-$1\,$ so onto, by the Pigeonhole/box principle, since $\rm\:\Bbb Z/m\:$ is finite

$\rm(3)\ \ x\to ax\:$ is onto $\,\Rightarrow$ $\rm\:ax\equiv 1\:$ for some $\rm\,x.\quad$ QED

share|improve this answer
1  
Damn, I liked this one! +1 –  DonAntonio Feb 17 '13 at 20:20

If you have access to Ireland and Rosen's "Classical Introduction to Modern Number Theory," the pages 30 - 33 give a very readable presentation to the general congruence problem:

$ax \equiv b \pmod m$

share|improve this answer

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.