# Linear Diophantine equations

Let be a polynomial with integer coefficients in one or more variables. An algebraic equation of the form

whose roots are required to be integers, is called a Diophantine equation.

The simplest equations are linear Diophantine equations of the form

where .

Linear Diophantine equation

In more detail, we will observe a linear Diophantine equation in two variables, and :

First of all, we will show how to solve a homogeneous linear Diophantine equation , by using the following example.

Example 1.  Find all integer solutions of the following equation:

Solution. The given equation we write in the form:

Since must be an integer, and how and are relatively prime numbers, that must be a multiple of . Therefore, , where . If we include it in the given equation, we will obtain . Therefore,

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

then

from where it follows and . Therefore, with and is given the set of all  integer solutions of the equation .

We can show now how to solve a non-homogeneous  linear Diophantine equation in two variables . The basic idea of solving these equation it consists in the fact that we solve its associated homogeneous linear equation . Consider the following example.

Example 2. Solve the following Diophantine equation:

Solution.

First of all, we will find any integer solution of the given equation. Such a solution surely exists because and is divisible by . One solution of the given equation is . Any concrete solution of the equation is called a particular solution. Therefore,  is one particular solution of the given equation, so the following is valid:

If  from the given equation we subtract the previous equality, we will obtain the following:

and that is a homogeneous linear equation. Its solution is:

that is,

Substituting and to the solution of a homogeneous equation, we obtain all integer solutions of the given equation:

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:

However, there appears a problem, that is, the question of whether each of the linear Diophantine equation has integer solutions. For example, the equation has no integer solutions because its left side is an even number, , and its right side is an odd number, so, there are no integers and 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 , , has integer solution if and only if .

To search for the greatest common measure of two numbers, we use the Euclidean algorithm, and it relies on the divisibility theorem:

For and there exist unique integers and such that and .

The number is called the quotient and is called the remainder. The quotient and remainder defined by the theorem above are unique. If the remainder is , then , therefore, by the definition of divisibility, divides .

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:

The remainder is the greatest common measure of and . From the first equality we can see that the remainder we can write as a linear combination of and , from the second equality we can see that the remainder can be written as a linear combination of and , and thus as a linear combination of and . So we can see that the each reminder can be written as a linear combination of and . Specifically, this is true for , so we conclude that the following is valid:

Theorem 2. For each two integers and there exist integers and such that

Using the previous theorem we can determine a particular solution of the Diophantine equation (by multiplying the equation with .

If we agree that numbers and are relatively prime numbers, then from the Theorem 2. follows:

Theorem 3.  If and are relatively prime integers, then there exist integers and such that

Example 3. Solve the following equation in the set of integers:

Solution.

How the particular solution is not apparent, we will apply the Euclidean algorithm on the ordered pair to find it.

We have:

Since and , then, by the Theorem 1., the equation has solutions.

We see that the remainders we can express in the following way:

It follows:

In our equation , so we have (by the Theorem 2.):

If we write it in the startup form, then we have:

that is, a particular solution is .

The associated homogeneous linear equation has a form:

It follows . Therefore, the solution of the associated homogeneous equation is (by the example 1.):

Finally, the solution of the initial equation is:

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 we will denote the number of tickets for 30 dollars and with number of tickets for 50 dollars. From the terms of the task we get the Diophantine equation

that is,

with the conditions and . We express the unknown whose coefficient is lower by the absolute value; in this case that is :

Since we are looking for integer solutions, will be an integer if and only if the expression is an integer, that is, , where . By transforming, we obtain a Diophantine equation:

Now we will express the unknown :

will be an integer if and only if is an integer, that is, . Now we have:

Now we must solve a homogeneous linear Diophantine equation . Considering the example 1., the solution is:

Now we must include it in the expressions for and . Therefore, we have:

Finally,

We still have to apply the conditions and and see how many possible solutions are there. This means that it must be valid:

and

that is,

We take into account only integers between and , that is, . The requested pairs of integers are:

Therefore, there is possible solutions, that is, it is possible on ways to buy cinema tickets that cost and dollars for dollars.

Shares