# 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 algorithmis a method for computing thegreatest common divisorof 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 algorithmis 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 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`

,
_{0}) = … = 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
```

_{0} + r_{0}

q = r_{0} × m_{1} + r_{1}

r_{0} = r_{1} × m_{2} + r_{2}

r_{1} = r_{2} × m_{3} + r_{3}

ā

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`

.
_{0} > r_{1} > … > 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`

is the last non-zero remainder
received by the Euclidean algorithm procedure applied to non-negative _{n-1}`p`

and
`q`

, then `r`

divides both _{n-1}`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`

equal zero and
_{n}`r`

be the last non-zero remainder. Then, by
Lemma 2, the final rounds of the Euclidean algorithm execution can be
represented by the equations
_{n-1}

`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`

and
_{n-1}|r_{n-2}`r`

.
_{n-1}|r_{n-3}

By an analogous argument, it follows that `r`

divides all the preceding remainders and the initial input _{n-1}`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`

is the zero remainder, guaranteed to
be computed by the termination claim):
_{n}

## Footnotes:

^{2}

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

^{3}

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