## 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}$

$\text{.....}$

$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.