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

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

__Proof__.

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

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

And also there exists integer $k$ such that

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

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

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

We get

- The equation $3x+6y = 7$ has no integer solution because $(3, 6) = 3$ does not divide 7.
- 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$.