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 <b.

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

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

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

        \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

        \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

        \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

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

    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}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s