MATH135 Study Guide - Midterm Guide: Extended Euclidean Algorithm, Euclidean Algorithm, Divisor

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Wentang Kuo

Document Summary

Certi cate of correction: in this case to check d to be gcd(a, b) when d comes from euclidean algorithm, we can use gcd ct to check. By ea, we get d = 14 = gcd(1386, 322) Thus, 14 is a common divisor of 1386 and 322. By reversing ea, (back substitution), we have 14 = 10 1386 + ( 43)(322). Thus 14 is an integral combination of 1386 and 322. By gcd ct, 14 is indeed the gcd of 1386 and 322. Prove that gcd(x, y) = gcd(3x + 2y, x + y) 3x + 2y = 2(x + y) + x x + y = 1x + y. By gcd wr, gcd(3x + 2y, x + y) = gcd(x, y) If a > b > 0 are integers, then d = gcd(a, b) can be found. There is also exists x, y z such that ax + by = d.