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 a_{k} and (a_{1}, a_{2}).

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 a_{1}, a_{2}, … ,a_{n} are zero they have greatest common divisor (a_{1}, … ,a_{n}). Its value can be found by repeated application of the Euclidean algorithm, using the fact that

The equation

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 a_{k} using simple algebra and Euclid’s algorithm.

## Leave a Reply