The Euclidean Algorithm

This post aims to lay out the foundational basics needed for an understanding of the Euclidean algorithm's inner workings. The text contains a mix of formal and informal narration. It was attempted to make the contents clear for a reader with any level of knowledge in mathematics ✨ 📜 📚 ✨.

We get started with a concise definition of the Euclidean algorithm ¹.

The Euclidean algorithm is a method for computing the greatest common divisor of two non-negative integers.

The Greatest Common Divisor (GCD)

First of all, let's uncover the meaning hidden under the complex-looking term greatest common divisor (GCD).

Divisor: This is a name of some value that divides (can split) another value into equal parts. By value, we mean anything measurable, such as integers, lengths, items, etc.
Common: This term implies that a division into equal parts of more than one value is considered. In other words, we are looking for a value that can serve as a divisor for several different values.
Greatest: It means the largest of the common divisors is being identified.

Four Formal Definitions

The considerations presented in the next sections of this text are based on the following definitions:

Divisibility

If a and b are integers, then a is divisible by b if there is an integer c such that a = bc and b ≠ 0. The notation b|a is read "b divides a".²

The Greatest Common Divisor (GCD)

Given two integers a and b that are not both zero, the greatest common divisor of a and b — denoted as gcd(a, b) — is the largest integer d such that d|a and d|b.²

The Quotient-Remainder Theorem (Division Algorithm)

Given any integer a and positive integer b, there exist unique integers q and r such that a = bq + r and 0 ≤ r < b.³

The Well-Ordering Principle

Any non-empty set of positive integers contains a smallest number.³

The Euclidean Algorithm

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. ⁴

This quote correctly describes the essence of the algorithm, but still, it may not "sink in" for everyone right away. That's why in the following text we elaborate more on the topic. Sooner or later, after reading and comprehending different descriptions of the algorithm, it will become clearer.

Procedure

Let p and q be integers with p ≥ q ≥ 0.
(For q < p, swap the numbers.)

If: q = 0, then terminate with the result gcd(p, q) = p.
Else: Adjust the numbers to process:
gcd(p, q) = gcd(q, p mod q).

Termination Claim

Observe that the processed numbers are getting smaller at each round of the algorithm execution. (mod returns a remainder of the division.) Since the remainders are non-negative integers by definition, then the least possible remainder is zero. Therefore, by the well-ordering principle for natural numbers, the algorithm is guaranteed to terminate after a finite number of steps, reaching a zero remainder.

Putting it differently (so to speak, procedurally), it is guaranteed that at some moment the remainder p mod q will equal to zero; then the If condition will return true; and then the algorithm will terminate with the found GCD.

Comprehending the Procedure

By the definition of the greatest common divisor, gcd(p, q) denotes an integer that divides (equally, without leaving a remainder) some integers p and q. And the Euclidean algorithm is a procedure that finds it, by verifying such candidate divisors one by one, in descending order.

Stage 1

The algorithm starts with a check whether one of the given integers equals zero. If it is so, then GCD equals the other, non-zero, integer value.

Lemma 1

For any positive integer a, gcd(a, 0) = a

Proof

Since 0 = a × 0, and a = a × 1, then a|0 and a|a. And since a > 0, then, by the definition of GCD, gcd(a, 0) = a.

Stage 2

Otherwise, the algorithm prepares the subsequent pair of numbers to be processed again as described above, at Stage 1.

In the new pair:

The first number: is the next GCD candidate, it equals the current value of q.
The second number: is the remainder that will verify the next GCD candidate. This remainder is a result of the mod operation: a "leftover" after an attempt to equally divide the current p by q.

In other words

The Euclidean algorithm performs a division on each run of Stage 2. During the algorithm's life-cycle, it works only with the initially given values and the remainders of the divisions. (In our imagination, all these values can be seen as one "family" with two parents and remainders-children.)
With each division, remainders become smaller and smaller, until a zero remainder is found. Such zero remainder is the only marker that an equal division is finally made.
The last non-zero remainder — the division by which eventually results in the equally divided parts — is the greatest common divisor. It divides the whole "family" of the given and computed values into equal parts and it is the first found common divisor (checking possible ones in descending order) and thus the greatest.

