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

Note that the sign of the integers is not important when computing the gcd. This is easy
to see if one simply notices that the divisors of n are exactly the same as the divisors of n .

So, all of the following are equal:

( x , y ) = ( x ,

y ) = ( x , y ) = ( x , y ) = (| x |, | y |)

Thus, we need only concern ourselves with the gcd of positive integers.

E XAMPLE .

(18, 54) = (18, 54) = 9.

PROPOSITION 7 Let x , y , and z be integers with ( x , y ) = d . Then

a. ( x / d , y / d ) = 1
b. ( x + cy , y ) = ( x , y ).
c. An integer c divides both x and y if and only if c |( x , y ).

Proof. (Part a.) First, suppose there is some integer n that divides both x / d and y / d . Then
integers j and k such that x / d = jn and y / d = kn or, alternatively, x = djn and y = dkn . From
this we establish that dn is a common divisor of both x and y . But d is the greatest common
divisor of both x and y , so dn ≤ d , implying that n = 1. So the gcd of x / d and y / d is 1.
(Part b.) Let x , c , and y be integers, and suppose e is a common divisor of x and y . By
Proposition 2 we know e |( x + cy ), so e divides both x + cy and y . On the other hand, sup-
pose f is a common divisor of x + cy and y . Then f also divides ( x + cy ) cy = x by Propo-
sition 2. So f is then a common divisor of x and y . Consequently, we conclude that the
common divisors of x and y are identical to the common divisors of x + cy and y , and so they
share the same greatest common divisor.
(Part c.) The “if ” part is obvious, since ( x , y ) divides both x and y , and because if we have
c |( x , y ) we must have c | x and c | y by proposition 1. This tells us that the divisors of ( x , y ) is
a subset of the common divisors of x and y . We can represent this with a Venn diagram, as
shown in Figure 3.2.
Now we write x and y as multiples of their gcd; that is,

x = ( x , y ) e , and y = ( x , y ) f .

and note ( e , f ) = 1 by part (a). Thus, no common divisor of x and y (except 1) can simulta-
neously divide e and f , and so any common divisor of x and y must also divide ( x , y ).
Thus, the set of divisors of ( x , y ) and the set of common divisors of x and y are the same
set. (See Figure 3.3.)

E XAMPLES .

To satisfy our cynical natures, we'll test the previous proposition with some data.