NTIC Linear Diophantine Equations

Section 3.1 Linear Diophantine Equations

The first goal for this chapter is to completely solve all linear Diophantine equations (of two variables¹). This is the question of finding solutions

x, y \in Z

of equations of the generic form

a x + b y = c for given a, b, c \in Z .

Systems of equations with several variables have a very long pedigree in nearly every culture we have documentation from; see Exercise 3.6.10 for just one exercise, and see [E.5.3, Chapter 6] for some interesting historical examples, particularly the last couple.

🔗

Historical remark 3.1.1. Diophantine and his equations.

These equations have been studied since the late Roman era, most notably by the (Greek speaking) mathematician Diophantus, from whom we derive their name, though we know little else about him. One of the most notable things about Diophantus' work is that it incorporates a proto-algebra which begins to use certain Greek letters for an unknown – an advance which, unfortunately, did not go anywhere for over a millenium.

While Diophantus studied much more complicated equations as well (as we will see), methods for solving equations like $6 x + 4 y = 2$ were pursued throughout antiquity and the medieval period – see Historical remark 2.4.7.

🔗

There are several main cases involved in the solution, as we see in the following theorem.

🔗

Theorem 3.1.2. Solutions of Linear Diophantine Equations.

Given integers $a, b, c,$ we wish to find all integer solutions $x, y$ to $a x + b y = c .$

Let $d = gcd (a, b),$ unless $a = b = 0$ in which case let $d = 0 .$ We will consider cases by ease of generating solutions.

When $c$ is not a multiple of $d$ (including if $c \neq d = 0$ ), there is no solution.
When $a$ or $b$ is zero (but not both) and the nonzero one divides $c,$ there are infinitely many solutions that require little work to obtain.
When $a, b \neq 0$ and $c = d,$ there are infinitely many solutions, but you will need to first obtain one solution in order to generate the others.
When $a, b \neq 0$ and $c$ is a nontrivial multiple of $d,$ there are infinitely many solutions that are easiest to generate by means of a solution to $a x + b y = d .$

🔗

Proof.

The details are in the following subsections.

When $c$ is not a multiple of $d\text{:}$ Subsection 3.1.1
When $a$ or $b$ is zero: Subsection 3.1.2
When $c=d\text{:}$ Subsection 3.1.3
When $c$ is a nontrivial multiple of $d\text{:}$ Subsection 3.1.4

You should definitely follow the steps with specific simple numbers to see how each proof works. Examples 3.1.3 and 3.1.4 are good models.

🔗

Subsection 3.1.1 If $c$ is not a multiple of $gcd (a, b)$

🔗

When

d \neq 0,

our previous theorems say that solving

a x + b y = c

is impossible. Can you see why? For instance, try it out with

a = 6,

b = 9,

and

c = 5 .

🔗

Reading the statement of Theorem 3.1.2 carefully shows that this case includes the situation where

a = 0 = b

but

c \neq 0 .

It is also an easy exercise to show this is impossible. You can provide full details of all these things in Exercise 3.6.8. Don't forget the division algorithm!

🔗

Subsection 3.1.2 If $a$ or $b$ is zero

🔗

Suppose

b = 0

– in which case

gcd (a, b) = a .

(Try

a = 55

as an example.)

🔗

Then we are just solving

a x = c,

so the equation is true because we already assumed that

d = a ∣ c .

All pairs

(\frac{c}{a}, y)

with integer

y

are solutions.

🔗

a = 0

the answer is analogous; write it down for yourself as practice!

🔗

Subsection 3.1.3 If $c = gcd (a, b)$

🔗

Suppose

a, b \neq 0

and

c

actually is the gcd of

a

and

b \dots

then there is some work to do. Follow along with

a = 60,

b = 42,

and

c = 6

if you wish.

🔗

Your first step should be to get that gcd

d

via the Euclidean algorithm. Then you will be able to go backwards (i.e. using the Bezout identity 2.4.1) to get one solution

(x_{0}, y_{0}) .

That is important, since now at least one

a x_{0} + b y_{0} = c

is known.

🔗

