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 |
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