Latest Tweets

Free math worksheets

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:

    \[\begin{aligned} (a, b) & \quad & a = bq_1 + r_1 & \quad & r_1 < b \\ (b, r_1) & \quad & b = r_1 q_2 + r_2 & \quad & r_2 < r_1 \\ (r_1, r_2) & \quad & r_1 = r_2 q_3 + r_3 & \quad & r_3 < r_2 \\ (r_3, r_3) & \quad & r_2 = r_3q_4 + r_4 & \quad & r_4 < r_3 \\ \vdots \\ (r_{k-2}, r_{k-1}) & \quad & r_{k-2} =  r_{k-1}q_k + r_k & \quad & r_k < r_{k-1} \\ (r_{k-1}, r_k )& \quad & r_{k-1} = r_k q_{k +1} + 0 \end{aligned}\]

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_1and 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:

    \[\begin{aligned} 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 \\ \end{aligned}\]

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,

    \[\begin{cases} x = 48 + 5t, \\ y=1 -3t, & t \in \mathbb{Z} \\ \end{cases}\]

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.

 

Shares