Number Theory Primer : The Euclidean Algorithm

authored by Premmi and Beguène

Previous Topic : The Greatest Common Divisor

Introduction

We have already seen a situation that necessitated the calculation of the greatest common divisor of two integers. We calculated the greatest common divisor of the two integers by listing all their positive divisors and choosing the largest one common to each. This method of calculation becomes cumbersome for large numbers. The Euclidean Algorithm, as we shall see shortly, through repeated application of the Division Algorithm provides a more efficient process to calculate the greatest common divisor of two integers.

Intuition

Suppose we want to find the greatest common divisor of 36 and 24 i.e., gcd(36, 24). One way to do this is to list the positive divisors of 36 and 24 and choose the largest divisor common to both as shown below.

The positive divisors of each of 36 \text{ and } 24 are listed below.

\begin{equation*} 
\begin{split}
\text{Positive divisors of } 36 &: 1, 2, 3, 4, 6, 9, 12, 18, 36 \\
\text{Positive divisors of } 24 &: 1, 2, 3, 4, 6, 8, 12, 24 \\
\end{split}
\end{equation*}

We can see that 12 is the greatest common divisor of both 36 \text{ and } 24. Hence, gcd(36, 24) = 12.

Now suppose we have to find the greatest common divisor of 9 and 6 i.e., gcd(9, 6).

The positive divisors of each of 9 \text{ and } 6 are listed below.

\begin{equation*} 
\begin{split}
\text{Positive divisors of } 9 &: 1, 3, 9 \\
\text{Positive divisors of } 6 &: 1, 2, 3, 6 \\
\end{split}
\end{equation*}

We can see that this list of positive divisors for 9 \text{ and } 6 is smaller than the corresponding list for 36 \text{ and } 24.

Similarly, if we are asked to find the greatest common divisor of 12480 \text{ and } 4032, the list of positive divisors of both these numbers will be long and cumbersome to make.

To summarize, since larger numbers have more number of potential divisors than smaller numbers this method of finding all the positive divisors of both the numbers and choosing the largest one common to both might be infeasible when large numbers are involved.

So how do we circumvent this problem? What if we could reduce the problem of finding the greatest common divisor of large numbers to an equivalent albeit easier problem of finding the greatest common divisor of small numbers which is easier to calculate?

We will now explore this method in detail.

Suppose we have to find gcd(36, 24). Let us assume that d = \text{gcd}(36, 24). Since by definition, d \,|\,36 \text{ and } d \,|\,24, part (g) of the Theorem we have already proved allows us to conclude that d divides any linear combination of 36 \text{ and } 24.

By applying the Division Algorithm to 36 \text{ and } 24 we get,

36 = 1 \times 24 + 12

which can be rewritten as

36 - 1 \times 24 = 12

Since d divides any linear combination of 36 \text{ and } 24, d divides 36 - 1 \times 24 i.e., d \,|\, 12. Therefore, d is also the positive common divisor of 24 \text{ and } 12.

Now if c is some arbitrary positive common divisor of 24 \text{ and } 12, then part (g) of the Theorem we have already proved allows us to conclude that c divides any linear combination of 24 \text{ and } 12 i.e., c \,|\, (1 \times 24 + 1 \times 12). Therefore, c divides 36. That is, c is also the positive common divisor of both 36 \text{ and } 24. Since d is the greatest common divisor of 36 \text{ and } 24, it follows that c \leq d. Therefore, d is the greatest common divisor of 24 \text{ and } 12, i.e., \text{gcd}(24, 12) = d.

By similar reasoning, applying the Division Algorithm to 24 \text{ and } 12 we get,

24 = 2 \times 12 + 0

Therefore, d is the greatest common divisor of 12 \text{ and } 0, i.e., \text{gcd}(12, 0) = d.

Hence, gcd(36, 24) = \text{gcd}(24, 12) = \text{gcd}(12, 0) = d = 12.

We have reduced the problem of finding the greatest common divisor of 36 \text{ and } 24 to an equivalent and much easier problem of find the greatest common divisor of 12 \text{ and } 0 i.e., \text{gcd}(36, 24) = \text{gcd}(12, 0).

