MATH135 Study Guide - Quiz Guide: Coprime Integers, Extended Euclidean Algorithm, Euclidean Algorithm

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Sean Mc Master

Document Summary

The extended euclidean algorithm and its consequences, part 1 (oct 11) Consider calculating gcd(574, 203) using the euclidean algorithm, shown below on the left side. The iterations of the division algorithm are shown on the right. gcd(574, 203) = gcd(203, 168) Using the data on the right and performing backward substitution, we can express gcd(574, 203) = 7 as an integer combination of 574 and 203, as follows: = 35 1 (168 4 35) = 5 (203 1 168) 1 168. = 5 203 6 (574 2 203) Thus, we nd that gcd(574, 203) = 7 = 574(6) + 203(17). l. In fact, there is a procedure known as the extended euclidean algorithm, which computes both gcd(a, b) and the needed integers x and y almost simultaneously.