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