It should be noted that a zero remainder must eventually appear at some point because the repeated application of the Division Algorithm results in a decreasing sequence of remainders that cannot contain more than 24 integers since we started the division with 24.

To recap, as shown below, to find the greatest common divisor of two integers, namely, 36 \text{ and }24, we repeatedly apply the Division Algorithm till a zero remainder appears and then choose the last nonzero remainder that appears in these equations, namely, the integer 12, as the greatest common divisor of 36 \text{ and }24. This method is much easier than finding all the divisors of 36 \text{ and }24 and choosing the largest divisor common to both.

\begin{equation*} 
\begin{split}
36 &= 1 \times 24 + 12 \\
24 &= 2 \times 12 + 0 \\
\end{split}
\end{equation*} 

This method of finding the greatest common divisor of two integers by repeated application of the Division Algorithm till a zero remainder appears is called the Euclidean Algorithm.

In order to fully appreciate the Euclidean Algorithm let us use it to calculate the greatest common divisor of two large integers, namely, 12480 \text{ and } 4032.

\begin{equation*} 
\begin{split}
12480 &= 3 \times 4032 + 384 \\
4032 &= 10 \times 384 + 192 \\
384 &= 2 \times 192 + 0\\
\end{split}
\end{equation*}

Working down the displayed system of equations, we obtain

\text{gcd}(12480, 4032) = \text{gcd}(4032, 384) = \text{gcd}(384, 192) = \text{gcd}(192, 0) = 192

since

\begin{equation*} 
\begin{split}
\text{gcd}(12480, 4032) &= \text{gcd}(3 \times 4032 + 384, 4032) = \text{gcd}(4032, 384), \\
\text{gcd}(4032, 384) &= \text{gcd}(10 \times 384 + 192, 384) = \text{gcd}(384, 192) \,\& \\
\text{gcd}(384, 192) &= \text{gcd}(2 \times 192 + 0, 192) = \text{gcd}(192, 0) \\

\end{split}
\end{equation*}

We can see that with just three applications of the Division Algorithm we were able to calculate the greatest common divisor of 12480 \text{ and } 4032. This calculation would have been very cumbersome if we had to list each of their divisors and then pick the largest divisor common to both.

We have already seen that the greatest common divisor of two integers can be expressed as a linear combination of the two integers i.e., given integers a \text{ and } b not both zero, there exist integers x \text{ and } y such that gcd(a, b) = ax + by. We did not provide a practical method to find x \text{ and } y which we will remedy now.

In order to represent 192 as a linear combination of the integers 12480 \text{ and } 4032, we will use the equations displayed above as follows.

From the last but one equation, we get

192 = 4032 - 10 \times 384

From the first equation, we get

384 = 12480 - 3 \times 4032

Combining the above two equations we get,

\begin{equation*} 
\begin{split}
192 &= 4032 - 10 \times (12480 - 3 \times 4032) \\
&= (-10) \times 12480 + 31 \times 4032 \\
\end{split}
\end{equation*}

Therefore,

192 = \text{gcd}(12480, 4032) = 12480 x + 4032y

where x = -10 \text{ and } y = 31. It should be noted that this is not the only way to express 192 as a linear combination of the integers 12480 \text{ and } 4032; among other possibilities, we could add and subtract 12480 \cdot 4032 to get

\begin{equation*} 
\begin{split}
192 &= (-10 + 4032) \times 12480 + (31 - 12480) \times 4032 \\
&= 4022 \times 12480 + (-12449) \times 4032 \\
\end{split}
\end{equation*}

From our discussion thus far we have seen that in order to calculate the greatest common divisor of two integers using the Euclidean Algorithm we repeatedly apply the Division Algorithm till a zero remainder appears. This implies that the most efficient way to calculate the greatest common divisor of two integers using the Euclidean Algorithm is to make the zero remainder emerge with as few applications of the Division Algorithm as possible.

We will illustrate this point using an example. Suppose we have to find the greatest common divisor of 24 \text{ and } 14. We have shown two ways of doing this. In the first way as we can see the remainders are all positive integers, while in the second the remainders are positive as well as negative. We can see that the second way leads to fewer steps and hence is more efficient.

