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

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

share|improve this question
8  
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
1  
Note $\rm\:a|b \iff gcd(a,b) = a\:.$ So you seem to be missing a hypothesis that $\rm\:a\ne \pm1\:.$ – Gone 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
show 4 more comments

1 Answer

up vote 2 down vote accepted

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.

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.