# System of linear congruences

In this lesson we will show how to solve a systems of linear congruences with one unknown, that is, systems of the shape

The idea is simple. Solve first one of them and then find its solutions that also satisfy the another.

Example 1. Solve the following system of linear congruences:

Solution.

Firstly, we will determine a solution to the congruence . Since , that the congruence has a unique solution.

The congruence we write in the equivalent way:

The one particular solution to the equation above is , so is valid. By subtracting the obtained equations we obtain

It follows

that is,

Substituting that into the first congruence gives:

that is,

The associated linear Diophantine equation of the congruence above is:

One particular solution to the equation above is , so

If we substituting that into , then we obtain

that is,

and that is the solution to the given system of linear congruences.

If we need to solve a system of three linear congruences with one unknown, then we need first solve a system of two linear congruences, and then see which of the obtained solutions also satisfy  the third congruence. With the increase in the number of congruences, the process becomes more complicated. That help us the following theorem.

Theorem (the Chinese remainder theorem) Let be nonzero integers that are pairwise relatively prime. Then, for any integers , the system of congruences

has a solution. If is the one solution, then all solutions are given by

A proof of the Chinese remainder theorem gives us an algorithm for solving a system of linear congruences with one unknown.

Proof.

Put , and , for .

Then . Let be an inverse of modulo . Then we have

by the definition of the inverse.

Let now

Then is a simultaneous  solution to the given system of linear congruences.

If now and are two simultaneous solutions to the given system, then for , so because are pairwise relatively prime , we obtain that , that is, the solution is a unique congruence class modulo , and the value of computed above is in that class.

Systems that have no solution are said to be inconsistent.

Example 2. Solve the following system of congruences:

Solution.

Notice first that the moduli are pairwise relatively prime, therefore, we can use the Chinese remainder theorem. In the notation of the Chinese remainder theorem, we have:

so,

and

Now the linear congruences

and

are satisfied by , and , respectively.

Thus, a solution to the given system is given by

modulo . So the solutions form the congruence class of modulo , that is, the general solution is

What if moduli are not pairwise relatively prime? The Chinese remainder theorem does not work in this case. If we have a congruence with a modulus which is divisible by at least two primes, then we can split this single congruence into several congruences as long as the new moduli  are pairwise relatively prime and their product is the original modulus. After this procedure, we can use the Chinese remainder theorem.

Example 3. Solve the following system of congruences:

Solution.

The moduli in this problem are not pairwise relatively prime, so we can not apply the Chinese remainder theorem directly, and it is possible that such a system has no solution.

Since , and , the first congruence is equivalent to

the second congruence is equivalent to

and the third congruence is equivalent to

Therefore, the original system is equivalent to the following system:

Now we can apply the method of the proof of the Chinese remainder theorem.

We have and , therefore

It follows

Now the linear congruences

and

are satisfied by and , respectively.

Thus, a solution to the given system is given by

Shares