Simultaneous Linear Congruences- Chinese Remainder Theorem (CRT)

We will now consider the solutions of simultaneous congruences. In the 1st century AD, the Chinese mathematician Sun-Tsu considered problems like ‘find a number which leaves remainders 2,3,2 when divided by 3,5,7 respectively’. Equivalently, he wanted to find $x$ such that the congruences

$$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod {5}, \quad x \equiv 2 \pmod {7}$$

 

are simultaneously true. Note that if $x_0$ is any solution, then so is $x_0 +(3 \times 5 \times 7)t$ for any integer $t$, so the solutions form a union of congruence classes mod (105).

We shall show that in this particular case the solutions form a single congruence class, but in other cases we may find that there are several classes or none: as an example, the simultaneous congruences

$$x \equiv 3 \pmod {9},\quad  x \equiv 2 \pmod {6}$$

have no solutions, for if $x \equiv 3 \pmod {9}$ then 3 divides $x$, whereas if $x \equiv 2\pmod {6}$ then 3 does not divide $x$. The difficulty here is that the moduli 9 and 6 have a factor 3 in common, so both congruences have implications about the congruence class of $x \pmod {3}$, and in this particular case these implications are mutually inconsistent. To avoid this type of difficulty, we will initially restrict our attention to cases like our first example, where the moduli are mutually coprime. 

  

Fortunately, the following result, known as the Chinese Remainder Theorem, gives a very satisfactory solution to this type of problem.

The Chinese Remainder Theorem (CRT) is a fundamental theorem in number theory with applications in various fields such as cryptography, computer science, and pure mathematics. It provides a solution to simultaneous congruences.

Statement:

Let $n_1, n_2, \ldots, n_k$be positive integers that are pairwise coprime (i.e., for every $\neq j$, $\text{gcd}(n_i, n_j) = 1$), and let $a_1, a_2, \ldots, a_k$be any integers. Then the system of simultaneous congruences

$$\begin{align*} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align*}$$

has a unique solution modulo $N = n_1 \times n_2 \times \ldots \times n_k$

Proof:

1. Existence of a Solution:

   Let $N = n_1 \times n_2 \times \ldots \times n_k$For each $i$, let $N_i = N / n_i$. Since $n_i$and $N_i$are coprime, there exist integers $b_i$ such that $N_i b_i \equiv 1 \pmod{n_i}$. Now, let $x = \sum_{i=1}^{k} a_i N_i b_i$ We claim that $x$ is a solution to the system of congruences.

   Indeed, for any $i$, we have:

   $$x \equiv a_i N_i b_i \equiv a_i 1  \equiv a_i \pmod{n_i}$$

   Thus, $x$ satisfies all the congruences.

2. Uniqueness of Solution:

   Suppose $x_1$ and $x_2$ are two solutions to the system of congruences. Then $x_1\equiv x_2(\mathrm{m}\mathrm{o}\mathrm{d}{n}_i)$ for all $i$. Hence, $x_1 \equiv x_2 \pmod{N_i}$ for all $i$.

   Since $N = n_1 \times n_2 \times \ldots \times n_k$ by the Chinese Remainder Theorem, $x_1 \equiv x_2 \pmod{N}$

   Thus, any two solutions are congruent modulo $N$, and hence, the solution is unique modulo $N$.

Example:

Let's solve the following system of simultaneous congruences:

$$\begin{align*} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{5} \\ x &\equiv 2 \pmod{7} \end{align*}$$

Here, $n_1 = 3$, $n_2 = 5$, and $n_3 = 7$ are pairwise coprime.

1. Compute $N = n_1 \times n_2 \times n_3 = 3 \times 5 \times 7 = 105$.
2. Compute $N_1 = 105 / 3 = 35$, $N_2 = 105 / 5 = 21$, and $N_3 = 105 / 7 = 15$
3. Compute the inverses $b_1$, $b_2$, and $b_3$ such that $N_i b_i \equiv 1 \pmod{n_i}$. $35b_1 \equiv 1 \pmod{3},21b_2 \equiv 1\pmod{5},15b_3 \equiv 1 \pmod{7}$
   

    4.We get $b_1 = 2$, $b_2=1$, and $b_3 = 1$.

    5.Calculate $x = a_1 N_1 b_1 + a_2 N_2 b_2 + a_3 N_3 b_3 = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 233$

Therefore, the unique solution to the given system of congruences modulo $N = 105$ is $x \equiv 23 \pmod{105}$

Example:

Suppose we have the following system of congruences:

$\begin{align*} x &\equiv 1 \pmod{3} \\ x &\equiv 4 \pmod{5} \\ x &\equiv 6 \pmod{7} \end{align*}$

 

We follow the steps of the Chinese Remainder Theorem:

1. Compute $N = n_1 \times n_2 \times n_3 = 3 \times 5 \times 7 = 105$
2. Compute $N_1 = 105 / 3 = 35$, $N_2 = 105 / 5 = 21$, and $N_3=105\mathrm{/}7=15$
3. Compute the inverses $b_1$, $b_2$, and $b_3$ such that $N_i b_i \equiv 1 \pmod{n_i}$

For $n_1 = 3$, we have $N_1 b_1 \equiv 1 \pmod{3}$, so $35b_1 \equiv 1 \pmod{3}$Solving this congruence, we find $b_1 \equiv 2 \pmod{3}$

