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.