MACM 101 Lecture 26: Lecture 26 Part 2_ Common Divisors

40 views2 pages

Document Summary

Let a and b be positive integers with a b. Set and successively apply the division algorithm until the remainder is 0. Eventually, the remainder is zero, because the sequence of remainders a = r0 > r1 > r2. >> 0 cannot contain more than a elements. Hence gcd(a,b) is the last nonzero remainder in the sequence. If a, b are integers and d is their greatest common divisor, then there are integers u, v such that d = au + bv. We use the euclidean algorithm and the notation a = r0, b = r1, d = rk r0 = r1q1 + r2 rk-3 = rk-2qk-2 + rk-1 rk-2 = rk-1qk-1 + rk rk-1 = rkqk. = r0u + r1v = au + bv. Find d = gcd(821,123) and integers u and v such that d = 821u + 123v a = 821, b = 123, d = 821 u + 123 v r0 = 821, r1 = 123.

Get access

Grade+
$40 USD/m
Billed monthly
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
10 Verified Answers
Class+
$30 USD/m
Billed monthly
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
7 Verified Answers

Related textbook solutions

Related Documents

Related Questions