# Proof that every common divisor divides GCD (solve only by Bézout's identity)

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

• You haven't used $x$ and $y$ at all, so it cannot be literally true, but it has the right ideas in it. – darij grinberg Apr 22 at 20:17
• 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 – StevenU Apr 22 at 20:31
• Yep, this way it's true. – darij grinberg Apr 22 at 20:32
• 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. – Bill Dubuque Apr 22 at 20:58

## 2 Answers

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

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