If a and b are integers (not both 0), the greatest common divisor (a,b) of a and b is the largest integer which divides both a and b. The Euclidean algorithm uses repeated division to compute the greatest common divisor.
The greatest common divisor of a and b can be expressed as an integer linear combination of a and b. That is, there are integers s and t such that
(a,b) = s a + t b.
There are infinitely many pairs of numbers s, t that work; sometimes, you can find a pair by trial and error. For example, (10,7) = 1, and by juggling numbers in my head I see that
1 = (-2)(10) + (3)(7).
On the other hand, (367,221) = 1, but it's not likely that you'd figure out that
1 = (-56)(367) + (93)(221)
by juggling numbers in your head!
The Extended Euclidean Algorithm computes the greatest common divisor (a,b) of integers a and b, as well as numbers s and t such that
(a,b) = s a + t b.
Send comments about this page to: bikenaga@marauder.millersville.edu.
Last updated: June 13, 2005
Millersville University Home Page
Copyright 1998 by Bruce Ikenaga