Tell me more ×
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.
up vote 0 down vote favorite

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 at 17:48
What is a? What is m? – Ludolila Feb 17 at 17:48
Shosh, be more careful when copying questions: you seem to have mixed up a,m,x,y... – DonAntonio Feb 17 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 at 17:51
sorry, now i fixed it – shosh Feb 17 at 17:53
show 4 more comments

3 Answers

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 at 18:48
up vote 3 down vote

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 at 20:20
up vote 0 down vote

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.