1
$\begingroup$

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

  • 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 1

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.