Euclidean Algorithm

The Euclidean algorithm gives an algorithm for finding the greatest common divisor of two integers.
It essentially relies on the following two facts about the GCD:
1. if $a \mid b$, then $\text{gcd}(a, b) = a$
2. $\text{gcd}(a, b) = \text{gcd}(b, \text{mod}(a, b))$

The algorithm uses identity (2) to repeatedly reduce the input pair $(a, b)$ until the base case (1) is reached rk.
*Remark*. Strictly speaking, we should justify that such a process eventually terminates. The justification boils down to noting that $\text{mod}(a, b) < b$, so our inputs shrink; in the worst case we reduce to $a=1$ or $b=1$ and terminate.

Referenced by: