Linear Diophantine Equations

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 a_k and (a₁, a₂).

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₁, a₂, … ,a_n are zero they have greatest common divisor (a₁, … ,a_n). 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 a_k using simple algebra and Euclid’s algorithm.

About these ads

This entry was posted on February 29, 2012 at 10:54 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Some Classical Maths

Linear Diophantine Equations

Leave a Reply Cancel reply

Follow “Some Classical Maths”