It is easy to see that , 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 by multiplying
our solution: , . 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 .

All other integer solutions of
may be obtained by changing the first solution:

If we do the process illustrated on the previous page for any
equation , we eventually get one of the coefficients
as zero and the other as . [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 and are several hundred digits long. It is easy
to show that the larger of the two coefficients decreases by at
least every two equations, hence that in twenty equations
the larger coefficient has decreased by
, so
a 600-digit number would not require more than 4000 equations.
[this analysis can be improved]

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.

2002-12-14