Last modified on February 15th, 2024

chapter outline

 

Chinese Remainder Theorem

The Chinese remainder theorem is used to get a unique solution for an arbitrary finite number of congruences with coprime moduli, which states that:

If M = m1, m2, …, mr is a set of pairwise relatively prime non-zero integers such that gcd(mi, mj) = 1 for i ≠ j, and a1, a2, …, ar  Є ℤ, then the system of congruences x ≡ a1 (mod m1), x  ≡ a2 (mod m2), …, x ≡ ar (mod mr) has a unique solution in modulo M for all 1≤ i ≤ r. 

It is applied in all areas of mathematics, especially in computer science, including internet cryptography, where it is used to encode numbers based on it.

Now, let us first verify if the theorem is true for a pair of congruences.

For Pair of Congruences

It states that if m and n are two coprime numbers, the pair of congruences x ≡ a (mod m) and x ≡ b (mod n) has a unique solution for x modulo mn, ∀ a, b Є ℤ.

Here, we show that there is always a solution for x modulo mn, and then we verify that the solution is unique in modulo mn.

Proof

Verifying the Existence of Solution 

The first congruence is written as

x ≡ a (mod m) ⇒ x = a + mp, for some p Є ℤ …..(i)

Using (i), we get the second congruence as x ≡ b (mod n)

⇒ a + mp ≡ b (mod n)

On subtracting a from both sides, we get

⇒ mp ≡ b – a (mod n) …..(ii)

Since m and n are coprime numbers, gcd(m, n) = 1

Also, we know m (mod n) is invertible. Let m’ be the inverse of m (mod n), which means mm’ ≡ 1 (mod n)

On multiplying (ii) by m’, we get

mm’p ≡ m’(b – a) (mod n) ⇒ p = m’(b – a) + nq, for some q Є ℤ

⇒ x = a + mp = a + mm’(b – a) + mnq

Thus, if x satisfies the given pair of congruences, it must hold the above form.

Now, let us verify this expression for every q Є ℤ, which satisfies the given pair of congruences a + mm’(b – a) + mnq ≡ a + 0 + 0 ≡ a (mod m) and a + mm’(b – a) + mnq ≡ a + 1(b – a) + 0 ≡ b (mod n)

Verifying the Uniqueness of Solution

Assuming the solution is not unique, if x = c and x = c’ both satisfy x ≡ a (mod m) and x ≡ b (mod n), then we have c ≡ c’ (mod m) and c ≡ c’ (mod n). 

Thus, m | (c − c’) and n | (c − c’). 

Since gcd(m, n) = 1, the product mn divides (c − c’), which means c ≡ c’ (mod mn). 

This shows that all solutions to the given pair of congruences are the same in modulo mn, and thus, the solution is unique.

Now, let us verify the Chinese remainder theorem for a system of congruences.

Proof

To prove the theorem, first, we verify that there is always a solution for x modulo mi, and then, if the solution is unique in modulo mi for all 1≤ i ≤ r.

Existence of Solution 

Here, we prove the existence of the solution using the mathematical induction.

We have already proved the base step for r = 2

Now, let us assume all simultaneous congruences with r pairwise relatively prime moduli in the inductive part for which the statement is true.

Considering a system of simultaneous congruences with r + 1 pairwise relatively prime moduli, we get:

x ≡ a1 (mod m1), …, x ≡ ar (mod mr), x ≡ ar+1 (mod mr+1), where (mi, mj) = 1 for all i ≠ j, and all the ai’s are arbitrary. 

By the inductive hypothesis, there is a solution b to the first r congruences, say b ≡ a1 (mod m1), b ≡ a2 (mod m2), …, b ≡ ar (mod mr). 

Now, from the system of two congruences, we get 

