Euclid's Algorithm (Algorithm E, §1.1)

Table of contents

Visual Intuition

The idea behind Euclid’s algorithm is simple: if you want the GCD of two numbers, you can repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero remainder is the GCD.

Here is Algorithm E applied to $m = 119$ and $n = 544$:

The left side shows the computation trace for $\gcd(544, 119)$. The right side shows the algorithm’s flow: divide, check if the remainder is zero, and loop until it is.

Knuth’s Formulation

Knuth defines Algorithm E with three steps:

E1. [Find remainder.] Divide $m$ by $n$ and let $r$ be the remainder. (We will have $0 \leq r < n$.)

E2. [Is it zero?] If $r = 0$, the algorithm terminates; $n$ is the answer.

E3. [Reduce.] Set $m \leftarrow n$, $n \leftarrow r$, and go back to step E1.

In mathematical notation, this computes:

by repeatedly applying the identity until the second argument reaches zero.

The correctness relies on a key property: 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)$.

Relation to algorithm definition

Knuth maps Euclid’s algorithm onto this framework explicitly. For $\gcd(m, n)$:

• $Q$ = all pairs of non-negative integers plus intermediate states
• $I$ = pairs $(m, n)$ with $m, n > 0$
• $\Omega$ = states where the remainder is zero (the answer is ready)
• $f$ = one step of “divide, check remainder, reduce”

Complexity and Notes

Time complexity: $O(\log(\min(m, n)))$ — Gabriel Lame 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.