greatest common divisor

if a and b are positive integers, show that gcd(a,b)=gcd(a,a+b),
gcd represents the greatest common divisor.

Hello,

Quote:

---

Originally Posted by tryitall34567

if a and b are positive integers, show that gcd(a,b)=gcd(a,a+b),
gcd represents the greatest common divisor.

---

Let d=gcd(a,b)
Let d'=gcd(a,a+b)

d divides a and b. Hence it divides a+b too. So it divides both a & a+b. Then d divides d'.

d' divides a and a+b. Hence it divides (a+b)-a=b. So it divides a & b. Then d' divides d.

This shows that d=d'.