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$?
1
$\begingroup$
elementary-number-theory
-
9I 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. – 2011-10-13
-
0What 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. – 2011-10-13
-
1Note $\rm\:a|b \iff gcd(a,b) = a\:.$ So you seem to be missing a hypothesis that $\rm\:a\ne \pm1\:.$ – 2011-10-13
-
0What happens when you assume that $b=ac$ for some integer $c$? What does that tell you about 1? – 2011-10-13
-
0I 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)$ – 2011-10-13
-
0@robjohn: I mean (gcd(a,b)=1⟺ax+by=1)⟹a∤b. – 2011-10-14
-
0@Aaron: if b=ac, then a|b, but I don't know then what conclusions to draw from there. Only I know is that if a|b, then ax+by=ax+acy=a(x+cy)=1 => a=1, x+cy=1. – 2011-10-14
-
0@alvoutila Yes, if $a\vert b$ and $ax+by=1$ then $a=1$. – 2011-10-14
-
0@alvoutila: in that case it is false. If $a=2$ and $b=2$, then both sides of the $\Longleftrightarrow$ are false so the $\Longleftrightarrow$ is true, but $2\nmid2$ is false. In fact, if $a\not=1$ and $a\mid b$, then $a$ and $b$ are counterexamples. – 2011-10-14
1 Answers
2
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.