The Euclidean Algorithm

In this post, we discuss the Euclidean algorithm, which is an algorithm to find the greatest comment divisor of two integers. This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

Introduction

Computing the greatest common divisor of two integers is a topic that is taught in elementary school and is also an important tool that is of great interest in number theory. We begin with an example.

Let’s take a simple example of finding the greatest common divisor of 24 and 60. In a math class in elementary school, one motivation of finding the greatest common divisor of 24 and 60 is to reduce the fraction $\displaystyle \frac{24}{60}$ to its lowest terms. The first step is to factor each of the numerator and denominator using their prime factors.

$\displaystyle \frac{24}{60}=\frac{2 \cdot 2 \cdot 2 \cdot 3}{2 \cdot 2 \cdot 3 \cdot 5}$

Then cross out the prime factors common to the numerator and the denominator.

$\displaystyle \frac{24}{60}=\frac{\not 2 \cdot \not 2 \cdot 2 \cdot \not 3}{\not 2 \cdot \not 2 \cdot \not 3 \cdot 5}=\frac{2}{5}$

The product of the prime factors that are crossed out is $2 \cdot 2 \cdot 3=12$, which is the greatest common divisor of 24 and 60.

Thus the greatest common divisor of two integers $a$ and $b$ is the product of the prime factors shared by the two numbers. This approach of finding the greatest common divisor depends on performing prime factorization, which is a hard problem for larger numbers. This approach, though conceptually clear, is clearly not efficient.

We need an algorithm for finding the greatest common divisor that does not require prime factorization. First, we have another discussion on the greatest common divisor.

___________________________________________________________________________________________________________________

The Greatest Common Divisor

Let $a$ and $b$ be integers. We say that $a$ divides $b$ (denoted by $a \ \lvert \ b$) if there is an integer $q$ such that $b=q \cdot a$. In other words, $a \ \lvert \ b$ if $a$ divides $b$ without leaving a remainder. For examples, $3 \ \lvert \ 18$ and $7 \ \lvert \ 91$. When $a$ does not divide $b$, we write $a \not \lvert \ b$.

The greatest common divisor (or GCD) of two integers $a$ and $b$ is denoted by $\text{GCD}(a,b)$ and is the largest positive integer that divides both $a$ and $b$. It is clear that $\text{GCD}(a,b)$ is the positive integer $d$ such that

• $d \lvert a$ and $d \lvert b$.
• If $c \lvert a$ and $c \lvert b$, then $c \le d$.

The greatest common integer $\text{GCD}(a,b)$ is always uniquely defined. Each integer has only finitely many integer divisors. So there are only finitely many divisors common to both $a$ and $b$ (the integer 1 is one of them). Any finite set of real numbers has a unique largest element. Thus among all the common divisors of $a$ and $b$, there is the largest one, which we denote by $\text{GCD}(a,b)$. Consequently, $\text{GCD}(a,b) \ge 1$.

We can observe that the greatest common integer $\text{GCD}(a,b)$ defined in this section is identical to the product of the prime factors shared by the two integers $a$ and $b$.

To perform the Euclidean algorithm, we need the division algorithm and the following lemma.

Division Algorithm
Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r .

Lemma 1
Let $a$ and $b$ be positive integers. If $a=q \cdot b+r$, then $\text{GCD}(a,b)=\text{GCD}(b,r)$.

For the discussion in this post, Lemma 1 is used in conjunction with the division algorithm. So we put Lemma 1 in words in the context of applying the division algorithm as follows.

Lemma 1. When $a$ is divided by $b$, the GCD of $a$ and $b$ is the same as the GCD of the $b$ (the divisor) and the $r$ (the remainder).

Proof of Lemma 1

Suppose that $a=q \cdot b+r$. Let $h=\text{GCD}(a,b)$ and $k=\text{GCD}(b,r)$.

We first show that $h \le k$. Since $a=q \cdot b+r$ and since $h \ \lvert \ a$ and $h \ \lvert \ b$, we have $h \ \lvert \ r$. Since $h$ is a common divisor of $b$ and $r$, $h \le k$.

Now we show $k \le h$. Since $a=q \cdot b+r$, it follows that $k$ is a common divisor of $a$ and $b$. Thus $k \le h$. $\blacksquare$

___________________________________________________________________________________________________________________

Example for the Euclidean Algorithm

Before defining the Euclidean algorithm, let’s look at an example. Find the greatest common divisor of $1638$ and $357$.

The Euclidean algorithm can be implemented using subtraction or division.

In the subtraction implementation, the Euclidean algorithm starts with a pair of positive integers and forms a new pair that consists of the smaller integer and the difference between the larger and smaller integers. The process repeats until the two integers are equal. That number then is the greatest common divisor of the original pair.

The following series of subtractions derives the GCD of $1638$ and $357$.

$\displaystyle (1) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&1281&\text{ }&357 \\ 3&\text{ }&924&\text{ }&357 \\ 4&\text{ }&567&\text{ }&357 \\ 5&\text{ }&210&\text{ }&357 \\ 6&\text{ }&210&\text{ }&147 \\ 7&\text{ }&63&\text{ }&147 \\ 8&\text{ }&63&\text{ }&84 \\ 9&\text{ }&63&\text{ }&21 \\ 10&\text{ }&42&\text{ }&21 \\ 11&\text{ }&21&\text{ }&21 \end{bmatrix}$

In the above table, to go from one row to the next, the larger number is reduced by the smaller number. The process stops when the two numbers are equal. In this example, the greatest common divisor is $21$.

Note that the above subtraction process can be speeded up by doing division instead. For example, in the above table, you can jump from row 1 to row 5 by applying the division algorithm. The following is the same example using the division implementation.

