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 .[more]
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):
These rows are , where is the depth of the recursion, is the integer quotient of and , and is recursively defined by , if , and if , , where and .
The recursion terminates because . If , , , and . If , assume and . Then, , and . By induction, whenever and are positive integers, , where and .
Thus, in each row , , is the depth of recursion, is the input and is the output of with .
You can check this by studying numerical examples. Check it is true for the last row. Then check that if is true for a given row, then it is true for the previous row. It is therefore true for the first row.
When , it is a little more difficult to prove, but you can still verify numerically that if and are successive rows and , then . Also, this is true for the last row.[less]
The correctness of the recursive definitions in the source code can be argued by observing 1) they terminate, 2) they return the correct result when they terminate, and 3) they return the correct result whenever a recursive call returns the correct result. The function in the program for is ; it is defined there for reference. Only is used, however. It has a list of positive integers and a recursion level for inputs and returns the list that is displayed.
A classic exposition of these ideas is found in "1.7 The Euclidean Algorithm", in Birkhoff and MacLane, which can be read online.
The recursive algorithm we have used (for ) is essentially described in Euclidean algorithm, under "Extended Euclidean Algorithm".
G. Birkhoff and S. MacLane, A Survey of Modern Algebra, 4th ed., New York: MacMillan Publishing Co., 1977.
K. H. Rosen, Elementary Number Theory and its Applications, 4th ed., Reading, MA: Addison–Wesley, 2000.