\begin{equation*} 
\begin{split}
24 &= 1 \times 14 + 10 \\
14 &= 1 \times 10 + 4 \\
10 &= 2 \times 4 + 2 \\
4 &= 2 \times 2 + 0\\
\end{split}
\end{equation*}

\begin{equation*} 
\begin{split}
24 &= 2 \times 14 - 4 \\
14 &= 3 \times 4 + 2 \\
4 &= 2 \times 2 + 0\\
\end{split}
\end{equation*}

Lets illustrate this point with an example. Suppose we divide 19 by 10. We can express 19 as

19 = 1 \times 10 + 9 \\

or as

19 = 2 \times 10 - 1

When we divide 19 by 10 we can get any one of the integers between 0 \text{ to } 9 as remainders. In the first case we got a remainder that is greater than \frac{10}{2} = 5 and in the second case we got a remainder that is less than 5. Therefore, we can reduce the number of steps in the Euclidean Algorithm whenever we are able to choose remainders, r, such that |r| < \frac{b}{2}, where b is the divisor. This might not always be possible, especially when |r| = \frac{b}{2}.

As we can see in the second case, this happened when 14 was divided by 4 and resulted in the remainder of 2 which equals \frac{4}{2}. We cannot optimize this particular step for a smaller absolute remainder and consequently, lesser number of subsequent steps in the Euclidean Algorithm since

14 = 3 \times 4 + 2

and

14 = 4 \times 4 - 2

result in the same absolute remainder of 2.

We will now formalize all these observations we have made thus far.

Lemma

If a = bq + r, as in the Division Algorithm, then \text{gcd}(a, b) = \text{gcd}(b, r).

Suppose d = \text{gcd}(a, b). Then it follows from the definition of \text{gcd}(a, b), that d \,|\, a \text{ and } d \,|\, b. Part (g) of the Theorem we have already proved lets us conclude that d divides any linear combination of a \text{ and } b i.e., d \,|\, (a - bq) or equivalently, d \,|\, r. Therefore, d is a positive common divisor of both b \text{ and }r.

On the other hand, if c is an arbitrary common divisor of b \text{ and }r, then part (g) of the Theorem we have already proved lets us conclude that c divides any linear combination of b \text{ and } r i.e., c \,|\, (bq + r) or equivalently, c \,|\, a. Hence, c is a positive common divisor of both a \text{ and }b. Since, \text{gcd}(a, b) = d, it implies that c \leq d.

Therefore, it follows from the definition of \text{gcd}(b, r) that d = \text{gcd}(b, r).

The Euclidean Algorithm

The Euclidean Algorithm may be described as follows:

Let a \text{ and } b be two integers whose greatest common divisor is desired.

We know from the definition of the divisibility of integers that, if a positive integer d divides a, then a = dr, for some integer r. Also we can see that -a = d(-r). That is, if d divides a, then d also divides -a.

Therefore, \text{gcd}(a, b) = \text{gcd}(|a|, |b|) and there is no harm is assuming that a \geq b > 0.

The first step of the Euclidean Algorithm is to apply the Division Algorithm to integers a \text{ and } b to get

a = q_1b + r_1 \quad \quad \quad 0 \leq r_1 < b

If it happens that r_1 = 0, then b \,|\, a and \text{gcd}(a, b) = b.

When r_1 \neq 0, we divide b by r_1 to produce integers q_2 \text{ and } r_2 satisfying

b = q_2r_1 + r_2 \quad \quad \quad 0 \leq r_2 < r_1

If r_2 = 0, then we stop; otherwise, we proceed as before to obtain

r_1 = q_3r_2 + r_3 \quad \quad \quad 0 \leq r_3 < r_2

This division process continues until some zero remainder appears, say, at the (n + 1)th stage where r_{n-1} is divided by r_n; a zero remainder occurs sooner or later because the decreasing sequence b > r_1 > r_2 > \cdots \geq 0 cannot contain more than b integers.

The result is the following system of equations:

\begin{equation*} 
\begin{split}
a &= q_1b + r_1 \quad \quad \quad 0 < r_1 < b\\
b &= q_2r_1 + r_2 \quad \quad \quad 0 < r_2 < r_1\\
r_1 &= q_3r_2 + r_3 \quad \quad \quad 0 < r_3 < r_2\\
&\,\,\,\vdots\\
r_{n-2} &= q_nr_{n-1} + r_n \quad \quad \quad 0 < r_n < r_{n-1}\\
r_{n-1} &= q_{n+1}r_{n} + 0 \\
\end{split}
\end{equation*}

