Page 88 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

• Example for # 1: Let’s use the Euclidean Algorithm to find (103, 37). First, we divide the
larger number by the smaller one. So,

103 =37 ∗ 2+ 29.

Now, we take the 37 and divide it by the remainder 29,

37 =29 ∗ 1+ 8.

Then, we take 29 and divide it by the remainder 8,

29 =8 ∗ 3+ 5.

Then, we take 8 and divide it by the remainder 5,

8= 5 ∗ 1+ 3.

Next, we take 5 and divide it by the remainder 3,

5= 3 ∗ 1+ 2.

We take 3 and divide it by the remainder 2,

3= 2 ∗ 1+ 1.

Now, we take 2 and divide it by the remainder 1,

2= 1 ∗ 2.

There is no remainder: the remainder is zero. This means that the previous remainder is the

greatest common divisor. The previous remainder was 1. So (103, 37) =1.

• Example for # 2 , # 3, and #4: We can use the Euclidean Algorithm backwards. Let’s use our
work in the previous example to find r and s such that

103r +37s =1.

We do this by writing each remainder as an integer times 103 plus an integer times 37. The
first remainder is 29. To write this as an integer times 103 plus an integer times 37, we re-
arrange the long division equation,

103 =37 ∗ 2+ 29 → 29 = 103 +(−2)37.

88