Prove that $\gcd(a,b) = \gcd (a+b, \gcd(a,b))$

Question

I started by saying that $\gcd(a,b) = d_1$ and $\gcd(a+b,\gcd(a,b)) = d_2$

Then I tried to show that $\ d_1 \ge d_2, d_1 \le d_2$.

I know that $\ d_2 | \gcd(a+b, d_1)$ hence $\ d_2 \le d_1 $.

How do I prove that $\ d_2 \ge d_1$ ?

Answer 1

If $\gcd(a,b)=d_1$ then $a = d_1 x$ and $b= d_1 y$, where $x,y$ are integers. Consequently, $$\gcd(a+b,\gcd(a,b))=\gcd(d_1(x+y),d_1) = d_1\gcd(x+y,1)=d_1.$$

Answer 2

$d_1$ divides $a$ and $b$, thus it divides $a+b$, and it divides $\gcd (a,b) $ (i.e. itself), thus $d_1$ divides $d_2$.

Answer 3

We have that $\exists x,y \in \mathbb{Z}$ s.t. $(a+b)x + d_1y = d_2$ by Euclid's Algorithm. Note that $d_1$ divides the LHS, so we must have $d_1 \mid d_2$ and hence the proof.

Answer 4

Don't worry about size so much as what they divide.

1) $\gcd(a,b)=d_1$ by definition divides $a$ and $b$ and thus $a+b$. And everything divides itself. So $\gcd(a,b)$ is a common divisor of $a+b$ and $\gcd(a,b)$ (and thus by definition is less or equal to the greatest common divisor of $a+b$ and $\gcd(a,b)$. $d_1 \le d_2$).

2) Likewise $\gcd(a+b, \gcd(a,b))= d_2$ divides $\gcd(a,b)$. So $d_2$ divides everything that $\gcd(a,b)$ divides so $d_2|a$ and $d_2|b$. So $d_2$ is a common divisor of $a$ and $b$ (and thus by definition is less than or equal to the greatest common divisor of $a$ and $b$. $d_2 \le d_1$.)

Obligatory fleablood essay: It's best not the think of the "greatest" in greatest common divisor as size as in "Five is bigger than four" but more in the sense of "completeness". The size of the GCD is of little interest or importance. What really matters is that can't find a more "comprehensive" factor but adding an additional component factor to GCD or by replacing a component factor of the GCD with another.

As a direct consequence the GCD is the largest possible factor but that is mostly and usually irrelevant.

Many text do not define the "greatest common factor" as "the common factor that is greatest" but as "the common factor so that all other common factors will divide into it". I, personally, find this a troubling definition because i) it sounds much more obscure and obtuse than it actually is and ii) we must prove that there is such a number and that it is unique.

But I do like that it relates directly wot what does and does not divide the two terms and how.

By that definition: 1) above says $d_1|d_2$ and 2) says $d_2|d_1$ so (assuming we are dealing with positive integers) $d_1 = d_2$.