Description

The Euclidean algorithm is usually usedsimplyto find the greatest common divisor of two integers. (Foradescription of this algorithm, see the notes aboutadditionaltopics in number theory.) The standard Euclideanalgorithm givesthe greatest common divisor and nothing else.However, if we keeptrack of a bit more information as we go throughthe algorithm, wecan discover how to write the greatest commondivisor as an integerlinear combination of the two originalnumbers. In other words, wecan find integers s and t such that

gcd(a, b) = sa + tb.

[Note that, since gcd(a, b) is usually less than both a andb,one of s or t will usually be negative.]

As a reminder, here are the steps of the standardEuclideanalgorithm to find the greatest common divisor of twopositiveintegers a and b:

Set the value of the variable c to the larger of the two valuesaand b, and set d to the smaller of a and b.
Find the remainder when c is divided by d. Call thisremainderr.
If r = 0, then gcd(a, b) = d. Stop.
Otherwise, use the current values of d and r as the new values ofcand d, respectively, and go back to step 2.
The extended Euclidean algorithm uses the same framework, butthereis a bit more bookkeeping. Before we present a formaldescriptionof the extended Euclidean algorithm, let’s work our waythrough anexample to illustrate the main ideas.