MATH135 Study Guide - Quiz Guide: Coprime Integers, Extended Euclidean Algorithm, Euclidean Algorithm
![MATH135 Full Course Notes](https://new-docs-thumbs.oneclass.com/doc_thumbnails/list_view/2419643-class-notes-ca-u-of-waterloo-math-135-lecture29.jpg)
40
MATH135 Full Course Notes
Verified Note
40 documents
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.