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 a_k 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 n₁ > n₂ > 0 are integers we can construct integers a₁ and a₂ such that

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

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

$n_{1} = q_{1}n_{2}$ (q₁ 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 P_i be the proposition that

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

with c_i and d_i defined as in the proposition, and for 1 ≤ i ≤ k-1.

It is easily seen that P₁ 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 P_i+1 is true. Consequently P_k-1 is true and n_k+1 = (n₁, n₂) can be expressed in the form proposed.

The construction can be easily extended to all (unequal) non-zero integers n₁ and n₂. We simply find integers a’₁ and a’₂ such that a’₁|n₁| + a’₂|n₂| = (n₁, n₂) then set a’₁=(n₁/|n₁|)a₁ and a’₂=(n₂/|n₂|)a₂.

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 a₁x₁ + a₂x₂ = a₀ (with a₁ and a₂ non-zero and unequal) has a solution only if (a₁, a₂) divides a₀. If x’₁ and x’₂ are integers such that a₁x’₁ + a₂x’₂ = (a₁, a₂) 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 (a₁, a₂) divides a₁x₁ + a₂x₂ it must divide a₀. The rest is clear on substituting.

Knowing one solution, we can now identify all solutions:

If x₁⁰, x₂⁰ is a solution of a₁x₁ + a₂x₂ = a₀ (with a₁ and a₂ non-zero and unequal) then x₁, x₂ 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 a₀ = 0, noting that x₁ = 0, x₂ = 0 is a solution. Then

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

Since (a’₁, a’₂) = 1 (if this were not so and there were a common divisor k > 1 then k(a₁, a₂) would divide a₁ and a₂, a contradiction) then a’₁ divides x₂ 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 x₁⁰, x₂⁰ and x₁, x₂ are solutions then a₁(x₁⁰ -x₁) + a₂( x₂⁰ – x₂) = 0

This entry was posted on January 4, 2012 at 9:22 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

Binary Linear Diophantine Equations

Leave a Reply Cancel reply

Follow “Some Classical Maths”