Page 287 - Discrete Mathematics and Its Applications

266 4 / Number Theory and Cryptography

Another way to find the greatest common divisor of two positive integers is to use the prime
factorizations of these integers. Suppose that the prime factorizations of the positive integers a
and b are

a 1 a 2
b 1 b 2
a = p p ··· p ,b = p p ··· p ,
b n
a n
1 2 n 1 2 n
where each exponent is a nonnegative integer, and where all primes occurring in the prime
factorization of either a or b are included in both factorizations, with zero exponents if necessary.
Then gcd(a, b) is given by
min(a 1 ,b 1 ) min(a 2 ,b 2 ) min(a n ,b n )
gcd(a, b) = p p ··· p ,
1 2 n
where min(x, y) represents the minimum of the two numbers x and y. To show that this formula
for gcd(a, b) is valid, we must show that the integer on the right-hand side divides both a and b,
and that no larger integer also does. This integer does divide both a and b, because the power of
each prime in the factorization does not exceed the power of this prime in either the factorization
of a or that of b. Further, no larger integer can divide both a and b, because the exponents of
the primes in this factorization cannot be increased, and no other primes can be included.

3
3
2
EXAMPLE 14 Because the prime factorizations of 120 and 500 are 120 = 2 · 3 · 5 and 500 = 2 · 5 , the
greatest common divisor is
2 0 1
gcd(120, 500) = 2 min(3, 2) min(1, 0) min(1, 3) = 2 3 5 = 20. ▲
3
5
Prime factorizations can also be used to find the least common multiple of two integers.

DEFINITION 5 The least common multiple of the positive integers a and b is the smallest positive integer that
is divisible by both a and b. The least common multiple of a and b is denoted by lcm(a, b).

The least common multiple exists because the set of integers divisible by both a and b is
nonempty (as ab belongs to this set, for instance), and every nonempty set of positive integers
has a least element (by the well-ordering property, which will be discussed in Section 5.2).
Suppose that the prime factorizations of a and b are as before. Then the least common multiple
of a and b is given by

max(a 1 ,b 1 ) max(a 2 ,b 2 ) max(a n ,b n )
lcm(a, b) = p p ··· p ,
1 2 n
wheremax(x, y)denotesthemaximumofthetwonumbersx andy.Thisformulaisvalidbecause
a common multiple of a and b has at least max(a i ,b i ) factors of p i in its prime factorization,
and the least common multiple has no other prime factors besides those in a and b.

3 5 2
4 3
EXAMPLE 15 What is the least common multiple of 2 3 7 and 2 3 ?
Solution: We have

3 5 2
4 5 2
4 3
lcm(2 3 7 , 2 3 ) = 2 max(3, 4) max(5, 3) max(2, 0) = 2 3 7 . ▲
3
7
Theorem 5 gives the relationship between the greatest common divisor and least common
multiple of two integers. It can be proved using the formulae we have derived for these quantities.
The proof of this theorem is left as Exercise 31.