There is a theorem that says that every pair of integers $a$ and $b$ has a common divisor $d$ of the form $d = ax+by$ where $x$ and $y$ are integers.
Is it true that $d$ is also definitely the greatest common divisor of $a$ and $b$? Why is that so?
Asked
Active
Viewed 756 times
0
-
Not for $a=b=0$. And we want $d$ positive. – André Nicolas Aug 09 '14 at 15:52
-
https://proofwiki.org/wiki/B%C3%A9zout%27s_Lemma – lab bhattacharjee Aug 09 '14 at 15:59
2 Answers
3
Such linear common divisors are greatest: $\, c\mid a,b\,\Rightarrow\,c\mid ax+by = d\,\Rightarrow\, c\le d\ \ $ (if $d > 0)$
Bill Dubuque
- 272,048
-
Is the second $\rightarrow$ true because if $c$ divides $d$, then $c \le d$ is necessarily true because the definition of $c$ divides $d$ is that $cn=d$ where $n$ is an integer (and not a fraction)? Also, the above explanation depends on the fact that $d$ actually divides $a$ and $b$ right? – darkgbm Aug 09 '14 at 16:05
-
@LateLearner Yes, the definition of integer divisibility is used to deduce the inequality. That $,d\mid a,b,$ is not used above. It is essentially using that the set $,c,\Bbb Z,$ of multiples of $,c,$ form an ideal, i.e. they are closed under addition, and under scaling by any integer. From this viewpoint the inference is $,a,b\in c,\Bbb Z,\Rightarrow,ax,by\in c,\Bbb Z,\Rightarrow, ax+by\in c,\Bbb Z.\ $ – Bill Dubuque Aug 09 '14 at 16:12
1
No, it is not true. Once you have $d=ax+by$, you get $2d=(2a)x+(2b)y$ for free (or any other multiple).
Jacob Bond
- 1,275
-
2I think the question almost explicitly specifies that $d$ is a common divisor of $a$ and $b$. – André Nicolas Aug 09 '14 at 15:56
-
Oh, ok. I thought it was asking whether $d$ being representable by $ax+by$ implies $\rm{gcd}$. – Jacob Bond Aug 09 '14 at 15:59
-
1What the question asks is a matter of interpretation. In any case, your answer adds useful information. – André Nicolas Aug 09 '14 at 16:03