DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Matthew Russell, Rutgers University, russell2 {at} math [dot] rutgers [dot] edu)

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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

Abstract:

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.

See: http://www.math.rutgers.edu/~russell2/expmath/