Lab 9: The Euclidean Algorithm

Open Lab Notebook in Google Colab

Learning Objectives

  1. Compute the greatest common divisor of two integers with the Euclidean algorithm, and use it to compute their least common multiple.

  2. Derive and implement the base and recursive cases of the extended Euclidean algorithm.

  3. 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