If m and n are integers (not both 0), the greatest common divisor (m,n) of m and n is the largest integer which divides both m and n. The Euclidean algorithm uses repeated division to compute the greatest common divisor.
The greatest common divisor of m and n can be expressed as an integer linear combination of m and n. That is, there are integers c and d such that
(m,n) = c m + d n.
There are infinitely many pairs of numbers c, d 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 (m,n) of integers m and n, as well as numbers c and d such that
(m,n) = c m + d n.
Send comments about this page to: bikenaga@marauder.millersville.edu.
Last updated: June 13, 2005
Millersville University Home Page
Copyright 1998 by Bruce Ikenaga