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.
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).
1 answer