x ≡ b (mod m1m2 … mr) and x ≡ ar + 1 (mod mr + 1

⇒ x ≡ b (mod M) and x ≡ ar + 1 (mod mr + 1) …..(iii)

Since (mr, mr + 1) = 1 for i = 1, 2, …, r, we have gcd(m1m2 … mr, mr + 1) = 1, and the two moduli in (iii) are relatively prime. 

As we know, in the case of two congruences, there is always a solution to (iii), say c. 

Since c ≡ b (mod m1m2 … mr), we have c ≡ b (mod M) for i = 1, 2, . . . , r. 

For any value of b, we have b ≡ ai (mod M) for i = 1, 2, …, r. 

Thus, c ≡ ai (mod M) for i = 1, 2, …, r. Also, c ≡ ar + 1 (mod mr + 1). 

For any value of c, we observe that c satisfies r + 1 given congruences. This concludes the inductive step, which indicates a solution exists for x modulo mi (1≤ i ≤ r). 

Uniqueness of Solution 

Assuming the solution is not unique, if x = c and x = c’ both satisfy x ≡ a1 (mod m1), x  ≡ a2 (mod m2), …, x ≡ ar (mod mr), then we have c ≡ c’ (mod mi) for i = 1, 2, …, r

Thus, mi | (c − c’) for i = 1, 2, …, r

Since all the mi’s are pairwise relatively prime, their product m1m2 …mr divides (c − c’), which means c ≡ c’ (mod m1m2 …mr) ⇒ c ≡ c’ (mod M).

This shows all solutions to the given system of congruences are the same when determined by modulo m1m2 …mr (that is, modulo M).

Thus, the Chinese remainder theorem is verified.

The solution to a system of congruences using the Chinese remainder theorem is found by the formula:

x ≡ ${\sum ^{r}_{i=1}a_{i}M_{i}x_{i}\left( modM\right)}$

Here,

  • ${M_{i}=\dfrac{M}{m_{i}}}$
  • xi is the modular inverse of Mi, modulo mi

Solved Examples

Find the set of solutions for x ≡ 2 (mod 6) and x ≡ 1 (mod 7).

Solution:

Here, the given pair of congruences are x ≡ 2 (mod 6) and x ≡ 1 (mod 7).
Simplifying the given pair of congruences, we get x = 2 +6p = 1 + 7q, where p, q Є ℤ.
It provides a clear solution of p and q, that is, p = 1 and q = 1. 
Thus, one solution to the system is x = 8
 ⇒ x ≡ 8 (mod 42) is the set of all solutions.

Use the Chinese Remainder Theorem to find the value of x such that: 
x ≡ 3 (mod 5) 
x ≡ 2 (mod 7) 
x ≡ 5 (mod 9)

Solution:

Calculating M = 5 × 7 × 9 = 315
Calculating all the Mi, we get 
M1 = ${\dfrac{315}{5}}$ = 63 
M2 = ${\dfrac{315}{7}}$ = 45
M3 = ${\dfrac{315}{9}}$ = 35
Now, we find modular inverses, as shown:
x1 ≡ 63-1 (mod 5) 
Since 63 ≡ 3 (mod 5), thus, 3x1 ≡ 1 (mod 5) ⇒ x1 ≡ 2 (mod 5)
x2 ≡ 45-1 (mod 7) 
Since 45 ≡ 3 (mod 7), thus 3x2 ≡ 1 (mod 7) ⇒ x2 ≡ 5 (mod 7)
x3 ≡ 35-1 (mod 9)
Since 35 ≡ 8 (mod 9), thus 8x3 ≡ 1 (mod 9) ⇒ x3 ≡ 8 (mod 9)
Now, substituting the values in the formula:
x ≡ (3 × 63 × 2 + 2 × 45 × 5 + 5 × 35 × 8) (mod 315)
⇒ x ≡ (378 + 450 + 1400) (mod 315)
⇒ x ≡ 2228 (mod 315)
To find the smallest positive solution, we consider x ≡ 2228 ≡ 23 (mod 315)
Thus, the solution to the system of congruences is x ≡ 23 (mod 315).