The Extended Euclidean Algorithm

The Extended Euclidean Algorithm computes the greatest common divisor of two integers, and expresses the greatest common divisor as a linear combination of the two numbers.

This script will carry out the Extended Euclidean Algorithm for you. To use it, enter the two numbers in the blanks below, then submit the form. (In some Web browsers, you submit a form by clicking on "Submit" with your mouse; in a text-based brower like Lynx, you use the Arrow keys to highlight "Submit", then press ENTER.)

The script will return a table which shows the work for the computation, followed by the greatest common divisor and the linear combination.

Introduction: The Extended Euclidean Algorithm
The statement and proof of the Extended Euclidean Algorithm
Example: Using the algorithm by hand

Send comments about this page to: bikenaga@marauder.millersville.edu.

Last updated: June 13, 2005

Bruce Ikenaga's Home Page

Math Department Home Page

Millersville University Home Page