Page 286 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 265

Greatest Common Divisors and Least Common Multiples

The largest integer that divides both of two integers is called the greatest common divisor of
these integers.

DEFINITION 2 Let a and b be integers, not both zero. The largest integer d such that d | a and d | b is called
the greatest common divisor of a and b. The greatest common divisor of a and b is denoted
by gcd(a, b).

The greatest common divisor of two integers, not both zero, exists because the set of common
divisors of these integers is nonempty and finite. One way to find the greatest common divisor
of two integers is to find all the positive common divisors of both integers and then take the
largest divisor. This is done in Examples 10 and 11. Later, a more efficient method of finding
greatest common divisors will be given.

EXAMPLE 10 What is the greatest common divisor of 24 and 36?

Solution: The positive common divisors of 24 and 36 are 1, 2, 3, 4, 6, and 12. Hence,
gcd(24, 36) = 12. ▲

EXAMPLE 11 What is the greatest common divisor of 17 and 22?

Solution: The integers 17 and 22 have no positive common divisors other than 1, so that
gcd(17, 22) = 1. ▲

Because it is often important to specify that two integers have no common positive divisor
other than 1, we have Definition 3.

DEFINITION 3 The integers a and b are relatively prime if their greatest common divisor is 1.

EXAMPLE 12 By Example 11 it follows that the integers 17 and 22 are relatively prime, because
gcd(17, 22) = 1. ▲

Because we often need to specify that no two integers in a set of integers have a common
positive divisor greater than 1, we make Definition 4.

DEFINITION 4 The integers a 1 ,a 2 ,...,a n are pairwise relatively prime if gcd(a i ,a j ) = 1 whenever 1 ≤
i< j ≤ n.

EXAMPLE 13 Determine whether the integers 10, 17, and 21 are pairwise relatively prime and whether the
integers 10, 19, and 24 are pairwise relatively prime.

Solution: Because gcd(10, 17) = 1, gcd(10, 21) = 1, and gcd(17, 21) = 1, we conclude that
10, 17, and 21 are pairwise relatively prime.
Because gcd(10, 24) = 2 > 1, we see that 10, 19, and 24 are not pairwise relatively
prime. ▲