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 1.
The Euclidean algorithm is a method for computing the greatest common divisor of two non-negative integers.
First of all, let's uncover the meaning hidden under the complex-looking term greatest common divisor (GCD).
- 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.
- 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.
- It means the largest of the common divisors is being identified.
The considerations presented in the next sections of this text are based on the following definitions:
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 "
The Greatest Common Divisor (GCD)
Given two integers
b that are not both zero, the greatest common
b — denoted as
gcd(a, b) — is the largest integer
The Quotient-Remainder Theorem (Division Algorithm)
Given any integer
a and positive integer
b, there exist unique integers
r such that
a = bq + r and
0 ≤ r <
The Well-Ordering Principle
Any non-empty set of positive integers contains a smallest number.3
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. 4
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.
q be integers with
p ≥ q ≥
q < p, swap the numbers.)
q = 0, then terminate with the result
gcd(p, q) = p.
- Adjust the numbers to process:
gcd(p, q) = gcd(q, p mod q).
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.
By the definition of the greatest common divisor,
gcd(p, q) denotes an integer
that divides (equally, without leaving a remainder) some integers
And the Euclidean algorithm is a procedure that finds it, by verifying such
candidate divisors one by one, in descending order.
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.
For any positive integer
gcd(a, 0) = a
0 = a × 0, and
a = a
× 1, then
a|a. And since
a > 0, then, by the
definition of GCD,
gcd(a, 0) = a.
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
- The second number
- is the remainder that will verify the next GCD
candidate. This remainder is a result of the
modoperation: a "leftover" after an attempt to equally divide the current
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.
p = qm + r, for integers
r, such that
q > r ≥ 0, then
gcd(p, q) = gcd(q,
r are integers with
p ≥ q > r ≥
d is an arbitrary common divisor of the pair
Then, by the definition of divisibility,
p = da
q = dc for some integers
r = p - qm by
= da - dcm by
= d(a - cm) by
for some integer
It follows that
d also divides
d is a common divisor of the pair
(q, r) too.
d' is an arbitrary common divisor of the pair
(q, r). Let
c' be arbitrary integers, then
q = d'a' and
r = d'c'.
p = qm' + r by
= d'a'm' + d'c'
= d'(a'm' + c')
by factoring out
for a positive integer
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, r0) = … = gcd(rn−2, rn−1) =
n is a number of performed divisions.
p = q × m0 + r0
q = r0 × m1 + r1
r0 = r1 × m2 + r2
r1 = r2 × m3 + r3
rn-3 = rn-2 × mn-1 + rn-1
rn-2 = rn-1 × mn + rn,
p ≥ q > r0 > r1 > … > rn-1 > rn =
We can come to a similar conclusion (but considering the procedure backward) by proving and applying the following lemma.
rn-1 is the last non-zero remainder
received by the Euclidean algorithm procedure applied to non-negative
rn-1 divides both
n is a number of the performed Euclidean algorithm divisions and
is a remainder computed by these divisions. Let
rn equal zero and
rn-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
rn-3 = rn-2 × mn-1 + rn-1 ,
rn-2 = rn-1 × mn
for some integer
rn-3 = rn-1 × mn × mn-1 +
= rn-1 × (mn ×
mn-1 + 1).
Hence, by the definition of divisibility,
By an analogous argument, it follows that
divides all the preceding remainders and the initial input
And now we're getting to the final proof in this post.
The Euclidean algorithm computes the greatest common divisor of any pair of
q are arbitrary non-negative integers. Suppose
r is the last
non-zero remainder computed by the Euclidean algorithm. Then, by Lemma 3,
a common divisor of both
q. And since, by the termination claim,
is the largest integer in a set of possible common divisors of
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
rn is the zero remainder, guaranteed to
be computed by the termination claim):