Unknown

32 1. Fundamentals

number into the larger to get

1606 = 3.418 + 352.

Explain why the greatest common divisor of 418 and 1606 is the same

as the greatest common divisor of 352 and 418. Accordingly, we look

for the greatest common divisor of 352 and 418.

418 = 1.352 + 66

Continue on:

352 = 5.66+22

66 = 3.22+0.

What is the greatest common divisor of 418 and 1606? Justify your

answer. Carry out the same process to find gcd(20119, 34782).

Explain the following pencil-and-paper rendition of the Euclidean

algorithm:

3

418)1606

2. (a) An important application of the Euclidean algorithm is to obtain
   a representation for the greatest common divisor of two numbers.
   Taking the numerical example of the last exercise, we can start
   with the representation of the greatest common divisor given by
   the second last equation and work our way back through the
   equations:

22 = 1.352 - 5.66 = 1.352 - 5(418 - 1.352)

= 6.352 - 5.418 = 6(1606 - 3.418) - 5.418

= 6.1606 - 23.418.

This can be rendered in a handy paper-and-pencil form. Suppose

we have performed the paper-and-pencil calculation to find the

greatest common divisor. Now construct the table:

-5 -1 -3

1 -5 6 -23.