MATH135 Lecture Notes - Lecture 5: Coprime Integers, Extended Euclidean Algorithm

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Gabrielde Morais Coutinho

Document Summary

University of waterloo - fall 2014 - math 135. Write the gcd of 24 and 15 as an integer combination of these numbers. From this, it follows that gcd(24, 15) = 3. Moreover, we can reverse engineer these equalities, starting from the third and moving up. 3 = 9 6 = 9 (15 9) = 2 9 15 = 2(24 15) 15 = 2 24 3 15. Let"s now learn of organizing these ideas and nice and neat table. Write gcd(29, 13) as an integer combination of 29 and 13. We will start writing the following table: x y. The two last rows of the table are simply indicating that 29x + 13y = r for the given values of x and y. The column q is only important to keep track of the steps, as we will see now.