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

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

-
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

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

-
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

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

-