# Answer to Question #13265 in Other Math for Anish

Question #13265

Let a, b, q, r ∈ Z and suppose that a = bq + r. Show that gcd(a,b) = gcd(b,r)

Expert's answer

We use Bezout identity: d=gcd(a,b)=au+bv , for some u,v.

Then

d=(bq+r)u+bv=b(qu+v)+ru. Last equality shows that gcd(b,r)=d=gcd(a,b)

Then

d=(bq+r)u+bv=b(qu+v)+ru. Last equality shows that gcd(b,r)=d=gcd(a,b)

## Comments

## Leave a comment