Math Help Us

Lemma 2

If p = qm + r, for integers p, q, m, r, such that p ≥ q > r ≥ 0, then gcd(p, q) = gcd(q, r).

Proof

Assume p, q, r are integers with p ≥ q > r ≥ 0.

Now suppose d is an arbitrary common divisor of the pair (p, q).

Then, by the definition of divisibility, p = da and q = dc for some integers a and c.

Thus,

r = p - qm by quotient-remainder theorem

= da - dcm by substitution

= d(a - cm) by factoring out d,

for some integer m.

It follows that d also divides r, hence d is a common divisor of the pair (q, r) too.

Now suppose d' is an arbitrary common divisor of the pair (q, r). Let a' and c' be arbitrary integers, then q = d'a' and r = d'c'.

Hence,

p = qm' + r by quotient-remainder theorem

= d'a'm' + d'c' by substitution

= d'(a'm' + c') by factoring out d',

for a positive integer m'.

It follows that d' is a common divisor of the other pair (p, q) too.

Since common divisors of the pairs (p, q) and (q, r) are in the same set of integers, then the greatest common divisors of (p, q) and (q, r) are equal.

By an analogous argument, we can show that the GCD of the initially given integers equals the GCD of each succeeding pair of the integers received by the Euclidean algorithm division. Namely,

gcd(p, q) = gcd(q, r₀) = … = gcd(r_n−2, r_n−1) = gcd(r_n-1, r_n),

where n is a number of performed divisions.

It follows, by applying quotient-remainder theorem and termination claim, that the Euclidean algorithm procedure can be represented by the sequence of equations:

p = q × m₀ + r₀ q = r₀ × m₁ + r₁ r₀ = r₁ × m₂ + r₂ r₁ = r₂ × m₃ + r₃ ⁞ r_n-3 = r_n-2 × m_n-1 + r_n-1 r_n-2 = r_n-1 × m_n + r_n,

with p ≥ q > r₀ > r₁ > … > r_n-1 > r_n = 0.

We can come to a similar conclusion (but considering the procedure backward) by proving and applying the following lemma.

Lemma 3

If r_n-1 is the last non-zero remainder received by the Euclidean algorithm procedure applied to non-negative p and q, then r_n-1 divides both p and q.

Proof

Suppose n is a number of the performed Euclidean algorithm divisions and r is a remainder computed by these divisions. Let r_n equal zero and r_n-1 be the last non-zero remainder. Then, by Lemma 2, the final rounds of the Euclidean algorithm execution can be represented by the equations

r_n-3 = r_n-2 × m_n-1 + r_n-1 r_n-2 = r_n-1 × m_n,

for some integer m.

Observe that

r_n-3 = r_n-1 × m_n × m_n-1 + r_n-1

= r_n-1 × (m_n × m_n-1 + 1).

Hence, by the definition of divisibility, r_n-1|r_n-2 and r_n-1|r_n-3.

By an analogous argument, it follows that r_n-1 divides all the preceding remainders and the initial input p and q.

And now we're getting to the final proof in this post.

The Euclidean algorithm computes the greatest common divisor of any pair of non-negative integers p and q.

Proof

Assume p and q are arbitrary non-negative integers. Suppose r is the last non-zero remainder computed by the Euclidean algorithm. Then, by Lemma 3, r is a common divisor of both p and q. And since, by the termination claim, r is the largest integer in a set of possible common divisors of p and q, then gcd(p, q) = r.

Quite interestingly, based on all the considerations given above, now we can illustrate the essence of the Euclidean algorithm procedure as shown below (assume r_n is the zero remainder, guaranteed to be computed by the termination claim):

gcd(p, q) = gcd(r_n-1, r_n) by Lemma 2 induction

= gcd(r_n-1, 0) by substitution

= r_n-1 by Lemma 1.

Footnotes:

Euclid's Algorithm for the Greatest Common Divisor.

Epp, S. S. (2019). Discrete Mathematics with Applications (5th ed.). Cengage Learning.

Lady, E. L. (2000). Article The Division Algorithm.

⁴

Wikipedia: Euclidean algorithm.