Answer to Question #13265 in 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)

Learn more about our help with Assignments: Math

Comments

No comments. Be the first!

Leave a comment

Related Questions

1. 8y3 + [ (-4) + 6 ] = [ 8y3 + (-4) ]+6
2. How many integers from 1 to 9999 have exactly 15 divisors?
3. Paul's three children have birthdays in the same week. He bought a circular birthday cake and d
4. Hi, I currently have an order already in place...assignment number 37213. I placed the deadline for
5. A bag contains a number of 10paise,20 paise and 25 paise coins inratio 7:3:4. If value of money come
6. A picture is a 1.84 Gb and converted to 300Kb, what percentage is that?
7. Suppose the Toronto Maple Leafs meet Philadelphia Flyers, 1st round of playoffs, the series is best