Chinese Remainder Theorem

A system of linear congruences of the form: $$ \begin{cases} x ≡ r_1 \mod n_1 \\ x ≡ r_2 \mod n_2 \\ \vdots \\ x ≡ r_n \mod n_n \end{cases} $$ has a unique solution \( x \) modulo \( N = n_1 \cdot n_2 \cdot \dots \cdot n_n \) if and only if the moduli are pairwise coprime: $$ \gcd(n_i, n_j) = 1 \quad \text{for all } i \neq j. $$ The solution is given by: $$ x = \frac{N}{n_1} x_1 +\frac{N}{n_2} x_2 + ... + \frac{N}{n_n} x_n \mod N $$ where \( x_1, x_2, x_3, \dots \) are the solutions to the system: $$ \begin{cases} x ≡ x_1 \frac{N}{n_1} \mod n_1 \\ x ≡ x_2 \frac{N}{n_2} \mod n_2 \\ \vdots \\ x ≡ x_n \frac{N}{n_n} \mod n_n \end{cases} $$

In other words, if the moduli in a system of linear congruences are pairwise coprime integers, then a unique solution exists.

Important: The Chinese Remainder Theorem applies only when the moduli are coprime. If they are not, the system must be solved using alternative methods.

A Practical Example

Consider the following system of linear congruences:

$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$

The moduli are pairwise coprime:

$$ \gcd(4,3) = 1 \\ \gcd(4,5) = 1 \\ \gcd(3,5) = 1 $$

Since this condition holds, we can apply the Chinese Remainder Theorem.

Rewriting the system in an equivalent form:

$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$

$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ x ≡ 2 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$

Explanation:
• For the first congruence, \( x = 3 \) satisfies \( x \equiv 3 \mod 4 \) since \( 3 \equiv 3 \mod 4 \).
• For the second, \( x = 2 \) ensures that \( 2x \equiv 1 \mod 3 \) holds, since \( 2(2) \equiv 4 \equiv 1 \mod 3 \).
• For the third, \( x = 4 \) satisfies \( x \equiv 4 \mod 5 \) as \( 4 \equiv 4 \mod 5 \).

Next, we compute the product of the moduli:

$$ N = n_1 \cdot n_2 \cdot n_3 = 4 \cdot 3 \cdot 5 = 60 $$

We then express \( x \) in terms of \( (N/n_i)x_i \):

$$ \begin{pmatrix} \frac{N}{n_1} x_1 ≡ 3 \mod 4 \\ \frac{N}{n_2} x_2 ≡ 2 \mod 3 \\ \frac{N}{n_3} x_3 ≡ 4 \mod 5 \end{pmatrix} $$

Substituting the values:

$$ \begin{pmatrix} \frac{60}{4} x_1 ≡ 3 \mod 4 \\ \frac{60}{3} x_2 ≡ 2 \mod 3 \\ \frac{60}{5} x_3 ≡ 4 \mod 5 \end{pmatrix} $$

$$ \begin{pmatrix} 15 x_1 ≡ 3 \mod 4 \\ 20 x_2 ≡ 2 \mod 3 \\ 12 x_3 ≡ 4 \mod 5 \end{pmatrix} $$

Simplifying:

$$ \begin{pmatrix} 3 x_1 ≡ 3 \mod 4 \\ 2 x_2 ≡ 2 \mod 3 \\ 2 x_3 ≡ 4 \mod 5 \end{pmatrix} $$

Explanation: The remainders of 15 mod 4, 20 mod 3, and 12 mod 5 are 3, 2, and 2, respectively.

The solutions are \( x_1 = 1 \), \( x_2 = 1 \), and \( x_3 = 2 \).

Now, we compute the final solution using the formula:

$$ x = \frac{N}{n_1} x_1 + \frac{N}{n_2} x_2 + \frac{N}{n_3} x_3 $$

$$ x = \frac{60}{4} (1) + \frac{60}{3} (1) + \frac{60}{5} (2) $$

$$ x = 15(1) + 20(1) + 12(2) $$

$$ x = 59 $$

Thus, the solution to the system is \( x = 59 \).

Verification: $$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$ $$ \begin{pmatrix} 59 ≡ 3 \mod 4 \\ 2(59) ≡ 1 \mod 3 \\ 59 ≡ 4 \mod 5 \end{pmatrix} $$ $$ \begin{pmatrix} 3 ≡ 3 \mod 4 \\ 1 ≡ 1 \mod 3 \\ 4 ≡ 4 \mod 5 \end{pmatrix} $$ The solution satisfies all congruences in the system.

Solving a Congruence Using the Chinese Remainder Theorem

If the modulus \( n \) is a composite number, the Chinese Remainder Theorem can be used to solve a congruence of the form \( a^b \mod n \) by factoring \( n \) into its prime components, i.e., \( n = p_1 p_2 \dots p_k \).

This approach allows us to compute \( a^b \) modulo each prime factor separately and then reconstruct the final solution by combining the individual results.

