Extended Euclidean Algorithm steps

m= n=

The following steps will find x,y to satisfy gcd(m,n)=mx+ny. Scroll down or click for the theory.

click Go to start

Theory

The algorithm works on a pair of equations (rather than just one equation)
z=mx+ny
w=mu+nv
In each iteration the invariant gcd(z,w)=gcd(m,n) holds. Without knowing the answer to gcd(m,n) beforehand, we can still establish the invariant by suitable initialization and steps.

The pair is initially the trivial
m=m×1+n×0
n=m×0+n×1
The invariant gcd(z,w)=gcd(m,n) is established because we use z=m, w=n as initial values.

In each step we subtract one equation by a multiple of another:

z=m×x+n×y
-) q× w=m×u+n×v
z-q×w=m×(x-q×u)+n×(y-q×v)

and the second and third equations become the new pair. This preserves the invariant because gcd(z,w)=gcd(z-q×w,w). We use q = z div w, i.e., z-q×w = z mod w.

Eventually z-q×w will become 0. Then the invariant tells us gcd(m,n)=gcd(0,w)=w. The equation w=m×u+n×v then becomes the solution we want, gcd(m,n)=m×u+n×v.


I have more Math Homework Help