The next step is the last one; write down the entire solution set:

x = x_{0} + \frac{b}{d} n, y = y_{0} - \frac{a}{d} n for n \in Z!

🔗

There are three comments to make to finish the proof.

First, look at the structure of the solutions. The constants $a$ and $b$ have switched their ‘affiliation’ from $x$ and $y$ to $y$ and $x .$ Also note that $x$ and $y$ have $\pm$ involved. It doesn't really matter which is which (switch $- n$ for $n$ to see why), but if they have the same sign it is wrong. (When in doubt, try something and then check to see if the answers are right.)
It's easy to check that any particular solution works.

$a (x_{0} + \frac{b}{d} n) + b (y_{0} - \frac{a}{d} n) = a x_{0} + \frac{a b n}{d} + b y_{0} - \frac{a b n}{d}$

and $a x_{0} + b y_{0} = c$ by hypothesis.
Why does this give all solutions? First note that since the only common divisors of $a$ and $b$ are divisors of $d,$ the integers $\frac{b}{d}$ and $\frac{a}{d}$ must be relatively prime.

Now pick another solution $x = x^{'}, y = y^{'},$ and let's show it has the desired form. Start with

$a x^{'} + b y^{'} = c = a x_{0} + b y_{0}$

and gather terms so that

$\frac{a}{d} (x^{'} - x_{0}) = - \frac{b}{d} (y^{'} - y_{0}) .$

Since $\frac{b}{d}$ divides the right side, it divides the left side as well. Now we use Proposition 2.4.10 and the observation in the previous paragraph to see $\frac{b}{d}$ must divide the $x^{'} - x_{0}$ factor of the left-hand side, so that there exists an integer $k$ such that

$x^{'} - x_{0} = k \frac{b}{d}, which means x^{'} = x_{0} + k \frac{b}{d},$

which is exactly what we just said was the form of all solutions.

🔗

Example 3.1.3. An easy example: $6 x + 4 y = 2$ .

Trial and error tells us that $6 x + 4 y = 2$ can be solved with $x_{0} = 1, y_{0} = - 1 .$ Thus the full answer is

x = 1 + \frac{4}{2} n, y = - 1 - \frac{6}{2} n

which we may rewrite as

x = 1 + 2 n, y = - 1 - 3 n, n \in Z .

🔗

Subsection 3.1.4 If $c$ is a nontrivial multiple of the gcd

🔗

Finally, what if

c

is not the greatest common divisor but we still have solutions because

d ∣ c ?

(Follow along in Example 3.1.4 if you wish.)

First, we can write $c = d m,$ where again $d$ is the greatest common divisor.
In Subsection 3.1.3 we just saw that there must be a solution for $a x + b y = d .$ Take any solution $(x_{0}, y_{0})$ to this equation.
By hypothesis, $d = a x_{0} + b y_{0} .$ Now multiply this by $m$ to obtain

$c = d m = a x_{0} m + b y_{0} m = a (x_{0} m) + b (y_{0} m)$

which shows $x = x_{0} m, y = y_{0} m$ is a solution to the original equation $a x + b y = c .$
Finally, the surprise is that the full solution has the same form as in Subsection 3.1.3:

$x = x_{0} m + \frac{b}{d} n, y = y_{0} m - \frac{a}{d} n$

It is easy to check and the proof is very similar to the case $c = d$ (see Exercise 3.6.9). Intuitively, the reason you don't need the $m$ in the fractions is because they will just cancel anyway.

🔗

Example 3.1.4.

Try to do $15 x - 21 y = 6,$ a slightly harder one. (Hint: $d = 3;$ what are $c$ and $d ?$

Section 3.1 Linear Diophantine Equations

Historical remark 3.1.1. Diophantine and his equations.

Theorem 3.1.2. Solutions of Linear Diophantine Equations.

Proof.

Subsection 3.1.1 If c is not a multiple of gcd(a,b)

Subsection 3.1.2 If a or b is zero

Subsection 3.1.3 If c=gcd(a,b)

Example 3.1.3. An easy example: 6x+4y=2.