# Chinese Remainder Theorem

By **Sudheer S**

# Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the Chinese Remainder Theorem.

### Prereseqisites

- Modular arithmetic, especially modular inverses
- The Extended Euclidean Algorithm

# The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) provides a solution to a system of simultaneous congruences with different moduli. Here’s a step-by-step explanation:

## Problem Setup

Suppose you have a system of congruences like this:

x ≡ a_{1} (mod m_{1})

x ≡ a_{2} (mod m_{2})

⋮

x ≡ a_{k} (mod m_{k})

Here, m_{1}, m_{2}, … m_{k} are pairwise coprime, which means that the greatest common divisor (GCD) of any pair m_{i} and m_{j} (for i!=j) is 1.

## Objective

Find an integer `x`

that satisfies all these congruences simultaneously.

## Step-by-Step Solution

**Step 1**: Compute the product of all moduli.

Let M=m_{1} x m_{2} x … x m_{k}

**Step 2**: Calculate individual terms.

For each `i`

from 1 to `k`

:

Compute Mi=M/m_{i}.

Find the multiplicative inverse N_{i} of M_{i} modulo m_{i}. This N_{i} satisfies the congruence:

M_{i}×N_{i} ≡ 1 (mod m_{i})

**Step 3**: Construct the solution.

The solution x is given by:

$$x = \sum_{i=1}^{k} a_i \times M_i \times N_i$$This sum will give you the unique solution modulo `M`

, meaning `x`

will satisfy all the given congruences.

## Example

Suppose you have the following system of congruences:

x≡2 (mod 3)

x≡3 (mod 5)

x≡2 (mod 7)

**Step 1**: M = 3×5×7 = 105

**Step 2**: Compute

M_{1} = 105/3 = 35

M_{2} = 105/5 = 21

M_{3} = 105/7 = 15

Find the inverses:

N_{1} is the inverse of 35 modulo 3: 35×2≡1 (mod 3), so N_{1}=2.

How did we solve for N_{1}?

To solve the congruence 35 × N_{1} ≡ 1 ( mod 3 ), we’re looking for an integer N_{1} such that when 35×N_{1} is divided by 3, the remainder is 1.

Simplify the congruence: First, reduce 35 modulo 3:

35 ≡ 2 (mod 3)

This is because 35//3=11 with a remainder of 2.

So, the congruence simplifies to:
2×N_{1} ≡ 1 (mod 3)

Solve for N_{1}: Now, find an integer N_{1} such that:

2×N_{1} ≡ 1 (mod3)

To do this, try values of N_{1} modulo 3:

If N_{1}=1, then 2×1=2≡2(mod3) . Notice the value is not 1; but we want 1.

If N_{1}=2, then 2×2=4≡1(mod3)

So, N_{1}=2 is the solution.

Thus, N_{1}=2 satisfies the congruence 35×N_{1}≡1(mod3).

Similarly, find the exact values for N_{2} and N_{3}.

N_{2} is the inverse of 21 modulo 5: 21×1≡1 (mod 5), so N_{2}=1.

N_{3} is the inverse of 15 modulo 7: 15×1≡1 (mod 7), so N_{3}=1.

**Step 3**: Calculate x:

x= ((2×35×2) + (3×21×1) + (2×15×1)) (mod 105)

x = (140+63+30) (mod 105) = 233 (mod 105) = 23

So, the solution is x≡23 (mod 105).

## Interpretation

This means that 23 is the unique solution modulo 105 that satisfies all the original congruences.

## Proof

### Statement of the Theorem:

Suppose we have a system of congruences:

x ≡ a1 (mod m1)

x ≡ a2 (mod m2)

$$ \vdots \notag $$x ≡ a_{k} (mod m_{k})

where the moduli m1,m2,…,m_{k} are pairwise coprime (i.e., gcd(m_{i},m_{j})=1 for all i ≠ j).

The Chinese Remainder Theorem tells us that there exists a unique solution x modulo M, where M=m1×m2×⋯×m_{k}.

Let’s break down the proof into simple steps.

### Constructing a Solution:

First, define the total modulus M as:

M=m_{1} x m_{2} x…x m_{k}

For each i, define:
M_{i} = M / mi

