gcd(a, b) = sa + tb.
[Note that, since gcd(a, b) is usually less than both a and b, one of s or t will usually be negative.]
As a reminder, here are the steps of the standard Euclidean algorithm to find the greatest common divisor of two positive integers a and b:
Set the value of the variable c to the larger of the two values a and b, and set d to the smaller of a and b.
Find the remainder when c is divided by d. Call this remainder r.
If r = 0, then gcd(a, b) = d. Stop.
Otherwise, use the current values of d and r as the new values of c and d, respectively, and go back to step 2.
The extended Euclidean algorithm uses the same framework, but there is a bit more bookkeeping. Before we present a formal description of the extended Euclidean algorithm, let’s work our way through an example to illustrate the main ideas.