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

(f)

Figure 3.1

(g)

(h)

E XAMPLE . The divisors of 30 are 1, 2, 3, 5, 6, 10, 15, and 30. The divisors
of 18 are 1, 2, 3, 6, 9, 18. The largest integer in both lists is 6, so the gcd of 30
and 18 is 6.

Definition
Two integers are said to be relatively prime if their gcd is 1.

E XAMPLES .

The following pairs of integers are relatively prime. (Verify.)

a. 8 and 9
b. 23 and 44
c. 27 and 55