Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: The Inverse of the Euclidean Algorithm and the Stern-Brocot Tree
Speaker: Arthur DuPre, Rutgers University - Newark
Date: Thursday, April 16, 2015 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
The Euclidean algorithm gives a mapping from pairs of positive integers to a finite sequence of positive integers which represents the sequence of quotients when the Euclidean algorithm is applied to the two positive integers. The inverse of the Euclidean algorithm applied to this finite sequence gives back the original two integers. The extended Euclidean algorithm applied to positive integers m and n yields two integers x and y so that mx + ny = GCD(m,n). The x and y are not unique and this is displayed nicely and graphically on the Stern-Brocot tree.