Archive for February, 2012

Linear Diophantine Equations

February 29, 2012

We saw in an earlier post that the binary linear diophantine equation

a_{1}x_{1} + a_{2}x_{2} = a_{0}

has a solution if and only if (a_{1}, a_{2}) divides a_{0} .  We saw that a specific solution x_{1}^{0}, x_{2}^{0} can be found by use of the Euclidean algorithm and that the set of all solutions is

x_{1} - x_{1}^{0} = \alpha_{1}t    ;  x_{2} - x_{2}^{0} = \alpha_{2}t

where t 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

(a_{1}, ... , a_{n}) = ((a_{1}, ... , a_{n-1}), a_{n})

 The equation

a_{1}x_{1} + ... + a_{n}x_{n} = a_{0}

has a solution if and only if (a_{1}, ... , a_{n}) divides a_{0} .  If this is so, integers x_{1}, x_{2}, ... , x_{n} can be found such that

a_{1}x_{1} + ... + a_{n}x_{n} = (a_{1}, ... , a_{n})

and it is then an easy matter to calculate a specific solution x_{1}^{0}, ... , x_{n}^{0} to the diophantine equation.

The general solution then has the form

x_{1} - x_{1}^{0} = \alpha_{1,1}t_{1}  ;  x_{2} - x_{2}^{0} = \alpha_{2,1}t_{1} + \alpha_{2,2}t_{2}


x_{n-1}-x_{n-1}^{0} = \alpha_{n-1,1}t_{1} \text{+ ... } +\alpha_{n-1,n-1}t_{n-1}

x_{n}-x_{n}^{0} = \alpha_{n,1}t_{1} \text{+ ... } +\alpha_{n,n-1}t_{n-1}

The alphas can be calculated iteratively from the ak using simple algebra and Euclid’s algorithm.