Page 288 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 267

THEOREM 5 Let a and b be positive integers. Then

ab = gcd(a, b) · lcm(a, b).

The Euclidean Algorithm

Computing the greatest common divisor of two integers directly from the prime factorizations
of these integers is inefficient. The reason is that it is time-consuming to find prime factoriza-
tions. We will give a more efficient method of finding the greatest common divisor, called the
Euclidean algorithm. This algorithm has been known since ancient times. It is named after the
ancient Greek mathematician Euclid, who included a description of this algorithm in his book
The Elements.
Before describing the Euclidean algorithm, we will show how it is used to find gcd(91, 287).
First, divide 287, the larger of the two integers, by 91, the smaller, to obtain

287 = 91 · 3 + 14.

Any divisor of 91 and 287 must also be a divisor of 287 − 91 · 3 = 14. Also, any divisor of 91
and 14 must also be a divisor of 287 = 91 · 3 + 14. Hence, the greatest common divisor of 91
and 287 is the same as the greatest common divisor of 91 and 14. This means that the problem
of finding gcd(91, 287) has been reduced to the problem of finding gcd(91, 14).
Next, divide 91 by 14 to obtain

91 = 14 · 6 + 7.

Because any common divisor of 91 and 14 also divides 91 − 14 · 6 = 7 and any common divisor
of 14 and 7 divides 91, it follows that gcd(91, 14) = gcd(14, 7).
Continue by dividing 14 by 7, to obtain

14 = 7 · 2.

Because 7 divides 14, it follows that gcd(14, 7) = 7. Furthermore, because gcd(287, 91) =
gcd(91, 14) = gcd(14, 7) = 7, the original problem has been solved.
We now describe how the Euclidean algorithm works in generality. We will use successive
divisions to reduce the problem of finding the greatest common divisor of two positive integers
to the same problem with smaller integers, until one of the integers is zero.
The Euclidean algorithm is based on the following result about greatest common divisors
and the division algorithm.

EUCLID (325 b.c.e.– 265 b.c.e.) Euclid was the author of the most successful mathematics book ever written,
The Elements, which appeared in over 1000 different editions from ancient to modern times. Little is known
about Euclid’s life, other than that he taught at the famous academy at Alexandria in Egypt. Apparently, Euclid
did not stress applications. When a student asked what he would get by learning geometry, Euclid explained
that knowledge was worth acquiring for its own sake and told his servant to give the student a coin “because he
must make a profit from what he learns.”