For a and b, the number (a,b) is the largest number which divides a and b evenly.
This can be seen by solving the equation by making a sequence of simplifying substitutions:
It is easy to see that x''=1, y'=0 is a solution to the final equation and we get a solution to the original equation by working backwards:
We could also solve an equation like 30x+69y=15 by multiplying our solution: y=-15, x=35. It should be clear that the equation will have no solution in integers if 15 is replaced by something that is not a multiple of (30,69)=3.
All other integer solutions of 30x+69y=15 may be obtained by changing the first solution:
If we do the process illustrated on the previous page for any equation ax+by=(a,b), we eventually get one of the coefficients as zero and the other as (a,b). In fact, this process is usually presented as ``Euclid's algorithm for finding the greatest common divisor.''
It is important that this process is feasible on a computer even if
a and b are several hundred digits long. It is easy to show that
the larger of the two coefficients decreases by at least 1/2 every
two equations, hence every twenty equations the larger coefficient
has decreased by 
, so a 600-digit number would not
require more than 4000 equations.
We pointed out earlier that division does not work with congruences. An important application of Theorem 1 is that it does work for prime numbers.
