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

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