Using the result of the lemma we have proved previously, we simply work down the displayed system of equations, obtaining

\text{gcd}(a, b) = \text{gcd}(b, r_1) = \text{gcd}(r_1, r_2) = \cdots = \text{gcd}(r_{n-1}, r_n) =  \text{gcd}(r_n, 0) = r_n

Expressing gcd(a,b) as a linear combination of a and b

Theorem asserts that \text{gcd}(a, b) can be expressed as a linear combination of a \text{ and } b i.e., in the form ax + by, but the proof of the theorem does not provide a method to determine the integers x \text{ and } y. We will now demonstrate how the Euclidean Algorithm can be used to determine x \text{ and } y.

Starting with the last but one equation arising from the algorithm, we rewrite

r_{n-2} = q_nr_{n-1} + r_n

as

r_n = r_{n-2} - q_nr_{n-1}

Now we solve the preceding (last but second) equation in the algorithm for r_{n-1} and substitute in the above equation to get,

\begin{equation*} 
\begin{split}
r_n &= r_{n-2} - q_n(r_{n-3} - q_{n-1}r_{n-2}) \\
&= (1 + q_nq_{n-1})r_{n-2} + (-q_n)r_{n-3} \\
\end{split} 
\end{equation*}

This represents r_n as a linear combination of r_{n-2} and r_{n-3}. Continuing backward through the system of equations, we successfully eliminate the remainders r_{n-1}, r_{n-2}, \ldots, r_2, r_1 until a stage is reached when r_n = \text{gcd}(a, b) is expressed as a linear combination of a \text{ and } b.

Some interesting observations

The number of steps required in the Euclidean Algorithm is at most five times the number of digits in the smaller integer. This was proved by the French mathematician Gabriel Lamé (1795-1870).

Another observation of interest is that for each n > 0, it is possible to find integers a_n \text{ and } b_n such that exactly n divisions are required to compute \text{gcd}(a_n, b_n) by the Euclidean Algorithm. We shall prove this fact later.

As we have already discussed, the number of steps in the Euclidean Algorithm can be reduced if it is possible to select remainders r_{k+1} such that |r_{k+1}| < \dfrac{r_k}{2}.

An important consequence of Euclidean Algorithm

The following theorem is an important consequence of the Euclidean Algorithm.

Theorem

If k > 0, where k is an integer, \text{gcd}(ka, kb) = k\,\text{gcd}(a, b).

If each of the equations appearing in the Euclidean Algorithm for a \text{ and } b is multiplied by k, we obtain,

\begin{equation*} 
\begin{split}
ak &= q_1(bk) + r_1k \quad \quad \quad 0 < r_1k < bk\\
bk &= q_2(r_1k) + r_2k \quad \quad \quad 0 < r_2k < r_1k\\
r_1k &= q_3(r_2k) + r_3k \quad \quad \quad 0 < r_3k < r_2k\\
&\,\,\,\vdots\\
r_{n-2}k &= q_n(r_{n-1}k) + r_nk \quad \quad \quad 0 < r_nk < r_{n-1}k\\
r_{n-1}k &= q_{n+1}(r_{n}k) + 0 \\
\end{split}
\end{equation*}

But this is clearly the Euclidean Algorithm applied to the integers ak \text{ and } bk, so that their greatest common divisor is the last nonzero remainder r_nk; that is

\text{gcd}(ka, kb) = r_nk = k \, \text{gcd}(a, b)

as stated in the theorem.

An Alternate Proof

The following is an alternate proof of the theorem we have just proved.

From this Theorem we can conclude that \text{gcd}(ak, bk) is the smallest positive integer of the form (ak)x + (bk)y, which, in turn, is equal to k times the smaller positive integer of the form ax + by; this latter value is equal to k \, \text{gcd}(a, b).

Application of the Theorem

By way of illustrating this theorem, we see that