$\displaystyle (2) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&210&\text{ }&357 \\ 3&\text{ }&210&\text{ }&147 \\ 4&\text{ }&63&\text{ }&147 \\ 5&\text{ }&63&\text{ }&21 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

To go from row 1 to row 2, divide $1638$ by $357$ to obtain the remainder $210$. To go from row 2 to row 3, divide the larger number $357$ by $210$ to obtain the remainder $147$. Repeat the process until one of reaching the remainder of zero. Then the other number in the last row is the greatest common divisor. The following is the same algorithm with the divisions added.

$\displaystyle (3) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2}&\text{ }&\text{Division} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357&\text{ }&1638=4 \cdot 357+210 \\ 2&\text{ }&210&\text{ }&357&\text{ }&357=1 \cdot 210+147 \\ 3&\text{ }&210&\text{ }&147&\text{ }&210=1 \cdot 147+63 \\ 4&\text{ }&63&\text{ }&147&\text{ }&147=2 \cdot 63+21 \\ 5&\text{ }&63&\text{ }&21&\text{ }&63=3 \cdot 21+0 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

As shown in the example, the Euclidean algorithm only requires subtractions or divisions and no prime factorization. Note that Lemma 1 is used throughout the two tables. Let’s look at table (3). Because the GCD of two numbers is the same as the divisor and the remainder (Lemma 1), the GCD of any row is identical to the GCD of the row below.

___________________________________________________________________________________________________________________

The Euclidean Algorithm

In the remainder of the post, we only discuss the division implementation of the Euclidean algorithm. The following is the description of the Euclidean algorithm.

Euclidean Algorithm

Let $a_0$ and $b_0$ be positive integers. Assume $b_0. Start with the pair $(a_0,b_0)$ and forms a new pair that consists of the smaller number and the remainder derived from dividing the larger number by the smaller. The process stops when reaching a remainder of zero. Then the other number in the last pair is the GCD of $a_0$ and $b_0$.

To describe using some notations, we have the following divisions.

$a_0=q_0 \cdot b_0+r_0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_0

$b_0=q_1 \cdot r_0+r_1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_1

$r_0=q_0 \cdot r_1+r_2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_2

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$r_k=q_k \cdot r_{k+1}+r_{k+2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_{k+2}

The above series of divisions will stop at some $k=j$ where the remainder $r_{j+2}=0$. We have $r_j=q_j \cdot r_{j+1}$ where $r_{j+1}$ is the GCD of the original pair $(a_0,b_0)$.

Proof of Euclidean Algorithm
In the above notation, the sequence of non-negative numbers $b_0>r_0>r_1>r_2>\cdots$ must stop at some point. Eventually $r_{j+2}=0$ for some $j$. We have $r_j=q_j \cdot r_{j+1}+0$. Then $\text{GCD}(r_j,r_{j+1})=\text{GCD}(r_{j+1},0)=r_{j+1}$.

Applying Lemma 1 repeatedly, we have:

\displaystyle \begin{aligned} r_{j+1}&=\text{GCD}(r_{j+1},0) \\&=\text{GCD}(r_j,r_{j+1}) \\&\cdots \\&\cdots \\&\cdots \\&=\text{GCD}(r_1,r_{2}) \\&=\text{GCD}(r_0,r_{1}) \\&=\text{GCD}(b_0,r_{0}) \\&=\text{GCD}(a_0,b_{0}) \end{aligned}

Comment. Note that the statement of the Euclidean algorithm starts with a pair of positive integers $(a_0,b_0)$. If either number is negative, we can take the absolute value of the numbers and the resulting GCD is the same as the original pair. This follows from the following fact.

$\text{GCD}(a,b)=\text{GCD}(-a,b)=\text{GCD}(a,-b)=\text{GCD}(-a,-b)$

___________________________________________________________________________________________________________________

The Extended Euclidean Algorithm

Another good use of the Euclidean algorithm is to find integer solutions to the linear equation $ax+by=d$ where $d=\text{GCD}(a,b)$. This is called the extended Euclidean algorithm. We state it in the following lemma.

Lemma 2 (The Extended Euclidean Algorithm)
Let $a$ and $b$ be integers. Let $d=\text{GCD}(a,b)$. Then there are integers $x$ and $y$ that satisfies the equation $ax+by=d$.

Proving Lemma 2 is a matter of working the Euclidean algorithm backward. We demonstrate the idea using our example of $a=1638$ and $b=357$. The following shows the divisions used in Table (3) above.

$1638=4 \cdot 357+210$
$357=1 \cdot 210+147$
$210=1 \cdot 147+63$
$147=2 \cdot 63+21$
$63=3 \cdot 21+0$

We start off with the second to the last division and work backward.

\displaystyle \begin{aligned} 21&=147-2 \cdot 63 \\&=147 - 2 \cdot (210-147) \\&=3 \cdot 147-2 \cdot 210 \\&=3 \cdot (357-210)-2 \cdot 210 \\&=3 \cdot 357 -5 \cdot 210 \\&=3 \cdot 357- 5 \cdot (1638- 4 \cdot 357) \\&=(-5) \cdot 1638+23 \cdot 357 \end{aligned}

The equation $1638x+357y=21$ has solution $x=-5$ and $y=23$.

As an application to the extended Euclidean algorithm, we have the following corollary.

Corollary 3
Let $a$ and $b$ be integers. Let $h=\text{GCD}(a,b)$. Then if $k$ is a common divisor of $a$ and $b$, then $k$ is a divisor of $h$.

Proof of Corollary
According to Lemma 2, there are integers $x$ and $y$ such that $ax+by=h$. Note that $k$ divides each term on the left-hand side of this equation. So $k$ divides $h$ as well. $\blacksquare$
___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$