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

163 Views Asked by At

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

I understand the proof up till this point:

By definition of $\gcd(a,b)$ it implies that $d|a$ and $d\mid b$ thus, $d\mid a+b$, a linear combination of the two.

By definition of $\gcd(a+b,b)$ it implies that $d\mid a+b$ and $d\mid b$ thus, $d\mid(a+b)-b = a +b - b =b$

In the second statement, I don't understand where the subtraction comes from in $d\mid(a+b)-b = a +b - b =b$

1

There are 1 best solutions below

2
On BEST ANSWER

In the first statement,it should be like that:

Let $d=gcd(a,b)$

By definition, $d \mid a$, $d \mid b$,so $d$ divides also any linear combination of $a,b$,so it divides also their sum $a+b$.

In the second statement:

Let $d=gcd(a+b,b)$.

By definition, $d \mid a+b \text{ and } d \mid b$,so $d$ divides also any linear combination of $a+b,b$,so it divides also their difference $a+b-b=a$.