\text{gcd}(36, 24) = 3 \, \text{gcd}(12, 8) = 3 \, \cdot 2\, \text{gcd}(6, 4) = 3 \, \cdot 2\, \cdot 2\, \text{gcd}(3, 2) = 12 \, \cdot 1 = 12

Corollary

For any integer k \neq 0, \text{gcd}(ka, kb) = |\,k\,|\,\text{gcd}(a, b).

It suffices to consider the case in which k < 0. Then -k = |\,k\,| > 0.

Also, we know from the definition of the divisibility of integers that, if a positive integer d divides ak, then ak = dr, for some integer r. Also we can see that -ak = d(-r). That is, if d divides ak, then d also divides -ak.

Therefore,

\begin{equation*} 
\begin{split}
\text{gcd}(ak, bk) &= \text{gcd}(-ak, -bk)\\
&= \text{gcd}(a\,|\,k\,| , b\,|\,k\,| )\\
\end{split}
\end{equation*}

By the theorem we have just proved,

\text{gcd}(a\,|\,k\,| , b\,|\,k\,| ) = |\,k\,|\,\text{gcd}(a, b)

Hence,

\text{gcd}(ak, bk) = |\,k\,|\,\text{gcd}(a, b)

Least Common Multiple

There is a concept parallel to that of the greatest common divisor of two integers, known as their least common multiple. For the sake of completion, we shall explore this concept in detail in this section, though we shall not have much occasion to make use of it.

Intuition

Suppose you are throwing a party for kids. You want to give each kid who attends the party a box of chocolates. You are not certain about the exact number of kids who will turn up for the party. Depending on the number of kids who turn up for the party you would like to give each of them a box containing either 18 \text{ or } 42 pieces of chocolate; if less number of kids turn up each kid will get a box with 42 pieces of chocolates otherwise each kid will get a box with 18 pieces of chocolates.What is the minimum number of pieces of chocolates that needs to be bought such that they can be divided up into boxes of either 18 \text{ or } 42 pieces of chocolates with no chocolates leftover in either case?

Suppose the minimum number of pieces of chocolates that needs to be bought is x. Then x should divide both 18 \text{ and } 42 or equivalently, x is a common multiple of both 18 \text{ and } 42. Since x is the smallest positive integer that is divisible by both 18 \text{ and } 42 or equivalently, the smallest possible positive multiple of both 18 \text{ and } 42 it is called the least common multiple of integers 18 \text{ and } 42.

How do we find x? One way is to list the positive multiples of each of 18 \text{ and } 42 till we get a multiple that is common to both as illustrated below.

\begin{equation*} 
\begin{split}
\text{Positive multiples of } 18 &: 18, 36, 54, 72, 90, 108, 126 \\
\text{Positive multiples of } 42 &: 42, 84, 126 \\
\end{split}
\end{equation*}

We can see that since 126 is common to both the lists, x = 126 is the smallest positive integer that is divisible by both 18 \text{ and } 42. Hence, the minimum number of pieces of chocolates that needs to be bought is 126.

We could also use an alternate and more concise method to find the least common multiple of two integers. Since 42 > 18, the least common multiple of 18 \text{ and } 42 is the smallest positive multiple of 42 that is also a multiple of 18. Therefore, we test each multiple of 42 to see whether it is also a multiple of 18 as shown below.

We test 1 \cdot 42 = 42. Since 18 \nmid 42, 42 is not a common multiple of 18 \text{ and } 42.

Next, we test 2 \cdot 42 = 84. Since 18 \nmid 84, 84 is not a common multiple of 18 \text{ and } 42.

We test 3 \cdot 42 = 126. Since 18 \,|\, 126 and the only two smaller positive multiples of 42 are not multiples of 18, the least common multiple of 18 \text{ and } 42 is 126.

Proof of existence of Least Common Multiple

An integer c is said to be a common multiple of two nonzero integers a \text{ and } b whenever a \,|\, c \text{ and } b \,|\, c.

Evidently, zero is a common multiple of a \text{ and } b. There also exist common multiples that are not trivial because the products ab \text{ and} -\!(ab) are both common multiples of a \text{ and } b, one of which is always positive. Therefore, the set of positive common multiples of a \text{ and } b is nonempty. Consequently, by the Well-Ordering Principle, the set of positive common multiples of a \text{ and } b must contain a smallest integer; we call it the least common multiple of a \text{ and } b.

