The Euclidean Algorithm computes for us the greatest common divisor of two integers. The extended version actually gives integers x and y such that ax+by=gcd(a,b). One way of looking at this is to consider the equation ax+by=d, where a, b and d are known integers, and we are looking for a solution in x and y, where x and y must be integers. Writing equations with integer constants and solving for unknowns constrained to be integers is call a Diophantine problem.
Looked at this way, the Euclidean Algorithm is an efficient manner to solve the diophontine problem (that is, using only integers) ax+by=d, a simple linear equation in two unknowns. Such equations are not always solvable. The necessary anad sufficient conditions for solvablity is that d is a multiple of gcd(a,b). The Eucliden Algorithm at once solves this problem when it is solvable, and can be used to compute gcd(a,b).
It consists, essentially, of continually subtracting off one remainder from another, continually working the remainder smaller until it is zero. The next number before zero is the greatest common divisor. If we keep track of the multiples that were subtracted off we can work our way back to the integers x and y.
We want to show that ax+by=d is solvable of the integers for x and y whenever d is a multiple of the greatest common divisor of a and b.
Consider the set of all integers of the form ax+by (for the given a and b) when x and y vary over all possible integers. What does this set look like? Looking in this set, find the two integers that are the closest together. They differ by an amount d. That is (ax+by)-(ax'+by')=d. Rearranging a(x-x')+b(y-y')=d we see that d is in this set. Likewise all multiples of d is in this set: ka(x-x')+kb(y-y')=kd. What does the set of all integers of the form ax+by look like? It looks like kd for a certain d and all integers k.
a is in this set and so is b, so a=kd for some k and b=kd for some other k. So d is a common divisor of a and b. If a and b are relatively prime, then d=1. Thus we have shown that for gcd(a,b)=1 there is a solution in x and y for ax+by=1.
If k divides a and b both, then k must divide ax+by for all x and y, showing that if ax+by=d is solvable, then k must divide d. Supposing k does divide d, we now want to show a solution, and in particular when k equals d, the extreme case being when k is the greatest common divisor of a and b. If we can solve ax+by=gcd(a,b) then we can solve for any ax+by=d where d is a multiple of the greatest common divisor (how?).
To do this, write ax+by=a' gcd(a,b)x+b' gcd(a,b)y=gcd(a,b) and divide through by gcd(a,b), giving a'x+b'y=1 where gcd(a',b')=1. Solve for this x and y and then multiply that solution by gcd(a,b).
4 February 2008, Burton Rosenberg