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.
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 to its lowest terms. The first step is to factor each of the numerator and denominator using their prime factors.
Then cross out the prime factors common to the numerator and the denominator.
The product of the prime factors that are crossed out is , which is the greatest common divisor of 24 and 60.
Thus the greatest common divisor of two integers and 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 and be integers. We say that divides (denoted by ) if there is an integer such that . In other words, if divides without leaving a remainder. For examples, and . When does not divide , we write .
The greatest common divisor (or GCD) of two integers and is denoted by and is the largest positive integer that divides both and . It is clear that is the positive integer such that
- and .
- If and , then .
The greatest common integer is always uniquely defined. Each integer has only finitely many integer divisors. So there are only finitely many divisors common to both and (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 and , there is the largest one, which we denote by . Consequently, .
We can observe that the greatest common integer defined in this section is identical to the product of the prime factors shared by the two integers and .
To perform the Euclidean algorithm, we need the division algorithm and the following lemma.
Let and be positive integers. Then there exist unique integers and such that
Let and be positive integers. If , then .
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 is divided by , the GCD of and is the same as the GCD of the (the divisor) and the (the remainder).
Proof of Lemma 1
Suppose that . Let and .
We first show that . Since and since and , we have . Since is a common divisor of and , .
Now we show . Since , it follows that is a common divisor of and . Thus .
Example for the Euclidean Algorithm
Before defining the Euclidean algorithm, let’s look at an example. Find the greatest common divisor of and .
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 and .
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 .
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.
To go from row 1 to row 2, divide by to obtain the remainder . To go from row 2 to row 3, divide the larger number by to obtain the remainder . 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.
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.
Let and be positive integers. Assume . Start with the pair 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 and .
To describe using some notations, we have the following divisions.
The above series of divisions will stop at some where the remainder . We have where is the GCD of the original pair .
Proof of Euclidean Algorithm
In the above notation, the sequence of non-negative numbers must stop at some point. Eventually for some . We have . Then .
Applying Lemma 1 repeatedly, we have:
Comment. Note that the statement of the Euclidean algorithm starts with a pair of positive integers . 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.
The Extended Euclidean Algorithm
Another good use of the Euclidean algorithm is to find integer solutions to the linear equation where . This is called the extended Euclidean algorithm. We state it in the following lemma.
Lemma 2 (The Extended Euclidean Algorithm)
Let and be integers. Let . Then there are integers and that satisfies the equation .
Proving Lemma 2 is a matter of working the Euclidean algorithm backward. We demonstrate the idea using our example of and . The following shows the divisions used in Table (3) above.
We start off with the second to the last division and work backward.
The equation has solution and .
As an application to the extended Euclidean algorithm, we have the following corollary.
Let and be integers. Let . Then if is a common divisor of and , then is a divisor of .
Proof of Corollary
According to Lemma 2, there are integers and such that . Note that divides each term on the left-hand side of this equation. So divides as well.