Definition

The least common multiple of two nonzero integers a \text{ and } b, denoted by \text{lcm}(a, b), is the positive integer m satisfying the following conditions:

(a) a \,|\, m \text{ and } b \,|\, m

(b) For any integer c, if a \,|\, c \text{ and } b \,|\, c, with c > 0, then m \leq c

Example

As an example, the positive common multiple of the integers -9 \text{ and } 30 are 90, 180, 270, \ldots; hence, \text{lcm}(-9, 30) = 90.

Remark

The following remark is clear from our discussion thus far: given nonzero integers a \text{ and } b, \text{lcm}(a, b) always exists and \text{lcm}(a, b) \leq |ab|.

LCM of large integers

We had discussed a method to calculate the least common multiple of two nonzero integers. But does this method scale to large integers?

Now suppose instead of finding the least common multiple of 18 \text{ and } 42 we have to find the least common multiple of 3054 \text{ and } 12378. As we have already discussed, we can test each multiple of 12378 to see whether it is divisible by 3054. The first such multiple we encounter is the least common multiple of 3054 \text{ and } 12378. Let us proceed to find \text{lcm}(3054, 12378) in this way.

We test 1 \cdot 12378 = 12378. Since 3054 \nmid 12378, 12378 is not a common multiple of 3054 \text{ and } 12378.

We test 2 \cdot 12378 = 24756. Since 3054 \nmid 24756, 24756 is not a common multiple of 3054 \text{ and } 12378.

We proceed by testing every subsequent multiple i.e., the 3\text{rd}, 4\text{th}, 5\text{th}, etc., for divisibility by 3054.

Proceeding this way, we arrive at the 509\text{th} multiple. We test 509 \cdot 12378 = 6300402. Since 3054 \,|\, 6300402 and all the other smaller positive multiples of 12378 are not multiples of 3054, the least common multiple of 3054 \text{ and } 12378 is 6300402.

We can see that this method of finding the least common multiple of two nonzero integers becomes cumbersome when the integers are large. We had to iterate through 509 multiples of 12378 till we found a multiple that is common to both 3054 \text{ and } 12378.

Is there a more efficient way to find the least common multiple of two nonzero integers? Number Theory is one of those rare mathematical disciplines where one oftentimes solves problems by relying to a large extent upon trial and error, in combination with some curiosity, intuition and ingenuity. Often patient, plodding experimentation precedes rigorous proof. We will tackle this problem of coming up with an efficient way to find the least common multiple of two nonzero integers using this philosophy. We will try and connect some of ideas we have encountered so far to solve this problem.

We have seen before that given nonzero integers a \text{ and } b, \text{lcm}(a, b) \leq |ab|. Therefore, if a \text{ and } b are positive integers then,

\text{lcm}(a, b) \leq ab

If \text{lcm}(a, b) = ab, then it is easy to find the least common multiple of a \text{ and } b since we have to just multiply a \text{ with } b. In which situation does \text{lcm}(a, b) = ab? Lets try some examples.

\begin{equation*} 
\begin{split}
\text{lcm}(2, 3) &= 6\\
\text{lcm}(5, 6) &= 30\\
\text{lcm}(15, 22) &= 330\\
\end{split}
\end{equation*}

We can see that whenever integers a \text{ and } b are relatively prime i.e., \text{gcd}(a, b) = 1, then \text{lcm}(a, b) = ab. Therefore, we can see that whenever integers a \text{ and } b are relatively prime,

\text{gcd}(a, b)\,\text{lcm}(a, b) = ab

The next question to ask is whether this relationship always holds irrespective of whether a \text{ and } b are relatively prime. Lets try to check this using some examples.

Let us verify whether \text{gcd}(18, 42)\,\text{lcm}(18, 42) = 756 is true.

We will find \text{gcd}(18, 42) using Euclidean Algorithm.

\begin{equation*} 
\begin{split}
42 &= 2 \times 18 + 6 \\
18 &= 3 \times 6 + 0 \\
\end{split}
\end{equation*}

