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 y-column is filled in from bottom to top. The bottom y-value is always 0; the one above it is always 1.
Fill in the remaining y's from bottom to top using the following rule:
(next y) = (last q)(last y) + (next-to-last y).
It's probably easier to show than it is to explain.
(1)(1) + 0 = 1
(1)(1) + 1 = 2
To get the linear combination, form the products diagonally and subtract one from the other:
Thus,
17 = (187,102) = (2)(102) - (1)(187).
How do you know the order for the subtraction? The proof gives a formula, but the easiest thing is to pick one of the two ways, then fix it if it isn't right. If you subtract "the wrong way", you'll get a negative number. For example,
(1)(187) - (2)(102) = -17.
Since I know the greatest common divisor should be 17 (it's the last number in the a-column) I just multiply this equation by -1:
(-1)(187) + (2)(102) = 17.
This way, you don't need to memorize the exact formula.
Here's how the whole thing looks, one step at a time:
Send comments about this page to: bikenaga@marauder.millersville.edu.
Last updated: June 13, 2005
Millersville University Home Page
Copyright 1998 by Bruce Ikenaga