Tutorial: Euclidean Algorithm
2025-05-21
1 Euclidean Algorithm
In this tutorial, we’ll see the Euclidean Algorithm - one of the oldest algorithms dating back to 300BC.
The greatest common divisor for two natural numbers \(m, n\) is the greatest natural number, \(a \geq 1\), that divides both \(m\) and \(n\).
\(a\) divides \(n\) if there is some \(k \in \mathbb{N}\) such that \(ak = n\).
1.1
- What is GCD(6, 15)
- What is GCD(5, 10)
- What is GCD(0, 19)
- What is GCD(4321234,1234321)
Solution
3 , 5 , 19 , 12 Euclidean Algorithm Recursive
The Euclidean Algorithm finds the GCD of two numbers. Here is a recursive implementation.
Precondition, \(a, b \in \mathbb{N}\) with \(a \geq b\).
Source: Wikipedia.
Exercise: Trace this algorithm for GCD(4321234,1234321).
You can search \(x \mod y\) on google to get \(x \mod y\).
Here’s a start:
| a | b | a mod b |
|---|---|---|
| 4321234 | 1234321 | 618271 |
| 1234321 | 618271 | 616050 |
| 618271 | 616050 | 2221 |
Solution
| a | b | a mod b |
|---|---|---|
| 4321234 | 1234321 | 618271 |
| 1234321 | 618271 | 616050 |
| 618271 | 616050 | 2221 |
| 616050 | 2221 | 833 |
| 2221 | 833 | 555 |
| 833 | 555 | 278 |
| 555 | 278 | 277 |
| 278 | 277 | 1 |
| 277 | 1 | 0 |
| 1 | 0 |
2.1
We’ll now prove correctness of the algorithm. First, a lemma.
Lemma.
Suppose \(a, b \in \mathbb{N}\) with \(a \geq b\).
GCD(a, b) = GCD(b, a - b)
GCD(a, b) = GCD(b, a mod b)
Hint. Let \(g = \mathrm{GCD}(a, b)\), \(g' = \mathrm{GCD}(b, a-b)\). Show that in fact \(g\) divides \(a - b\) and \(g'\) divides \(a\).
Solution
1. GCD(a, b) = GCD(b, a - b)
Let \(g = \mathrm{GCD}(a, b)\). We have \(mg = a, ng = b\) since \(g\) divides both \(a\) and \(b\). Then \(a - b = g(m - n)\). Thus, \(g\) divides \(a - b\).
Let \(g' = \mathrm{GCD}(b, a-b)\). then we have \(og' = b\), and \(pg' = a - b\). Adding the two equations we get \(og' + pg' = a\), so \(a = g'(o - p)\) and thus \(g'\) is a divisor of \(a\)
Since \(g\) divides \(a - b\) and \(b\), and \(g' = \mathrm{GCD}(b, a-b)\), we have \(g \leq g'\). Similarly, since \(g'\) divides \(a\) and \(b\), and \(g = \mathrm{GCD}(a, b)\), \(g' \leq g\). Thus \(g' = a\).
2. GCD(a, b) = GCD(b, a mod b) P(n). For all \(n \in \mathbb{N}\) if \(a - nb \in \mathbb{N},\) then \(\mathrm{GCD}(a, b) = \mathrm{GCD}(b, a - nb)\)
Sketch. Base case is \(\mathrm{GCD}(a, b) = \mathrm{GCD}(b, a)\) which is true.
Inductive step: Use part a of the lemma!2.2
Now prove that the algorithm is correct.
Hint. Use induction on the second argument.
Solution
Sketch.
\(P(n)\). For all \(a \in \mathbb{N}\), the algorithm works on input \((a, n)\). We’ll show \(\forall n \in \mathbb{N}. P(n)\) by induction.
Base case. This is true b/c \(\mathrm{GCD}(a, 0) = a\) for all \(a \in \mathbb{N}\).
Inductive step. Use the lemma!2.3 (Optional)
Find the runtime of the algorithm.
3 Euclidean Algorithm Iterative
Precondition, \(a, b \in \mathbb{N}\) with \(a \geq b\). 
Source: Wikipedia.
3.1
Prove the algorithm is correct
It might help to think of the following questions.
Postcondition?
Descending Sequence?
Loop Invariant?
Solution
Loop invariant. \(P(n)\): After the \(n\)th iteration.
\(\mathrm{GCD}(a_n, b_n) = \mathrm{GCD}(a_0, b_0)\).
\(a_n, b_n\) are natural numbers.
Initialization. \(P(0)\) is true b/c both the RHS and the LHS are \(\mathrm{GCD}(a_0, b_0)\).
Maintenance. Assume \(P(k)\). We’ll show \(P(k+1)\). The variables \(b\) and \(a\) are updates as follows: \(b_{k+1} = a_k\mod b_k\), and \(a_{k+1} = b_k\). Then,
\[ \begin{align*} \mathrm{GCD}(a_{k+1}, b_{k+1}) &= \mathrm{GCD}(b_k, a_k \mod b_k)\\ &= \mathrm{GCD}(b_k, a_k) & (\text{Lemma})\\ &= \mathrm{GCD}(b_0, a_0) & (P(k))\\ \end{align*} \]
Termination. We’ll show the algorithm terminates later. For now, suppose the while check fails at the start of iteration \(k\). Then \(b_k = 0\). By \(P(k)\), we have \(\mathrm{GCD}(a_k, 0) = \mathrm{GCD}(a_0,b_0) = a_k\), which is the value that we return. Thus, we return \(\mathrm{GCD}(a_0, b_0)\) as required.
Descending sequence. We claim that \(b_i\) forms a descending sequence. Pick any \(i\). The above proof shows that \(a_i\) and \(b_i\) are both natural numbers. If \(b_i = 0\), the loop terminates. Otherwise, \(b_i > 0\) and the loop executes. We have \(b_{i+1} = a_i\mod b_i\) which is a natural number from \(0\) to \(b_i-1\) inclusive. Thus, \(b_{i+1} < b_i\), and \(b_0,b_1,...\) is a descending sequence. Thus, the algorithm terminates!