We can see that \text{gcd}(18, 42) = 6. We have already calculated \text{lcm}(18, 42) = 126. Since 6 \times 126 = 756, the relationship namely, \text{gcd}(18, 42)\,\text{lcm}(18, 42) = 18 \times 42 = 756 holds good in this case.

In order to verify whether this relationship is true for any two positive integers we will postulate this relationship as a theorem and try to prove it.

Relationship between gcd and lcm of positive integers

The following theorem establishes a relationship between the greatest common divisor and the least common multiple of two positive integers.

Theorem

For positive integers a \text{ and } b, \text{gcd}(a, b)\, \text{lcm}(a, b) = ab.

Proof. Suppose d = \text{gcd}(a, b). By definition, d \,|\, a \text{ and } d \,|\, b. We know from the definition of the divisibility of integers that, if a positive integer d divides a, then a = dr, for some integer r. Similarly, b = ds, for some integer s.

Consequently, r = \dfrac{a}{d} \text{ and } s = \dfrac{b}{d}. Suppose there is a positive integer m such that m = \dfrac{ab}{d}. Then m = as = rb i.e., a \,|\, m \text{ and } b \,|\, m. Therefore, by definition, m is the common multiple of a \text{ and } b.

Now let c be any positive integer that is a common multiple of a \text{ and } b i.e., c = au = bv for integers u \text{ and } v.

From this theorem, we know that since d = \text{gcd}(a, b), there exist integers x \text{ and } y such that d = ax + by.

Consequently,

\frac{c}{m} = \frac{cd}{ab} = \frac{c(ax + by)}{ab} = \Big(\frac{c}{b}\Big)x + \Big(\frac{c}{a}\Big)y = vx + uy

Since the expression vx + uy is the sum of the product of two integers, it is also an integer. Therefore, m \,|\, c. Consequently, from part (f) of the theorem we have already proved, m \leq c.

Hence, in accordance with this definition of the least common multiple of two nonzero integers, m = \text{lcm}(a, b). That is,

\text{lcm}(a, b) = \frac{ab}{d} = \frac{ab}{\text{gcd}(a, b)}

Rewriting the above equation, we get

\text{gcd}(a, b)\, \text{lcm}(a, b) = ab

which is what we started out to prove.

We have already discussed the corollary of this theorem which we will now formally state.

Corollary. For any choice of positive integers a \text{ and } b, \text{lcm}(a, b) = ab if and only if \text{gcd}(a, b) = 1.

It should be noted that for nonzero integers a \text{ and } b, \text{gcd}(a, b)\, \text{lcm}(a, b) = |ab|. The proof is the same as what we have already proved except that m = \dfrac{|ab|}{d}.

Calculation of lcm of integers using the relationship between gcd and lcm of integers

The main purpose of the theorem we have just proved is to make the calculation of the least common multiple of two integers dependent on the value of their greatest common divisor, which in turn can be calculated from the Euclidean Algorithm.

Earlier we had calculated the least common multiple of 3054 \text{ and } 12378 by iterating through each multiple of 12378 and checking whether it was divisible by 3054. We found the calculation tiresome since we had to iterate till the 509th multiple of 12378 to get the least common multiple of both 3054 \text{ and } 12378. We will now use this theorem we have just proved to recalculate \text{lcm}(3054, 12378) and thereby demonstrate the efficiency of this method over the previous one.

Since \text{lcm}(3054, 12378) = \dfrac{3054 \times 12378}{\text{gcd}(3054, 12378)}, we will first calculate \text{gcd}(3054, 12378) using the Euclidean Algorithm.

The appropriate applications of the Division Algorithm produce the following equations:

\begin{equation*} 
\begin{split}
12378 &= 4 \times 3054 + 162 \\
3054 &= 19 \times 162 - 24  \\
162 &= 7 \times 24 - 6  \\
24 &= (-4)(-6) + 0
\end{split}
\end{equation*}

From our previous discussion we know that the absolute value of the last nonzero remainder appearing in these equations, namely, integer 6, is the great common divisor of 3054 \text{ and } 12378.

Therefore, \text{gcd}(3054, 12378) = 6 and consequently,

\text{lcm}(3054, 12378) = \frac{3054 \times 12378}{6} = 6300402

Greatest Common Divisor of more than Two Integers

