Prove the following Let abn and r be integers with a and b n

Prove the following: Let a,b,n, and r be integers with a and b not zero. If a = nb + r, then the greatest common divisor of a and b is equal to the greatest common divisor of b and r.

Solution

Let, g=gcd(a,b) and h=gcd(b,r)

Hence, g|a, g|b and hence, g|(a-nb) , hence, g|r and g|b

But , h=gcd(b,r)

Hence, g|h

h|r and h|b , hence h|nb+r and hence, h|a and h|b

Hence, h|g

Hence, h=g