1
$\begingroup$

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

  • 9
    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.2011-10-13
  • 0
    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.2011-10-13
  • 1
    Note $\rm\:a|b \iff gcd(a,b) = a\:.$ So you seem to be missing a hypothesis that $\rm\:a\ne \pm1\:.$2011-10-13
  • 0
    What happens when you assume that $b=ac$ for some integer $c$? What does that tell you about 1?2011-10-13
  • 0
    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)$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 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.