The notion of greatest common divisor can be extended to more than two integers in an obvious way.

For example, in the case of three integers a, b \text{ and } c, not all zero, \text{gcd}(a, b, c) is defined to be the positive integer d having the following properties:

(a) d is a divisor of each of a, b \text{ and } c

(b) If e divides the integers a, b \text{ and } c, then e \leq d

Calculating the Greatest Common Divisor of Three Integers

How do we calculate the greatest common divisor of three integers? We know how to calculate the greatest common divisor of two integers using Euclidean Algorithm. We could use the Euclidean Algorithm to calculate the greatest common divisor of three integers if we could transform the problem of calculating the greatest common divisor of three integers into an equivalent one of calculating the greatest common divisor of two integers.

The following theorem will help us achieve this.

Theorem

For integers a, b \text{ and } c, no two of which are zero and d = \text{gcd}(a, b, c)

d = \text{gcd}(\text{gcd}(a, b), c) = \text{gcd}(a, \text{gcd}(b, c)) = \text{gcd}(\text{gcd}(a, c), b) 

Since d = \text{gcd}(a, b, c), by definition, d \,|\, a, d \,|\, b \text{ and } d \,|\, c.

Since d \,|\, a \text{ and } d \,|\, b, by part (g) of the theorem we have already proved, d \,|\, ax + by, for arbitrary integers x \text{ and } y.

From this theorem we know that there exist integers x \text{ and } y such that \text{gcd}(a, b) = ax + by.

Therefore, d \,|\, \text{gcd}(a, b) and consequently, d is a positive common divisor of \text{gcd}(a, b) \text{ and } c .

Suppose e = \text{gcd}(\text{gcd}(a, b), c), where e is some positive integer.

Since e is the greatest common divisor of \text{gcd}(a, b) \text{ and } c, by definition, d \leq e.

Let f = \text{gcd}(a, b), where f is some positive integer.

By definition, e \,|\, f \text{ and } e \,|\, c.

By the definition of divisibility of integers, if e \,|\, f, then there exists an integer r such that f = er.

Since f = \text{gcd}(a, b), by definition, f \,|\, a \text{ and } f \,|\, b. Therefore, by the definition of divisibility of integers, a = fs \text{ and } b = ft, for some integers s \text{ and } t.

Therefore, a = fs = e(rs) \text{ and } b = ft = e(rt) and consequently, e \,|\, a \text{ and } e \,|\, b.

Since e \,|\, a, e \,|\, b \text{ and } e \,|\, c and d = \text{gcd}(a, b, c), by definition, e \leq d.

Since d \leq e and e \leq d, it follows that d = e; that is,

d = \text{gcd}(\text{gcd}(a, b), c)

Similarly, we can prove that d = \text{gcd}(a, \text{gcd}(b, c)) = \text{gcd}(\text{gcd}(a, c), b).

Example

Let us calculate \text{gcd}(39, 42, 54).

From the theorem we have just proved it follows that \text{gcd}(39, 42, 54) = \text{gcd}(\text{gcd}(39, 42), 54).

We will first calculate \text{gcd}(39, 42).

Applying the Euclidean Algorithm to the evaluation of \text{gcd}(39, 42), we find that

\begin{equation*} 
\begin{split}
42 &= 1 \times 39 + 3\\
39 &= 13 \times 3 + 0\\
\end{split}
\end{equation*}

and therefore, \text{gcd}(39, 42) = 3.

Incorporating this result in our calculation, we get

\text{gcd}(39, 42, 54) = \text{gcd}(\text{gcd}(39, 42), 54) = \text{gcd}(3, 54)

Once again, we will apply the Euclidean Algorithm to evaluate \text{gcd}(3, 54).

\begin{equation*} 
\begin{split}
54 &= 18 \times 3 + 0\\
\end{split}
\end{equation*}

Therefore, \text{gcd}(3, 54) = 3.

Hence,

\text{gcd}(39, 42, 54) = \text{gcd}(\text{gcd}(39, 42), 54) = \text{gcd}(3, 54) = 3

It should be noted the we can extend the definition of the greatest common divisor of two integers to any number of integers by adopting the method we used to define the greatest common divisor of three integers.

Next Topic : The Diophantine Equation