Let $f$ be a polynomial with integer coefficients in one or more variables. An algebraic equation of the form
$$f(x_1, x_2, …, x_n) = 0,$$
whose roots are required to be integers, is called a Diophantine equation.
The simplest equations are linear Diophantine equations of the form
$$a_1x_1 + a_2x_2 + … + a_nx_n = m,$$
where $a_1, a_2, …, a_n, m \in \mathbb{Z}$.
Linear Diophantine equation
In more detail, we will observe a linear Diophantine equation in two variables, $x$ and $y$:
$$ax + by = c; \quad a, b, c \in \mathbb{Z}.$$
First of all, we will show how to solve a homogeneous linear Diophantine equation $ax + by = 0$, by using the following example.
Example 1. Find all integer solutions of the following equation:
$$2x – 3y = 0.$$
Solution. The given equation we write in the form:
$$y = \frac{2x}{3}.$$
Since $y$ must be an integer, and how $2$ and $3$ are relatively prime numbers, that $x$ must be a multiple of $3$. Therefore, $x = 3k$, where $k \in \mathbb{Z}$. If we include it in the given equation, we will obtain $y = 2k, k \in \mathbb{Z}$. Therefore,
$$x = 3 k, \quad y = 2 k, \quad k \in \mathbb{Z},$$
is the set of all solutions of the given equation. We can see that the equation has infinitely many solutions.
In general, if we have the equation
$$ax + by = 0, \quad a^2 + b^2 \neq 0,$$
then
$$x = – \frac{by}{a},$$
from where it follows $y = – at, t \in \mathbb{Z}$ and $x = bt, t \in \mathbb{Z}$. Therefore, with $x = bt$ and $y = – at, t \in \mathbb{Z}$ is given the set of all integer solutions of the equation $ax + by = 0$.
We can show now how to solve a non-homogeneous linear Diophantine equation in two variables $ax + by = c, c \neq 0$. The basic idea of solving these equation it consists in the fact that we solve its associated homogeneous linear equation $ax + by = 0$. Consider the following example.
Example 2. Solve the following Diophantine equation:
$$7x – 9y = 3.$$
Solution.
First of all, we will find any integer solution of the given equation. Such a solution surely exists because $\gcd(7, 9) = 1$ and $3$ is divisible by $1$. One solution of the given equation is $x_0 = 3, y_0 = 2$. Any concrete solution of the equation is called a particular solution. Therefore, $x_0 = 3, y_0 = 2$ is one particular solution of the given equation, so the following is valid:
$$7x_0 – 9 y_ 0 = 3.$$
If from the given equation we subtract the previous equality, we will obtain the following:
$$7( x – x_0) – 9 (y -y_0) = 0,$$
and that is a homogeneous linear equation. Its solution is:
$$x – x_0 = 9 t, \quad y – y_0 = 7t, $$
that is,
$$x = 9t + x_0, \quad y = 7t + y_0.$$
Substituting $x_0$ and $y_0$ to the solution of a homogeneous equation, we obtain all integer solutions of the given equation:
$$x = 3 + 9t, \quad y = 2 + 7t, \quad t \in \mathbb{Z}.$$
In general, solution of the non-homogeneous linear Diophantine equation is equal to the integer solution of its associated homogeneous linear equation plus any particular integer solution of the non-homogeneous linear equation, what is given in the form of a theorem. We write:
$$x = x_0 + bt, \quad y = y_0 – at, \quad t \in \mathbb{Z}.$$
However, there appears a problem, that is, the question of whether each of the linear Diophantine equation has integer solutions. For example, the equation $4x + 2y = 13$ has no integer solutions because its left side is an even number, $\forall x, y \in \mathbb{Z}$, and its right side is an odd number, so, there are no integers $x$ and $y$ that satisfy the specified equation.
Therefore, we must first determine the requirement with which a linear Diophantine equation has integer solutions.
The following theorem gives us a condition of resolvability of Diophantine equations.
Theorem 1. The equation $ax + by = c$, $a^2 + b^2 \neq 0$, $a, b, c \in \mathbb{Z}$ has integer solution if and only if $\gcd(a, b) | c$.
To search for the greatest common measure of two numbers, we use the Euclidean algorithm, and it relies on the divisibility theorem:
For $a \in \mathbb{Z}$ and $b \in \mathbb{N}$ there exist unique integers $q$ and $r$ such that $a = bq + r$ and $0 \le r < b$.
The number $q$ is called the quotient and $r$ is called the remainder. The quotient and remainder defined by the theorem above are unique. If the remainder is $0$, then $a = bq$, therefore, by the definition of divisibility, $b$ divides $a$.
Now we are going to write a scheme of the Euclidean algorithm. On the left of the page we will indicate the ordered pairs of numbers to which we will apply the equality from the divisibility theorem:
$$(a, b), a = bq_1 + r_1, r_1 < b $$
$$(b, r_1), b = r_1 q_2 + r_2 r_2 < r_1$$
$$(r_1, r_2), r_1 = r_2 q_3 + r_3, r_3 < r_2$$
$$(r_3, r_3), r_2 = r_3q_4 + r_4, r_4 < r_3 $$
$$\vdots $$
$$(r_{k-2}, r_{k-1}), r_{k-2} = r_{k-1}q_k + r_k, r_k < r_{k-1}$$
$$(r_{k-1}, r_k ), r_{k-1} = r_k q_{k +1} + 0$$
The remainder $r_k$ is the greatest common measure of $a$ and $b$. From the first equality we can see that the remainder $r_1$ we can write as a linear combination of $a$ and $b$, from the second equality we can see that the remainder $r_2$ can be written as a linear combination of $ r_1 $and $a$, and thus as a linear combination of $a$ and $b$. So we can see that the each reminder $r_i$ can be written as a linear combination of $a$ and $b$. Specifically, this is true for $r_k$, so we conclude that the following is valid:
Theorem 2. For each two integers $a$ and $b$ there exist integers $x_0$ and $y_0$ such that
$$ax_0 + by_0 = \gcd (a, b).$$
Using the previous theorem we can determine a particular solution of the Diophantine equation (by multiplying the equation with $ \frac{c}{\gcd( a, b)})$ .
If we agree that numbers $a$ and $b$ are relatively prime numbers, then from the Theorem 2. follows:
Theorem 3. If $a$ and $b$ are relatively prime integers, then there exist integers $x_0$ and $y_0$ such that
$$ax_0 + by_0 = 1.$$
Example 3. Solve the following equation in the set of integers:
$$858 x + 253 y = 33.$$
Solution.
How the particular solution is not apparent, we will apply the Euclidean algorithm on the ordered pair $(a, b) = (858, 253)$ to find it.
We have:
$$858 = 253 \cdot 3 + 99, \quad a = 3 b + r_1$$
$$253 = 99 \cdot 2 + 55, \quad b = 2 r_1 + r_2$$
$$99 = 55 \cdot 1 + 44, \quad r_1 = r_2 + r_3 $$
$$55 = 44 \cdot 1 + 11, \quad r_2 = r_3 + r_4$$
$$44 = 11 \cdot 4, \quad r_3 = 4r_4$$
Since $\gcd ( 858, 253) = r_4 = 11$ and $11 | 33$, then, by the Theorem 1., the equation has solutions.
We see that the remainders we can express in the following way:
$$99 = 858 – 253 \cdot 3$$
$$55 = 253 – 99 \cdot 2$$
$$44 = 99 – 55 \cdot 1$$
$$11 = 55 – 44 \cdot 1$$
It follows:
$$11= 55 – 44 \cdot 1 $$
$$= 55 – 1 \cdot (99 – 55 \cdot 1)$$
$$= 2 \cdot 55 – 99$$
$$= 2 \cdot (253 – 99\cdot 2) -99$$
$$= 2 \cdot 253 – 5 \cdot 99$$
$$= 2 \cdot 253 – 5 \cdot (858 – 253 \cdot 3)$$
$$= 17 \cdot 253 – 5 \cdot 858$$
In our equation $c = 33$, so we have (by the Theorem 2.):
$$11 = 17 \cdot 253 – 5 \cdot 858 / \cdot 3$$
$$33 = 51 \cdot 253 – 15 \cdot 858$$
If we write it in the startup form, then we have:
$$858 \cdot (- 15) + 253 \cdot 51 =33,$$
that is, a particular solution is $(x_0, y_0) = ( – 15, 51)$.
The associated homogeneous linear equation has a form:
$$858 x + 253 y = 0.$$
It follows $y = – \frac{858}{253}x \in \mathbb{Z}$. Therefore, the solution of the associated homogeneous equation is (by the example 1.):
$$x = -253 t, \quad t \in \mathbb{Z},$$
$$y =858 t, \quad t \in \mathbb{Z}.$$
Finally, the solution of the initial equation $858 x + 253 y = 33$ is:
$$x = -15 – 253 t, \quad t \in \mathbb{Z},$$
$$y = 51 + 858 t, \quad t \in \mathbb{Z}.$$
The Euler Method
The idea of this method we will show by using the following example.
Example 4. How much cinema tickets we can buy for 1490 dollars , if tickets cost 30 and 50 dollars? How many solutions are there?
Solution.
With $x$ we will denote the number of tickets for 30 dollars and with $y$ number of tickets for 50 dollars. From the terms of the task we get the Diophantine equation
$$30 x + 50 y = 1490,$$
that is,
$$3x + 5y = 149,$$
with the conditions $x \ge 0$ and $y \ge 0$. We express the unknown whose coefficient is lower by the absolute value; in this case that is $x$:
$$3x = 149 – 5y \Longrightarrow x = \frac{149 – 5y}{3} \Longrightarrow x = 49 -y + \frac{2 -2y}{3}.$$
Since we are looking for integer solutions, $x$ will be an integer if and only if the expression $\frac{2 – 2y}{3}$ is an integer, that is, $\frac{2 – 2y}{3} = v$, where $v \in \mathbb{Z}$. By transforming, we obtain a Diophantine equation:
$$2 – 2y = 3v.$$
Now we will express the unknown $y$:
$$y = 1 – \frac{3v}{2}.$$
$y$ will be an integer if and only if $\frac{3v}{2}$ is an integer, that is, $\frac{3v}{2} = w, w \in \mathbb{Z}$. Now we have:
$$\frac{3v}{2} = w \Longrightarrow 3v = 2w \Longrightarrow 3v – 2w =0.$$
Now we must solve a homogeneous linear Diophantine equation $3v – 2w= 0$. Considering the example 1., the solution is:
$$v = 2t, \quad t \in \mathbb{Z},$$
$$w = 3t, \quad t \in \mathbb{Z}.$$
Now we must include it in the expressions for $x$ and $y$. Therefore, we have:
$$y = 1 – w = 1 – 3t,$$
$$x =49 – y + v = 49 – (1 – 3t) + 2t =48 + 5t.$$
Finally,
$$x = 48 + 5t,$$
$$y=1 -3t, t \in \mathbb{Z}$$
We still have to apply the conditions $x \ge 0$ and $y \ge 0$ and see how many possible solutions are there. This means that it must be valid:
$$48 + 5t \ge 0 $$
and
$$1 – 3t \ge 0,$$
that is,
$$-\frac{48}{5} \le t \le \frac{1}{3}.$$
We take into account only integers between $-\frac{48}{5}$ and $\frac{1}{3}$, that is, $t=-9, -8, -7, -6, -5, -4, -3, -2, -1, 0$. The requested pairs of integers $(x,y)$ are:
$$(3, 28) , (8, 25), (13, 22), (18, 19), (23, 16), (28, 13), (33, 10), (38, 7), (43, 4), (48, 1).$$
Therefore, there is $10$ possible solutions, that is, it is possible on $10$ ways to buy cinema tickets that cost $30$ and $50$ dollars for $1490$ dollars.
