9846

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.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • 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 »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+