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

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_{1} > n_{2} > 0 are integers we can construct integers a_{1} and a_{2} such that

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

(q_{1} an integer) so

If the algorithm has k = 2 steps then

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

and where

; ; ; and

; 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

with c_{i} and d_{i} defined as in the proposition, and for 1 ≤ i ≤ k-1.

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

So P_{i+1} is true. Consequently P_{k-1} is true and n_{k+1} = (n_{1}, n_{2}) can be expressed in the form proposed.

The construction can be easily extended to all (unequal) non-zero integers n_{1} and n_{2}. We simply find integers a’_{1} and a’_{2} such that a’_{1}|n_{1}| + a’_{2}|n_{2}| = (n_{1}, n_{2}) then set a’_{1}=(n_{1}/|n_{1}|)a_{1} and a’_{2}=(n_{2}/|n_{2}|)a_{2}.

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_{1}x_{1} + a_{2}x_{2} = a_{0} (with a_{1} and a_{2} non-zero and unequal) has a solution only if (a_{1}, a_{2}) divides a_{0}. If x’_{1} and x’_{2} are integers such that a_{1}x’_{1} + a_{2}x’_{2} = (a_{1}, a_{2}) then

; is a solution.

Proof: if there is a solution then since (a_{1}, a_{2}) divides a_{1}x_{1} + a_{2}x_{2} it must divide a_{0}. The rest is clear on substituting.

Knowing one solution, we can now identify all solutions:

If x_{1}^{0}, x_{2}^{0} is a solution of a_{1}x_{1} + a_{2}x_{2} = a_{0} (with a_{1} and a_{2} non-zero and unequal) then x_{1}, x_{2} is a solution if and only if

; where t is any integer

Proof: the if part is easily seen by substitution. For the converse, consider first the case a_{0} = 0, noting that x_{1} = 0, x_{2} = 0 is a solution. Then

where a_{1} = a’_{1}(a_{1}, a_{2}) ; a_{2} = a’_{2}(a_{1}, a_{2})

Since (a’_{1}, a’_{2}) = 1 (if this were not so and there were a common divisor k > 1 then k(a_{1}, a_{2}) would divide a_{1} and a_{2}, a contradiction) then a’_{1} divides x_{2} so

where t is some integer and

The general case follows easily from the special case on noting that if x_{1}^{0}, x_{2}^{0} and x_{1}, x_{2} are solutions then a_{1}(x_{1}^{0} -x_{1}) + a_{2}( x_{2}^{0} – x_{2}) = 0

## Leave a Reply