← Browse / Number Theory
Algorithm E: Euclid's Algorithm
TAOCP Vol. 1, §1.1
Knuth §1.1 Number Theory
Given two positive integers $m$ and $n$, find their greatest common divisor (GCD) — the largest positive integer that divides both $m$ and $n$ without remainder.
Computation Method
E1
Find remainder
Divide $m$ by $n$ and let $r$ be the remainder. We will have $0 \leq r < n$.
$m = qn + r$, where $0 \leq r < n$
E2
Is it zero?
If $r = 0$, the algorithm terminates; $n$ is the answer.
$r = 0 \rightarrow$ return $n$
E3
Reduce
Set $m \leftarrow n$, $n \leftarrow r$, and go back to step E1.
$m \leftarrow n,\; n \leftarrow r \rightarrow$ goto E1
Why It Works
Key Identity
$$\gcd(m, n) = \gcd(n, m \bmod n)$$
If $m = qn + r$, then any common divisor of $m$ and $n$ is also a divisor of $r$, and vice versa. So $\gcd(m, n) = \gcd(n, r)$. Each step reduces the second argument strictly (since $r < n$), guaranteeing termination.
Computation Trace
$m = 544, n = 119$
| Step | m | n | r | Operation |
|---|---|---|---|---|
| E1 | 544 | 119 | 68 | 544 = 4×119 + 68 |
| E1 | 119 | 68 | 51 | 119 = 1×68 + 51 |
| E1 | 68 | 51 | 17 | 68 = 1×51 + 17 |
| E1 | 51 | 17 | 0 | 51 = 3×17 + 0 |
$\gcd(544, 119) = 17$
Complexity: $O(\log \min(m, n))$ — Gabriel Lamé proved in 1844 that the number of steps is at most five times the number of digits in the smaller number. This was one of the first analyses of an algorithm's running time.
Review Cards
Conceptual Step
What does step E3 do in Euclid's Algorithm, and why does it guarantee progress toward termination?
Invariant
What mathematical identity ensures correctness at each step of Algorithm E?
Trace
Trace Algorithm E on inputs $m = 544, n = 119$. What is the result?
When to Use
When would you reach for Euclid's Algorithm over alternative approaches?
Complexity
What is the time complexity of Euclid's Algorithm?