Lab 9: The Euclidean Algorithm¶
Open Lab Notebook in Google Colab
Learning Objectives
Compute the greatest common divisor of two integers with the Euclidean algorithm, and use it to compute their least common multiple.
Derive and implement the base and recursive cases of the extended Euclidean algorithm.
Apply the extended Euclidean algorithm to construct an integer matrix with determinant \(1\) from two relatively prime integers.
Recommended Textbook Reading
From the Math 290 textbook (Doud and Nielsen):
§17: Divisibility
§18: The Extended Euclidean Algorithm