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

The previous proposition provides us with a particularly fast way of finding the gcd of
two integers. We will calculate the gcd of 132 and 55. If we successively apply the division
algorithm to obtain

132 = 2 · 55 + 22
55 = 2 · 22 + 11
22 = 2 · 11 + 0,
the preceding proposition then tells us that

(132, 55) = (55, 22) = (22, 11) = (11, 0) = 11.
Note that we wisely chose q and r as the same q and r obtained by the division algorithm.
The remainders are all positive, and are getting smaller after each successive division. The
remainder must eventually reach 0, and the previous remainder must be the gcd. The proof
that this always works follows.

3.2

THE EUCLIDEAN ALGORITHM
PROPOSITION 11 (The Euclidean Algorithm.) Let r 0 = x and r 1 = y be integers such that
x ≥ y > 0. If the division algorithm is successively applied to obtain r j = r j 1 q j 1 + r j 2 with
0 < r j 2 < r j 1 for j = 0, 1, 2, . . . , n 2 and r n 1 = 0, then ( x , y ) = r n .

Proof. This follows almost immediately using proposition 10. Let r 0 = x , r 1 = y , where x

≥ y

> 0. We successively apply the division algorithm to obtain
r 0 = r 1 q 1 + r 2

with 0 ≤ r 2 < r 1

r 1 = r 2 q 2 + r 3 with 0

≤ r 3 <

r 2

...
r i 2 = r i 1 q i 1 + r i
...

This process must terminate. The remainders form a strictly decreasing sequence of pos-
itive integers bounded below by zero. This sequence can certainly have no more than x

terms:

r 0 ≥ r 1 > r 2 > . . . > r n 1 > r n > r n 1 = 0.
We must eventually have r n 1 = 0 for some n , where r n is the last nonzero remainder.
Proposition 10 then tells us that

x y r 0 , r 1 ) = ( r 1 , r 2 ) = . . . = ( r n 1 , r n ) = ( r n , r n 1 ) = ( r n , 0) = r n

( , ) = (

and we have the desired result.

E XAMPLE . Use the Euclidean algorithm to find the gcd of 252 and 198. Successively apply
the division algorithm to obtain