Page 289 - Discrete Mathematics and Its Applications

268 4 / Number Theory and Cryptography

LEMMA 1 Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r).

Proof: If we can show that the common divisors of a and b are the same as the common divisors
of b and r, we will have shown that gcd(a, b) = gcd(b, r), because both pairs must have the
same greatest common divisor.
So suppose that d divides both a and b. Then it follows that d also divides a − bq = r (from
Theorem 1 of Section 4.1). Hence, any common divisor of a and b is also a common divisor
of b and r.
Likewise, suppose that d divides both b and r. Then d also divides bq + r = a. Hence, any
common divisor of b and r is also a common divisor of a and b.
Consequently, gcd(a, b) = gcd(b, r).

Suppose that a and b are positive integers with a ≥ b. Let r 0 = a and r 1 = b. When we
successively apply the division algorithm, we obtain

r 0 = r 1 q 1 + r 2 0 ≤ r 2 <r 1 ,
r 1 = r 2 q 2 + r 3 0 ≤ r 3 <r 2 ,
·
·
·
r n−2 = r n−1 q n−1 + r n 0 ≤ r n <r n−1 ,
r n−1 = r n q n .

Eventually a remainder of zero occurs in this sequence of successive divisions, because the
sequence of remainders a = r 0 >r 1 >r 2 > ··· ≥ 0 cannot contain more than a terms. Fur-
thermore, it follows from Lemma 1 that

gcd(a, b) = gcd(r 0 ,r 1 ) = gcd(r 1 ,r 2 ) = ··· = gcd(r n−2 ,r n−1 )
= gcd(r n−1 ,r n ) = gcd(r n , 0) = r n .

Hence, the greatest common divisor is the last nonzero remainder in the sequence of divisions.

EXAMPLE 16 Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.

Solution: Successive uses of the division algorithm give:

662 = 414 · 1 + 248
414 = 248 · 1 + 166
248 = 166 · 1 + 82
166 = 82 · 2 + 2
82 = 2 · 41.

Hence, gcd(414, 662) = 2, because 2 is the last nonzero remainder. ▲

The Euclidean algorithm is expressed in pseudocode in Algorithm 1.