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 1.
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
".2
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
.2
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
.3
The Well-Ordering Principle
Any non-empty set of positive integers contains a smallest number.3
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. 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.
Procedure
Let p
and q
be integers with p ≥ q ≥
0
.
(For q < p
, swap the numbers.)
- If
q = 0
, then terminate with the resultgcd(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 currentp
byq
.
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, r0) = … = gcd(rnā2, rnā1) =
gcd(rn-1, rn)
,
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 × 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,
with p ≥ q > r0 > r1 > … > rn-1 > rn =
0
.
We can come to a similar conclusion (but considering the procedure backward) by proving and applying the following lemma.
Lemma 3
If rn-1
is the last non-zero remainder
received by the Euclidean algorithm procedure applied to non-negative p
and
q
, then rn-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
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 m
.
Observe that
rn-3 = rn-1 × mn × mn-1 +
rn-1
= rn-1 × (mn ×
mn-1 + 1)
.
Hence, by the definition of divisibility,
rn-1|rn-2
and
rn-1|rn-3
.
By an analogous argument, it follows that rn-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 rn
is the zero remainder, guaranteed to
be computed by the termination claim):
Footnotes:
Epp, S. S. (2019). Discrete Mathematics with Applications (5th ed.). Cengage Learning.
Lady, E. L. (2000). Article The Division Algorithm.