# How you get from $\gcd(a,b)=1 \Longleftrightarrow ax+by=1 \Longrightarrow a \nmid b$?

How you get from $\gcd(a,b)= 1 \Longleftrightarrow ax+by=1 \Longrightarrow a \nmid b$?

-
I would be beneficial (for you and the website as a whole) if you went through your old posts and accepted the most helpful answer in each post. – JavaMan Oct 13 '11 at 19:29
What exactly are you asking? To show $\mathrm{gcd}(a,b)=1$ iff there exists $x,y$ such that $ax+by=1$ and this implies $a$ does not divide $b$? Or just the implication? The equivalence essentially comes from the Euclidean algorithm and the implication is not true in general: gcd(1,5)=1 and 1 divides 5. – Bill Cook Oct 13 '11 at 19:40
Note $\rm\:a|b \iff gcd(a,b) = a\:.$ So you seem to be missing a hypothesis that $\rm\:a\ne \pm1\:.$ – Bill Dubuque Oct 13 '11 at 19:43
What happens when you assume that $b=ac$ for some integer $c$? What does that tell you about 1? – Aaron Oct 13 '11 at 20:05
I don't know if $\Longleftrightarrow$ and $\Longrightarrow$ have a well accepted order of precedence, but I assume you intend $\gcd(a,b)=1\Longleftrightarrow\left(ax+by=1\Longrightarrow a\nmid b\right)$ – robjohn Oct 13 '11 at 20:23

HINT $\$ If $\rm\:a\:|\:b\:$ then $\rm\:a\:$ is a common divisor of both $\rm\:a,\:b\:,\:$ hence $\rm\:a\ |\ a\:x+b\:y\: =\: gcd(a,b) = 1\:,\:$ i.e. all common divisors must divide the gcd, i.e. the gcd is the divisibly-greatest common divisor, so $\rm\ c\:|\:a,b\iff c\:|\:gcd(a,b)\:.\:$ Adjoining the (necessary) hypothesis $\rm\ a\nmid 1\$ concludes the proof.