Table of Contents

Last modified on April 26th, 2024

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 = m_{1}, m_{2}, …, m_{r} is a set of pairwise relatively prime non-zero integers such that gcd(m_{i}, m_{j}) = 1 for i ≠ j, and a_{1}, a_{2}, …, a_{r} Є ℤ, then the system of congruences x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}), …, x ≡ a_{r} (mod m_{r}) 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.

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.

**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.

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

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 ≡ a_{1} (mod m_{1}), …, x ≡ a_{r} (mod m_{r}), x ≡ a_{r+1} (mod m_{r+1}), where (m_{i}, m_{j}) = 1 for all i ≠ j, and all the a_{i}’s are arbitrary.

By the inductive hypothesis, there is a solution b to the first r congruences, say b ≡ a_{1} (mod m_{1}), b ≡ a_{2} (mod m_{2}), …, b ≡ a_{r} (mod m_{r}).

Now, from the system of two congruences, we get

x ≡ b (mod m_{1}m_{2} … m_{r}) and x ≡ a_{r + 1} (mod m_{r + 1})

⇒ x ≡ b (mod M) and x ≡ a_{r + 1} (mod m_{r + 1}) …..(iii)

Since (m_{r}, m_{r + 1}) = 1 for i = 1, 2, …, r, we have gcd(m_{1}m_{2} … m_{r}, m_{r + 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 m_{1}m_{2} … m_{r}), we have c ≡ b (mod M) for i = 1, 2, . . . , r.

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

Thus, c ≡ a_{i} (mod M) for i = 1, 2, …, r. Also, c ≡ a_{r + 1} (mod m_{r + 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 m_{i} (1≤ i ≤ r).

Assuming the solution is not unique, if x = c and x = c’ both satisfy x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}), …, x ≡ a_{r} (mod m_{r}), then we have c ≡ c’ (mod m_{i}) for i = 1, 2, …, r

Thus, m_{i} | (c − c’) for i = 1, 2, …, r

Since all the m_{i}’s are pairwise relatively prime, their product m_{1}m_{2} …m_{r} divides (c − c’), which means c ≡ c’ (mod m_{1}m_{2} …m_{r}) ⇒ c ≡ c’ (mod M).

This shows all solutions to the given system of congruences are the same when determined by modulo m_{1}m_{2} …m_{r }(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}}}$
- x
_{i}is the modular inverse of M_{i}, modulo m_{i}

**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 M_{i}, we get

M_{1} = ${\dfrac{315}{5}}$ = 63

M_{2} = ${\dfrac{315}{7}}$ = 45

M_{3} = ${\dfrac{315}{9}}$ = 35

Now, we find modular inverses, as shown:

x_{1} ≡ 63^{-1} (mod 5)

Since 63 ≡ 3 (mod 5), thus, 3x_{1} ≡ 1 (mod 5) ⇒ x_{1} ≡ 2 (mod 5)

x_{2} ≡ 45^{-1} (mod 7)

Since 45 ≡ 3 (mod 7), thus 3x_{2} ≡ 1 (mod 7) ⇒ x_{2} ≡ 5 (mod 7)

x_{3} ≡ 35^{-1} (mod 9)

Since 35 ≡ 8 (mod 9), thus 8x_{3} ≡ 1 (mod 9) ⇒ x_{3} ≡ 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).

Last modified on April 26th, 2024