Recursive Extended Euclidean Algorithm

The greatest common divisor of positive integers , , …, is the largest integer such that divides each of the integers. There always exist integers , , …, such that .

Mathematica's built-in function ExtendedGCD returns , given the arguments . This Demonstration implements ExtendedGCD with a recursive extended Euclidean algorithm that computes a list of the results of the recursive steps.

The basic case is . The algorithm, given and , returns the list (as a column):

,

,

…,

.

Here, , where , using the division algorithm, and .

The correct result is returned in the deepest step of the recursion, and .

We define , , and , .

Suppose , and .

Then .

And, .

Thus, if the correct result is returned at depth , the correct result is returned at depth . By induction, the result at depth 0 is correct: and .

The idea behind the the algorithm () can be gleaned by studying numerical examples provided by the Demonstration. In each case, observe that the result is correct at the deepest level of the recursion (last line of the list), and the correctness at depth (a given line) implies the correctness at depth (the previous line). The result at depth 0 (the first line) is therefore correct.