How do I prove $\gcd(a,b) = \gcd(a+b, b)$

Question

How do I prove $\gcd(a, b) = \gcd(a+b, b)$.

I know that by the euclidean algorithm, I can obtain the following equations

$ax_1 + by_1 = \gcd(a, b)\tag{1}$

$(a+b)(x_2) + (b)(y_2) = \gcd(a+b, b)\tag{2}$

I tried some algebraic manipulation but I can't seem too prove that $\gcd(a, b) = \gcd(a+b, b)$.

Answer 1

Let $\gcd (a,b)=d$ with $d \in \mathbb{N}^*$. We have $a=da_1,b=db_1$ with $a_1,b_1 \in \mathbb{N}$ and $\gcd (a_1,b_1)=1$.

We have $a+b=d(a_1+b_1)$ and $b=db_1$. Since $\gcd (a_1,b_1)=1$ then $\gcd (a_1+b_1,b_1)=1$. Therefore $\gcd (d(a_1+b_1),db_1)=d$ or $\gcd (a+b,b)= d= \gcd (a,b)$.

REMARK. To prove $\gcd (a_1+b_1,b_1)=1$ with $\gcd (a_1,b_1)=1$. You assume that if $\gcd (a_1+b_1,b_1)=m>1$. Then $m|b_1$ and $m\mid (a_1+b_1)-b_1$ or $m\mid a_1$, a contradiction since $\gcd (a_1,b_1)=1$. Thus, $\gcd (a_1+b_1,b_1)=1$.

Answer 2

Try using the Bezout Lemma. It states that for each pair of integers $(a,b)$ there is an integer solution to this equation:

$$ax + by = \gcd(a,b)$$

Now let's think like this:

$$(a+b)x + by = \gcd(a+b,b)$$ $$ax + bx + by = \gcd(a+b,b)$$ $$ax + b(x+y) = \gcd(a+b,b)$$

If we divide $(a+b)x + by = \gcd(a+b,b)$ by $\gcd(a+b,b)$ the RHS will be 1. Taking, $z = x+y$, if we divide $ax + bz = \gcd(a,b)$ by $\gcd(a,b)$ the RHS will be one again.

Now if we make back the substitution $z=x+y$, we'll have:

$$\frac{(a+b)x + by}{\gcd(a+b,b)} = 1, \frac{ax + b(x+y)}{\gcd(a,b)} = 1$$

$$\frac{(a+b)x + by}{\gcd(a+b,b)} = \frac{ax + b(x+y)}{\gcd(a,b)}$$

Because the numerator is the same, that implies that the denominator is same, i.e. $\gcd(a,b) = \gcd(a+b,b)$

Q.E.D.