Linear Diophantine Equations

In this section, we discuss equations in two variables called diophantine equations. These kinds of equations require integer solutions. The goal of this section is to present the set of points that determine the solution to this kind of equations. Geo-metrically speaking, the diophantine equation represent the equation of a straight line. We need to find the points whose coordinates are integers and through which the straight line passes.

Definition 1. A linear equation of the form

$ax + by = c$

where $a$, $b$ and $c$ are integers is known as a linear diophantine equation. Note that a solution to the linear diophantine equation ($x_0, y_0$) requires $x_0$ and $y_0$ to be integers. The following theorem describes the case in which the diophantine equation has a solution and what are the solutions of such equations.

Theorem 1. The equation $ax + by = c$ has integer solutions if and only if $d | c$ where $d = (a, b)$. If the equation has one solution $x = x_0$, $y = y_0$, then there are infinitely many solutions and the solutions are given by

$x = x_0 + ( \frac{b}{d} )t $

$y = y_0 - ( \frac{a}{d})t $

where t is an arbitrary integer.

Proof.
Suppose that the equation $ax + by = c$ has integer solution $x$ and $y$  Thus since $d | a $ and $d | b$, then

$d | (ax + by) = c$. 

Now we have to prove that if $d | c$, then the equation has integral solution. Assume that $d | c$. By theorem 3 (in GCD), there exist integers $m$ and $n$ such that

 $d = am + bn$. 

And also there exists integer $k$ such that

$c = dk$. 

Now since $c = ax + by$, we have

$ \begin{align} c &= dk \\ &= (ma + nb)k \\ & = a(km) + b(nk) \end{align} $.

Hence a solution for the equation $ ax + by = c$ is 

$x_0 = km$ and $y_0 = kn$.

What is left to prove is that we have infinitely many solutions. Let

$x = x_0 + ( \frac{b}{d})t$ and $y = y_0 - ( \frac{a}{d}) t$. 

We have to prove now that $x$ and $y$ are solutions for all integers $t$. Notice that

$ \begin{align} ax + by &= a(x_0 + ( \frac{b}{d})t) + b(y_0 - ( \frac{a}{d})t) \\ &= ax_0 + by_0 \\ & = c \end{align}$.

We now show that every solution for the equation $ax + by = c$ is of the form

$x = x_0 + ( \frac{b}{d})t$ and $y = y_0 - ( \frac{a}{d})t$.

Notice that since $ax_0 + by_0 = c$, we have 

$a(x - x_0) + b(y - y_0) = 0$.

Hence

$a(x - x_0) = b(y - y_0)$.

Dividing both sides by $d$, we get

$ \frac{a}{d} (x-x_0) = \frac{b}{d} (y - y_0) $

Notice that $( \frac{a}{d}, \frac{b}{d} ) =1$ and thus we get by Lemma (a, b, c are positive integers such that $(a, b) = 1$ and $a | bc$, then $a | c$) that $ \frac{a}{d} | y-y_0 $. As a result, there exists an integer $t$ such that $y=y_0 - ( \frac{a}{d} )t$.  Now substituting $y - y_0$ in the equation

$a(x - x_0) = b(y - y_0)$. 

We get

$x = x_0 + ( \frac{b}{d})t $.

Example.

1. The equation $3x+6y = 7$ has no integer solution because $(3, 6) = 3$  does not divide 7.
2. There are infinitely many integer solutions for the equation $4x +6y = 8$ because $(4, 6) = 2 | 8$. We use the Euclidean algorithm to determine $m$ and $n$  where $4m + 6n = 2$. It turns out that $4(-1) + 6(1) = 2$. And also $8 = 2.4$. Thus $x_0 = 4.(-1) = -4$ and $y_0 = 4.1 = 4$ is a particular solution. The solutions are given by $x = -4 + 3t$ and $y = 4 - 2t$ for all integers $t$.

Share :