For $n_2 = 5$, we have $N_2 b_2 \equiv 1 \pmod{5}$, so $21b_2 \equiv 1 \pmod{5}$. Solving this congruence, we find $b_2 \equiv 1 \pmod{5}$

For $n_3 = 7$, we have $N_3{b}_3\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}7),$ so $15b_3 \equiv 1 \pmod{7}$. Solving this congruence, we find $b_3 \equiv 1 \pmod{7}$

4. Calculate $x = a_1 N_1 b_1 + a_2 N_2 b_2 + a_3 N_3 b_3 = 1 \times 35 \times 2 + 4 \times 21 \times 1 + 6 \times 15 \times 1 = 356$

Therefore, the unique solution to the given system of congruences modulo $N = 105$ is $x \equiv 46 \pmod{105}$

The linear congruences in the Chinese Remainder Theorem are all of the form $x \equiv a_i \mod (n_i)$. If we are given a set of simultaneous linear congruences, with one (or more) of them in the more general form $ax \equiv b \: mod (n_i)$, then we will first need to use the earlier algorithm to solve this congruence, expressing its general solution as a congruence class modulo some divisor of $n_i$; it will then be possible to apply the techniques based on the Chinese Remainder Theorem to solve the resulting simultaneous congruences.

Example:

Consider the congruences

$$7x \equiv 3 \pmod {12},\quad 10x \equiv 6 \pmod {14}$$

This can be reduced into

$$x \equiv 9 \pmod {12},\quad x \equiv 2 \pmod {7}$$

Now it is in standard form and can be solved with CRT

The solution is

We follow the steps of the Chinese Remainder Theorem:

1. Compute $N = n_1 \times n_2 = 12 \times 7 = 84$
2. Compute $N_1 = 84 / 12 = 7$ and $N_2=84\mathrm{/}\mathrm{7=12}$
3. Compute the inverses $b_1$ and $b_2$ such that $N_i{b}_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{n}_i)$

For $n_1 = 12$, we have $N_1 b_1 \equiv 1 \pmod{12}$, so $7b_1 \equiv 1 \pmod{12}$. Solving this congruence, we find $b_1 \equiv 7 \pmod{12}$

For $n_2 = 7$, we have $N_2 b_2 \equiv 1 \pmod{7}$, so $12b_2 \equiv 1 \pmod{7}$. Solving this congruence, we find $b_2\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}7)$

4. Calculate $x=a_1{N}_1{b}_1+a_2{N}_2{b}_2=9\times 7\times 7+2\times 12\times 3=513$

Therefore, the unique solution to the given system of congruences modulo $N = 84$ is $x \equiv 21 \pmod{84}. General solution is $9+84t$$

The Chinese Remainder Theorem (CRT) can be used to convert a single congruence, with a large modulus into several simultaneous congruences with smaller moduli

Example:

Consider the congruence  $13x \equiv 71 \pmod{380}$

Instead of solving this single linear congruence, we can use factorization $380=2^2 \times 5 \times 19$
So we can replace the original congruence with three simultaneous congruences.

$$13x \equiv 71 \pmod{4}, \quad 13x \equiv 71 \pmod{5} ,\quad  13x \equiv 71 \pmod{19}$$

These can be immediately reduced to

$$x \equiv 3 \pmod{4} ,\quad 3x \equiv 1 \pmod{5}, \quad  13x \equiv 14 \pmod{19}$$

We can further reduce this into

$$x \equiv 3 \pmod{4}, \quad x \equiv 2 \pmod{5}, \quad  x \equiv 4 \pmod{19}$$

$Now these have mutually coprime  moduli and these can be solved using CRT$

We follow the steps of the Chinese Remainder Theorem:Compute $N = n_1 \times n_2 \times n_3= 4 \times 5 \times 19 = 380$

Compute $N_1 = 380 / 4 = 95$ and $N_2=380/5=76$ and $N_3=380/19=20$

Compute the inverses $b_1,b_2$​ and $b_3$​ such that $N_ib_i≡1(mod \:n_i)$

For $n_1=4$, we have $N_1 b_1 \equiv 1 \pmod{4}$, so $95.b_1 \equiv 1 \pmod{4}$. Solving this congruence, we find $b_1 \equiv 3 \pmod{4}$

For $n_2 = 5$, we have $N_2 b_2 \equiv 1 \pmod{5}$, so $76.b_2 \equiv 1 \pmod{5}$. Solving this congruence, we find $b_2≡1 \pmod{5}$

For $n_3 = 19$, we have $N_3 b_3 \equiv 1 \pmod{19}$, so $20.b_3 \equiv 1 \pmod{19}$. Solving this congruence, we find $b_3≡1 \pmod{19}$

Calculate $x=a_1N_1b_1+a_2N_2b_2+a_3N_3b_3=3 \times 95 \times 3+2 \times 76 \times 1+4 \times 20 \times 1=1080=327 \pmod{380}$

Therefore, the unique solution to the given system of congruences modulo $N = 380$ is $x \equiv 327 \pmod{380}$. General solution is $327+380t$

Python code 

$x≡2(mod\;3)x≡3(mod \; 5)x≡2(mod \; 7)$

from sympy.ntheory.modular import crt

print(crt([3, 5, 7], [2, 3, 2]))

Output:(23, 105)