The extended Euclidean Algorithm

It is always possible to express the greatest common divisor of two nonzero natural numbers as a integer linear combination of such two numbers:

where m,n≠0 are integers. Working backwards in the above equations it is possible to express the last nonzero remainder in terms of previous ones, until we get an expression in terms of a and b. The corresponding algorithm is called the extended Euclidean algorithm. In the following implementation the algorithm takes a and b as input and outputs a list where the first element is gcd(a,b) and the next two are m and n, the coefficients of a and b.

This algorithm is useful when solving linear Diophantine equations of the form ax+by=z where a,b,x,y,z∈Z, such as

First we note that the gcd of 172 and 20 divides 1000, so the equation is solvable.

So from the extended Euclidean algorithm we have 2(172)-17(20)=4, and by multiplying this equation by we get

So =2()= 500, and =-17()=-4250 are solutions to the equation. It is easily seen that if and are solutions to the equation, then so are

where d is the gcd(a,b)and t is any integer.

Created by Mathematica  (June 3, 2006)