An Example Using the Extended Euclidean Algorithm

If you're using the algorithm by hand (as opposed to using a computer), you can use a table to keep the numbers straight and remember what to do. I'll illustrate by applying the algorithm to find the greatest common divisor of 187 and 102. Here's how you start:

The a and q columns are filled in by successive division: Divide the next-to-the-last a by the last a. The quotient goes into the q-column, and the remainder goes into the a-column.

Divide 187 by 102; the quotient is 1, the remainder is 85.

Divide 102 by 85; the quotient is 1, the remainder is 17.

When the division comes out evenly, you stop. In this case, 85 divided by 17 is 5, with a remainder of 0.

The last entry in the a-column is the greatest common divisor. Thus, (187,102) = 17.

The x and y-columns are filled in using the following rules:

• (next x) = (next-to-last x) - q (last x)
• (next y) = (next-to-last y) - q (last y)

It's probably easier to show than it is to explain.

1 - (1)(0) = 1

0 - (1)(1) = -1

0 - (1)(1) = -1

1 - (1)(-1) = 2

The last x and y give the coefficients in a linear combination for the greatest common divisor. Thus,

   17 = (187,102) = (-1)(187) + (2)(102).

Here's how the whole thing looks, one step at a time:

• Introduction: The Extended Euclidean Algorithm
• The statement and proof of the Extended Euclidean Algorithm
• An Extended Euclidean Algorithm calculator

Send comments about this page to: bikenaga@marauder.millersville.edu.

Last updated: June 13, 2005

Bruce Ikenaga's Home Page

Math Department Home Page

Millersville University Home Page

Copyright 1998 by Bruce Ikenaga