We saw in an earlier post that the binary linear diophantine equation
has a solution if and only if divides . We saw that a specific solution can be found by use of the Euclidean algorithm and that the set of all solutions is
where runs through all the integers. The alphas can be derived by simple algebra from the ak and (a1, a2).
This result can be generalised to any finite number of variables, as outlined in what follows and explained in more detail in the pdf here.
If not all the integers a1, a2, … ,an are zero they have greatest common divisor (a1, … ,an). Its value can be found by repeated application of the Euclidean algorithm, using the fact that
has a solution if and only if divides . If this is so, integers can be found such that
and it is then an easy matter to calculate a specific solution to the diophantine equation.
The general solution then has the form
The alphas can be calculated iteratively from the ak using simple algebra and Euclid’s algorithm.