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.
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. 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.
|
![[Snapshot]](HTMLImages/index.en/thumbnail_1.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_2.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_3.gif)
Embed Interactive Demonstration 
Browse all topics
