10214

# 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):
,
,
…,
.
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.

### DETAILS

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.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.