## Binary Linear Diophantine Equations

Euclid’s Algorithm (previous post) provides a means of finding solutions, if solutions exist, of the binary linear diophantine equation

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

where the ak are unequal integers (if they are equal we are essentially dealing with an equation in one variable) and solutions in integers are sought.

We begin by showing that if n1 > n2 > 0 are integers we can construct integers a1 and a2 such that

$a_{1}n_{1}+a_{2}n_{2}=(n_{1}, n_{2})$

where (n1, n2) is the greatest common divisor of n1 and n2.  We perform the Euclidean algorithm (as described in the previous post) on n1 and n2.  If the algorithm has only k = 1 step we have

$n_{1} = q_{1}n_{2}$ (q1 an integer) so $n_{1} + (1-q_{1})n_{2} = n_{2} = (n_{1}, n_{2})$

If the algorithm has k = 2 steps then

$n_{1}-q_{1}n_{2}=(n_{1},n_{2})$

More generally it is easy to show by induction that if the algorithm completes in k ≥ 2 steps then

$a_{1}=c_{k-1}$  and  $a_{2} = d_{k-1}$ where

$c_{1}=1$  ;  $d_{1}=-q_{1}$  ;  $c_{2} = -q_{2}$  ;  $d_{2}=1+q_{1}q_{2}$ and

$c_{i}=c_{i-2}-q_{i-2}c_{i-1}$  ;  $d_{i}=d_{i-2}-q_{i-2}d_{i-1}$ for i ≥ 3

Proof:  The proposition is true for k = 2 and is easily shown to be true for k = 3.  Let Pi be the proposition that

$n_{i+2} = c_{i+2}n_{1}+d_{i+2}n_{2}$

with ci and di defined as in the proposition, and for 1 ≤ i ≤ k-1.

It is easily seen that P1 is true. Suppose the proposition is true for all values of i up to some fixed value i ≤ k – 2.  Then

$n_{i+3}=n_{i+1}-q_{i+1}n_{i+2}=(c_{i+1}-q_{i+1}c_{i+2})n_{1}+(d_{i+1}-q_{i+1}d_{i+2})n_{2}$

So Pi+1 is true. Consequently Pk-1 is true and nk+1 = (n1, n2) can be expressed in the form proposed.

The construction can be easily extended to all (unequal) non-zero integers n1 and n2. We simply find integers a’1 and a’2 such that a’1|n1| + a’2|n2| = (n1, n2) then set a’1=(n1/|n1|)a1 and a’2=(n2/|n2|)a2.

The following is an obvious corollary:

Let p, m, n be non-zero integers. If p divides mn and (p, m) = 1 then p divides n.  (There are integers x, y such that xp + my = (p, m) = 1.  Hence xpn + mny = n.  Since p divides the left hand side it must divide n.)

We can now state a criterion for determining whether a solution to the diophantine equation exists and, if it does, provide a method of constructing a solution:

The linear diophantine equation a1x1 + a2x2 = a0 (with a1 and a2 non-zero and unequal) has a solution only if (a1, a2) divides a0.  If x’1 and x’2 are integers such that a1x’1 + a2x’2 = (a1, a2) then

$\displaystyle x_{1} = \frac {a_{0}x'_{1}}{(a_{1},a_{2})}$  ;   $\displaystyle x_{2} = \frac {a_{0}x'_{2}}{(a_{1},a_{2})}$  is a solution.

Proof:  if there is a solution then since (a1, a2) divides a1x1 + a2x2 it must divide a0. The rest is clear on substituting.

Knowing one solution, we can now identify all solutions:

If x10, x20 is a solution of a1x1 + a2x2 = a0 (with a1 and a2 non-zero and unequal) then x1, x2 is a solution if and only if

$\displaystyle x_{1}=x_{1}^{0}+ \frac {a_{2}t} {(a_{1},a_{2})}$  ;   $\displaystyle x_{2}=x_{2}^{0}- \frac {a_{1}t} {(a_{1},a_{2})}$   where t is any integer

Proof:  the if part is easily seen by substitution.  For the converse, consider first the case a0 = 0, noting that x1 = 0, x2 = 0 is a solution. Then

$\displaystyle x_{1}= \frac {-a_{2}x_{2}} {a_{1}} = \frac {-a'_{2}x_{2}} {a'_{1}}$  where a1 = a’1(a1, a2) ; a2 = a’2(a1, a2)

Since (a’1, a’2) = 1 (if this were not so and there were a common divisor k > 1 then k(a1, a2) would divide a1 and a2, a contradiction) then a’1 divides x2 so

$\displaystyle x_{2} = \frac {-a_{1}t} {(a_{1}, a_{2})}$ where t is some integer and $\displaystyle x_{1} = \frac {a_{2}t} {(a_{1}, a_{2})}$

The general case follows easily from the special case on noting that if x10, x20 and x1, x2 are solutions then a1(x10 -x1) + a2( x20 – x2) = 0