The Integers - Introduction to Cryptography with Java Applets - page 75

of a 1 and a 2 by proposition 7 (part c). Now consider an integer that divides the last n 2

integers in the list, and that also divides the gcd of a 1 and a 2 . This divisor must then also sep-
arately divide both a 1 and a 2 , and so then is a common divisor of all the n integers. We now
see that the common divisors of all the n integers are exactly the same as the common divi-
sors of the last n

2 integers taken with the gcd of the first two. Hence, they also have the
same greatest common divisor.

E XAMPLE . The previous proposition is very handy in that it turns a large problem into a
small one. It says, for example, that we can compute the gcd of 28, 126, 21, and 10 in the
following way:

(28, 126, 21, 10)
= ((28, 126), 21, 10)
= (14, 21, 10)
= ((14, 21), 10)
= (7, 10)
= 1.

Note that the previous numbers, when taken together, have a gcd of 1. However, if we
examine each pair from the list, we see that some pairs are not relatively prime. (For exam-
ple, (28, 21) = 7.) This motivates us to make a distinction between these two situations, and
thus make a definition.

Definition
We say that the integers a 1 , a 2 , . . . , a n are mutually relatively prime if the gcd of the
set of integers is 1. We say the integers are pairwise relatively prime if each pair of
integers taken from the set are relatively prime.

E XAMPLE . The numbers 18, 9, and 25 are mutually relatively prime. The largest divisor all
have in common is 1. But, they are not pairwise relatively prime because (18, 9) = 9.

Until now, we have presented a lot of propositions about the gcd, but no really good way
of finding it has been presented. We could make a list of all the divisors of our numbers, then
choose the largest divisor that they have in common, but this is not really efficient. The
next proposition, which you should be able to prove, leads us to the Euclidean algorithm, a
lightning-fast way of finding the gcd.

PROPOSITION 10 If c and d are integers and c = dq + r where q and r are integers, then

( c , d ) = ( d , r ).