Question

This is a problem concerning GCD.

I need to prove gcd(a,b) = gcd(a,b+a).

I always get like like halfway then hit a roadblock (e.g. i can prove gcd(a,b) <= gcd(a,b+a) but not gcd(a,b) >= gcd(a,b+a).

Answer 1

By the way what ive got so far is:

gcd(a,b) = d, so d|a and d|b, so d|(a+b). Since d|(a+b) and d|a d <= gcd(a,b+a), which means gcd(a,b) <= gcd(a,b+a).

Its the other half that im stumped for.