Latest Tweets

Free math worksheets

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

    \[a_1 x \equiv b_1 \pmod{m_1}.\]

    \[a_2 x \equiv b_2 \pmod{m_2}.\]

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:

    \[5x \equiv 8 \pmod 2,\]

    \[7x \equiv 3 \pmod 5.\]

Solution.

Firstly, we will determine a solution to the congruence 7x \equiv 3 \pmod 5. Since \gcd (7, 5) =1, that the congruence has a unique solution.

The congruence we write in the equivalent way:

    \[7x - 5y = 3.\]

The one particular solution to the equation above is x_0 = 2, y_0 = -3, so 7x_0 - 5y_0 = 3 is valid. By subtracting the obtained equations we obtain

    \[7(x - x_0) - 5 (y - y_0) = 0.\]

It follows

    \[x - x_0 = 5t_1, \quad k_1 \in \mathbb{Z},\]

that is,

    \[x = 2 + 5k_1, \quad k_1 \in \mathbb{Z}.\]

Substituting that into the first congruence gives:

    \[5 ( 2 + 5k_1) \equiv 8 \pmod 2,\]

that is,

    \[25 k_1 \equiv 2 \pmod 2.\]

The associated linear Diophantine equation of the congruence above is:

    \[25 k_1 - 2 y = 2.\]

One particular solution to the equation above is k_1^0  = 2, y_0 = 24, so

    \[k_1 = 2 + 2k_2, \quad k_2 \in \mathbb{Z}.\]

If we substituting that into x = 2 + 5k_1, then we obtain

    \[x = 2 + 5 (2 + 2k_2) = 12 + 10 k_2,\]

that is,

    \[x \equiv 2 \pmod{10},\]

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 m_1, m_2, \ldots, m_r be nonzero integers that are pairwise relatively prime. Then, for any integers a_1, a_2, \ldots, a_r, the system of congruences

    \[x \equiv a_1 \pmod{m_1}\]

    \[x \equiv a_2 \pmod{m_2}\]

    \[\vdots\]

    \[x \equiv a_r \pmod{m_r}\]

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

    \[x \equiv x_0 \pmod{m_1m_2 \cdots m_r}.\]

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

Proof.

Put M= m_1m_2 \cdots m_r, and M_j =\frac{M}{m_j}, for j=1, \ldots, r.

Then \gcd(M_j, m_j) = 1. Let y_j be an inverse of M_j modulo m_j. Then we have

    \[M_jy_j \equiv 1 \pmod{m_j},\]

by the definition of the inverse.

Let now

    \[x =a_1 M_1x_1 + a_2M_2x_2 + \ldots + a_rM_rx_r.\]

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

If now x and y are two simultaneous solutions to the given system, then x \equiv y \pmod{m_j} for j= 1, \ldots, r, so because m_j are pairwise relatively prime , we obtain that x \equiv y \pmod M, that is, the solution is a unique congruence class modulo M, and the value of x computed above is in that class.

Systems that have no solution are said to be inconsistent.

Example 2. Solve the following system of congruences:

    \[x \equiv 2 \pmod 3\]

    \[x \equiv 3 \pmod 5\]

    \[x \equiv 2 \pmod 7.\]

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:

    \[m_1 = 3, \quad m_2 = 5, \quad m_3 = 7,\]

so,

    \[M = m_1 m_2 m_3 = 3 \cdot 5 \cdot 7 =  105,\]

and

    \[M_1 = \frac{M}{m_1} = \frac{105}{3} = 35,\]

    \[M_2 =  \frac{M}{m_2} = \frac{105}{5} = 21,\]

    \[M_3 = \frac{M}{m_3} = \frac{105}{7} = 15.\]

Now the linear congruences

    \[M_1 y_1 \equiv 1 \pmod 3 \Longrightarrow  35 y_1 \equiv 1 \pmod 3\]

    \[M_2 y_2 \equiv 1 \pmod 5 \Longrightarrow 21 y_2 \equiv 1 \pmod 5,\]

and

    \[M_3 y_3 \equiv 1 \pmod 7 \Longrightarrow 15 y_3 \equiv 1 \pmod 7\]

are satisfied by y_1 = -1, y_2 = 1 and y_3 = 1, respectively.

Thus, a solution to the given system is given by

    \[\begin{aligned} x &= ( 2 \cdot 35 \cdot (-1)) + (3 \cdot 21 \cdot 1 ) + (2 \cdot 15 \cdot 1) \\ &= -70 + 63 + 30 \\ &=  23 \\ \end{aligned}\]

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

    \[x = 23 + 105 k, \quad k \in \mathbb{Z}.\]

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:

    \[x \equiv 3 \pmod{10},\]

    \[x \equiv 8 \pmod{15},\]

    \[x \equiv 5 \pmod{84}.\]

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 10 = 2 \cdot 5, 15 = 3 \cdot 5 and 84  = 2 \cdot 2 \cdot 3 \cdot 7, the first congruence is equivalent to

    \[x \equiv 3 \pmod 2 \quad & \mbox{and} \quad x \equiv 3 \pmod 5,\]

the second congruence is equivalent to

    \[x \equiv 2 \pmod 3 \quad &\mbox{and} \quad x \equiv 3 \pmod 5,\]

and the third congruence is equivalent to

    \[x \equiv 5 \pmod 4 \quad & \mbox{and} \quad x \equiv 5 \pmod 3 \quad & \mbox{and} \quad x \equiv 5 \pmod 7.\]

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

    \[x \equiv 1 \pmod 4,\]

    \[x \equiv 2 \pmod 3,\]

    \[x \equiv 3 \pmod 5,\]

    \[x \equiv 5 \pmod 7.\]

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

We have m_1 = 4, m_2 = 3, m_3 = 5 and m_4 = 7, therefore

    \[M = 4 \cdot 3 \cdot 5 \cdot 7 = 420.\]

It follows

    \[M_1 = \frac{M}{m_1} = \frac{420}{4} = 105,\]

    \[M_2 = \frac{M}{m_2} = \frac{420}{3} = 140,\]

    \[M_3 = \frac{M}{m_3} = \frac{420}{5} = 84,\]

    \[M_4  = \frac{M}{m_4} = \frac{420}{7} = 60.\]

Now the linear congruences

    \[105  y_1 \equiv 1 \pmod 4,\]

    \[140 y_2 \equiv 1 \pmod 3,\]

    \[84y_3  \equiv 1 \pmod 5\]

and

    \[60 y_4 \equiv 1 \pmod 7\]

are satisfied by y_1 = 1, y_2 = 2, y_3= -1 and y_4 = 2, respectively.

Thus, a solution to the given system is given by

    \[\begin{aligned} x &= (1 \cdot 105 \cdot 1) + (2 \cdot 140 \cdot 2) + (3 \cdot 84 \cdot (-1)) + (5 \cdot 60 \cdot 2) \\ &= 1013 \\ & \equiv 173 \pmod{420}.\\ \end{aligned}\]

 

Shares