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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s