Latest Tweets

Linear Diophantine equations

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.