3
$\begingroup$

As part of the course's assignments, we received a task to prove the following sentence using only Bézout identity:

Every common divisor of $a, b$ divides the gcd $(a, b)$.

I tried the following proof: By Bézout's identity, we know that $$\text{gcd}(a,b) = ax + by\tag{*}$$ for some integers $x,y$.

Let $c$ be the common divisor of $a$ and $b$. By definition, since $c$ divides $a$, we know that there exists $k_1$ so that $ck_1 = a$. The same is true for $b$, so $k_2$ exists so that $ck_2 = b$. Replace $a$ and $b$ in an equation $(*)$ and received:

(Edited) $$\text{gcd}(a,b) = cxk_1+cyk_2 = c(xk_1+yk_2)$$ Therefore we obtained that $c$, which is any common divisor of $a$ and $b$ divides gcd $(a, b)$.

Is proof enough? To my mind, it seems too simple. I'm pretty new in the elementary number theory world, I'd be happy to have another opinion. Thanks

$\endgroup$
4
  • 2
    $\begingroup$ You haven't used $x$ and $y$ at all, so it cannot be literally true, but it has the right ideas in it. $\endgroup$ Apr 22, 2019 at 20:17
  • $\begingroup$ Oops, you're right. I meant to write like this: + gcd (a, b) = ax + by = cxk1 + cyk2 = c (xk1 + yk2) And the rest of the proof remains true $\endgroup$
    – StevenU
    Apr 22, 2019 at 20:31
  • $\begingroup$ Yep, this way it's true. $\endgroup$ Apr 22, 2019 at 20:32
  • 1
    $\begingroup$ This yields the fundamental GCD Universal Property $$ d\mid a.b,c\iff d\mid \gcd(a,b,c)$$ The dual for LCM is $$ a.b.c\mid m\iff {\rm lcm}(a,b,c)\mid m$$ These are in fact the definitions of GCD & LCM in more general rings. $\endgroup$ Apr 22, 2019 at 20:58

2 Answers 2

4
$\begingroup$

Apparently, your definition of greatest common divisor is “the largest common divisor”.

Assuming Bézout's identity $\gcd(a,b)=ax+by$, your proof is correct. If $c$ is a common divisor of $a$ and $b$, then by definition $a=ck_1$ and $b=ck_2$, for some integers $k_1$ and $k_2$, so you have $$ \gcd(a,b)=ax+by=ck_1x+ck_2y=c(k_1x+k_2y) $$ and this implies $c\mid\gcd(a,b)$.

Good job!

Linguistic remark: one should say “Let $c$ be a common divisor”, not “Let $c$ be the common divisor”.

$\endgroup$
1
$\begingroup$

I would define instead

$$k_1:= \frac{a\color{brown}x}{c}\implies a\color{brown}x=k_1c\qquad\qquad k_2:=\frac{b\color{brown}y}{c}\implies b\color{brown}y=k_2c$$

Therefore $$\text{gcd}(a,b)=a\color{brown}x+b\color{brown}y=k_1c+k_2c=c(k_1+k_2)\implies \color{red}{c\mid \text{gcd}(a,b)}$$

The proof doesn't make sense with your definitions of $\rm k_1$ and $\rm k_2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .