How do I prove $\gcd(a,b) = \gcd(a+b, b)$ 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)$.
 A: 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$.
A: 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.
