# How do I prove $\gcd(a,b) = \gcd(a+b, b)$ [duplicate]

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

## marked as duplicate by Git Gud, Julian Kuelshammer, Dan Rust, user1337, Davide GiraudoSep 4 '13 at 11:35

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|(a_1+b_1)-b_1$ or $m|a_1$, a contradiction since $\gcd (a_1,b_1)=1$. Thus, $\gcd (a_1+b_1,b_1)=1$.

• @Eagle1192 I think we can show this more easily as Let $gcd(a, b)=d_{1}$ and $gcd(a+b, b)=d_{2}$. Now $d_{1}/a$ and $d_{1}/b$ implies that $d_{1}/a+b$ and $d_{1}/b$, so we get $d_{1}/d_{2}$. This implies that $d_{1}\leq d_{2}$ Similarily we can show that $d_{2}\leq d_{1}$, this implies that $d_{1}=d_{2}$. – Noor Aslam Apr 19 '18 at 16:52
• @Noor Aslam : Can you please explain more on how we get d_{1}/d_{2} ? – ultimate cause Feb 22 at 5:10
• @ultimatecause $d_{1}=gcd(a,b)$ so it will divide both $a$ and $b$ and by linearity property it will also divide $a+b$, so we get that $d_{1}/a+b$ and $d_{1}/b$ but the $gcd(a+b, b)=d_{2}$ and $d_{1}$ is any number other number that divides $a+b$ and $b$, so by the properties of gcd it will also divide $d_{2}$. – Noor Aslam Mar 1 at 17:31

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.

• Are you sure it is appropriate to divide here? After all, we want to ensure we are working in $\mathbb{Z}$ rather than $\mathbb{Q}$. Otherwise none of what you written makes sense. – jamesmartini Aug 13 '17 at 3:39
• @jamesmartini Linear combinations are to be divisible by their $\gcd$, so you are wrong. – jiten Dec 14 '17 at 4:21
• @jamesmartini In fact, the logic used here shows use of 'what was to be proved'. – jiten Dec 14 '17 at 4:37