Why use this method? This technique is particularly useful when the prime factors of \( n \) are relatively small, as it simplifies modular computations compared to working directly with \( n \).

Example

Consider the congruence:

$$ 5^{89} \mod 77 $$

Since \( 77 \) is a composite number, \( 77 = 7 \times 11 \), we can apply the Chinese Remainder Theorem by computing \( 5^{89} \) modulo 7 and modulo 11 separately.

Step 1: Computing \( 5^{89} \mod 7 \)

Since 7 is prime, we can apply Fermat’s Little Theorem:

$$ a^{p-1} \equiv 1 \mod p $$

For \( p = 7 \):

$$ 5^6 \equiv 1 \mod 7 $$

We express the exponent \( 89 \) in terms of multiples of 6: \( 89 = 6 \times 14 + 5 \).

Rewriting the congruence:

$$ 5^{89} = (5^6)^{14} \cdot 5^5 \mod 7 $$

Since \( 5^6 \equiv 1 \mod 7 \), we substitute:

$$ 5^{89} \equiv 1^{14} \cdot 5^5 \mod 7 $$

$$ 5^{89} \equiv 5^5 \mod 7 $$

We know that \( 5^2 \equiv 25 \equiv 4 \mod 7 \) and that \( 5^5 = 5^2 \cdot 5^2 \cdot 5 \), so:

$$ 5^{89} \equiv (5^2 \cdot 5^2 \cdot 5) \mod 7 $$

$$ 5^{89} \equiv (4 \cdot 4 \cdot 5) \mod 7 $$

$$ 5^{89} \equiv 16 \cdot 5 \mod 7 $$

$$ 5^{89} \equiv 2 \cdot 5 \equiv 10 \mod 7 $$

$$ 5^{89} \equiv 3 \mod 7 $$

Step 2: Computing \( 5^{89} \mod 11 \)

Applying Fermat’s Little Theorem again with \( p = 11 \):

$$ 5^{10} \equiv 1 \mod 11 $$

We express \( 89 \) in terms of multiples of 10: \( 89 = 10 \times 8 + 9 \).

$$ 5^{89} = (5^{10})^8 \cdot 5^9 \mod 11 $$

Since \( 5^{10} \equiv 1 \mod 11 \), we simplify:

$$ 5^{89} \equiv 1^8 \cdot 5^9 \mod 11 $$

$$ 5^{89} \equiv 5^9 \mod 11 $$

We compute \( 5^9 \mod 11 \) knowing that \( 5^2 = 25 \equiv 3 \mod 11 \) and \( 5^4 = (5^2)^2 = 3^2 = 9 \mod 11 \):

$$ 5^9 = (5^4)^2 \cdot 5 \mod 11 $$

$$ 5^{89} \equiv 9^2 \cdot 5 \mod 11 $$

$$ 5^{89} \equiv 81 \cdot 5 \equiv 4 \cdot 5 \mod 11 $$

$$ 5^{89} \equiv 20 \equiv 9 \mod 11 $$

Step 3: Reconstructing the Solution Using the Chinese Remainder Theorem

We now solve the system:

$$ \begin{cases} x \equiv 3 \mod 7 \\ x \equiv 9 \mod 11 \end{cases} $$

From the first congruence, we express \( x \) as:

$$ x = 7k + 3 $$

Substituting into the second congruence:

$$ 7k + 3 \equiv 9 \mod 11 $$

$$ 7k \equiv 6 \mod 11 $$

To solve for \( k \), we need the modular inverse of 7 modulo 11, i.e., the number \( m \) such that:

$$ 7m \equiv 1 \mod 11 $$

Checking manually:

$$ 7 \times 1 = 7 \equiv 7 \mod 11 $$

$$ 7 \times 2 = 14 \equiv 3 \mod 11 $$

$$ 7 \times 3 = 21 \equiv 10 \mod 11 $$

$$ 7 \times 4 = 28 \equiv 6 \mod 11 $$

$$ 7 \times 5 = 35 \equiv 2 \mod 11 $$

$$ 7 \times 6 = 42 \equiv 9 \mod 11 $$

$$ 7 \times 7 = 49 \equiv 5 \mod 11 $$

$$ 7 \times 8 = 56 \equiv 1 \mod 11 $$

Thus, the modular inverse is \( 7^{-1} \equiv 8 \mod 11 \).

Note: In more complex cases, the modular inverse can be efficiently computed using the Extended Euclidean Algorithm.

Multiplying both sides by 8:

$$ k \equiv 6 \times 8 \equiv 48 \equiv 4 \mod 11 $$

Substituting \( k = 4 \) into \( x = 7k + 3 \):

$$ x = 7(4) + 3 = 28 + 3 = 31 $$

Thus, the final solution is:

$$ 5^{89} \equiv 31 \mod 77 $$

And that’s how we use the Chinese Remainder Theorem to solve modular exponentiation problems.