# Solving linear congruences

A linear congruence is an equation of the form

Lemma. Solving the congruence is equivalent to solving the linear Diophantine equation .

Since we already know how to solve linear Diophantine equations in two variables, we can apply that knowledge to solve linear congruences.

Let be any concrete solution to the above equation. Then is valid. If it is now any number from the equivalence class determined with , then from follows that , so , which means that is also the solution to .

Therefore, if has a solution, then there is infinitely many solutions.

A linear congruence   is equivalent to

for some integer .

This is a linear Diophantine equation and it has a solution if and only if divides . If this condition is met, then all solutions are given with the formula:

for any integer .

This means that a linear congruence also has infinitely many solutions which are given in the form:

We must now see how many distinct solutions are there. For this purpose, we take any two solutions from that set:

We have now:

Since divides , that by the theorem 6.

is valid.

Therefore, and are congruent modulo if and only if and are congruent modulo . This means that there are exactly distinct solutions.

Write this in the form of a theorem.

Theorem 1. Let and be natural numbers, and an integer. The congruence has solutions if and only if divides . If this condition is satisfied, then the above congruence has exactly solutions modulo , and that

If , then the linear congruence has no solutions.

For instance, solve the congruence . Since and , there are no solutions.

From the theorem above follows:

Theorem 2. If the number is a prime number, and if is not divisible by , then the congruence always has a solution, and that solution is unique.

This entails that a set of remainders by dividing by , whit addition and multiplication , makes the field. This field is denoted by .

There are several methods for solving linear congruences; connection with  linear Diophantine equations, the method of transformation of coefficients, the Euler’s method, and a method that uses the Euclidean algorithm…

Connection with  linear Diophantine equations

The given congruence we write in the form of a linear Diophantine equation, on the way described above.

Example 1. Solve the following congruence:

Solution.

Since , that, by the theorem 1., the congruence has a unique solution.

means that must be divisible by , that is, there must be an integer such that

that is,

The one particular solution to the equation above is , so is valid.

By subtracting obtained equations we have:

It follows: .

Therefore, solution to the congruence  is

that is,

or

Method of transformation of coefficients

The method of  transformation of coefficients consist in the fact that to the given equation we add or subtract a well selected true congruence. In this way we obtain the congruence which also specifies the class that is the solution.

Example 2. Solve the following congruence:

Solution.

Since , that the given congruence has a unique solution. To the above congruence  we add the following congruence

and we will obtain

By dividing the congruence by , we have

or

and that is the solution to the given congruence.

Method that uses the Euclidean algorithm

If we need to solve the congruence , we must first find the greatest common divisor by using the Euclidean algorithm. To the solution to the congruence , where and , can be reached by applying a simple recursive relation:

where is the least non-zero remainder and are quotients in the Euclidean algorithm.

In this case, is a solution to the congruence , so is the solution to the congruence .

The solution to the congruence is now given with:

Example 3. Solve the following congruence:

Solution.

We must first find by using the Euclidean algorithm:

Therefore, . Since , that the given congruence has solutions ( it has exactly two solutions). We have , and .

We need now aplly the above recursive relation:

We obtain that

is the solution to the congruence

so,

that is,

is the solution to the congruence

Finally, solutions to the given congruence are

Solutions we can write in the equivalent form:

Euler’s method

The Euler’s method consist in the fact that we use the Euler’s theorem. Given the congruence

Suppose that . By the Euler’s theorem

is valid.

Since always

is valid, that we obtain

By comparing the above congruence with the initial congruence, we can show that

is the solution to the initial congruence.

Example 4. Solve the following congruence:

Solution.

By using the formula

we obtain

Since , that it follows

We have now:

By substituting it in we obtain

that is,

and that is the solution to the given congruence.

Shares