Since M_{i} is the product of all moduli except m_{i}, it is clear that M_{i} is divisible by all m_{j} for j≠i, meaning M_{i} ≡ 0 (mod m_{j}) for j≠i.

Finding Inverses:

Next, for each i, we find an integer y_{i} such that:

y_{i}×M_{i} ≡ 1 (mod m_{i})

This y_{i} exists because M_{i} and m_{i} are coprime. (This is guaranteed by the fact that the moduli m_{1},m_{2},…,m_{k} are pairwise coprime.)

Constructing x:

Now, we construct the solution x as:

$$x = \sum_{i=1}^{k} a_i \times y_i \times M_i $$We need to verify that this xx satisfies all the congruences.

Verification:

Consider x modulo m_{j} for any j:

Since Mi≡0 (mod mj) for all i≠j, only the term where i=j remains:

x≡a_{j} * y_{j} * M_{j} (mod mj)

By the choice of y_{j}, we have y_{j}×M_{j}≡1 (mod m_{j}), so:

x ≡ a_{j} (mod m_{j})

Thus, x satisfies all the original congruences.

Uniqueness:

The solution x is unique modulo M because if there were another solution x′, then x−x′ would be divisible by all m_{i}, meaning x≡x′ (mod M).

## Program

```
# Function to find gcd and the coefficients of Bézout's identity using the extended Euclidean algorithm
def extended_gcd(a, b):
print(f"The start of the function a = {a} and b = {b}")
# Initial values
old_r, r = a, b # r represents the remainder
old_x, x = 1, 0 # Coefficients for a
old_y, y = 0, 1 # Coefficients for b
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r # the same as in the Eucildean algorithm
old_x, x = x, old_x - quotient * x
# x: This represents the current coefficient for a in the linear combination.
# old_x: This represents the previous coefficient for a from the last iteration.
old_y, y = y, old_y - quotient * y
# old_r is the GCD, and old_x and old_y are the coefficients
return old_r, old_x, old_y
# Function to implement the Chinese Remainder Theorem
def chinese_remainder_theorem(a, m):
# Step 1: Compute the product of all moduli
M = 1
for mi in m:
M *= mi
# Step 2: Initialize result variable
x = 0
# Step 3: Compute each term and add it to the result
for i in range(len(a)):
Mi = M // m[i] # Compute Mi = M / mi
# Find the multiplicative inverse of Mi mod mi
gcd, inverse, _ = extended_gcd(Mi, m[i])
# Ensure that gcd is 1 (they are coprime)
if gcd != 1:
raise ValueError(f"The moduli {m} are not pairwise coprime.")
# Add the current term to the result
x += a[i] * inverse * Mi
# Step 4: Return the result mod M (smallest non-negative solution)
return x % M
# Example usage
a = [2, 3, 1]
m = [3, 5, 7]
result = chinese_remainder_theorem(a, m)
print(f"The solution x is: {result}")
```

**Product Calculation**: The product M of all the moduli is computed using a simple loop.

**Result Calculation**: We loop through each congruence to calculate the contribution of each term and sum them up.

**Modulus Calculation**: The final result is taken modulo M to ensure it’s the smallest non-negative solution.

## Computational Complexity

The computational complexity of the program can be analyzed by breaking down the main steps:

**Product Calculation (M)**:

Calculating the product of all moduli m requires iterating through the list m, which has a time complexity of O(n)O(n), where nn is the number of congruences (or moduli).

**Extended Euclidean Algorithm (extended_gcd)**:
The Extended Euclidean Algorithm, which is used to find the multiplicative inverse, runs in O(log(min(a,b))). Since this function is called for each modulus, the overall time complexity for this part is O(n log m_{max}), where mmax is the largest modulus.

**Final Result Calculation**:

The final result is computed by summing up the contributions from each modulus, which involves n multiplications and additions. This also takes O(n) time.

**Overall Complexity**:

Multiplicative Inverses: The most computationally expensive part is computing the multiplicative inverses using the Extended Euclidean Algorithm. This step dominates the overall complexity.
Final Complexity: Combining all these, the overall time complexity of the program is O(n log m^{max}), where n is the number of moduli (congruences), and m_{max} is the largest modulus.

This means that as the number of moduli increases, or as the size of the moduli increases, the time taken by the program increases proportionally to the number of moduli and logarithmically with respect to the size of the moduli.