## Introduction

Hello Ninja! Have you ever wondered how mathematicians solve problems related to remainders and congruences? Mathematicians have been developing tools and theorems to tackle such problems efficiently for centuries. One of the most elegant and valuable of these tools is the Chinese Remainder Theorem (CRT). It has been used for centuries to solve problems related to remainders and __modular arithmetic__. We can use this theorem to solve various problems related to modular arithmetic. It has applications in many areas, including computer science, __cryptography__, and __number theory__.

This article will explore the history and applications of the Chinese Remainder Theorem. We will also look at some examples to help you better understand this powerful mathematical tool.

Also see, __Euclid GCD Algorithm__

## Chinese Remainder Theorem

This theorem is named after the Chinese mathematician **Sun Zi**, who first described this principle in the third century AD. It is a mathematical tool that helps you solve a system of equations where each equation has a different modulus. A **modulus** is just a fancy term for the remainder you get when you divide a number by another number.

According to the Chinese Remainder Theorem, if you have two equations, x ≅ a (mod m) and x ≅ b (mod n), where m and n are different moduli. You can combine them into a single equation, x ≅ c (mod mn), where x is the unique solution to the system. Provided, m and n are relatively prime.

Let us understand the working of this theorem in detail.

## Working of Chinese Remainder Theorem

Suppose we have a system of congruences:

where m_{1}, m_{2}, ..., m_{n} are co-prime (pairwise relatively prime) integers, and y_{1}, y_{2}, ..., y_{n} are arbitrary integers.

**Note:** The equation X ≅ Y_{i}(mod m_{i}) means that X leaves a remainder of Y_{i} when divided by m_{i}. The ≅ symbol is used to indicate "congruence modulo." It means that the two values on either side of the symbol are equivalent when they are divided by the modulus (here, m_{i}).

The Chinese Remainder Theorem states that this system of congruences has a unique solution x modulo ‘M’ (the product of the moduli m_{1}, m_{2}, ..., m_{n}.)

To find this unique solution:

- We first compute the product M = m
_{1}* m_{2}* … * m_{n}.

- For each i from 1 to n, we then compute “M
_{i}= M / m_{i}” For example,

M_{1} = M/m_{1}

= (m_{1} * m_{2} * m_{3} … * m_{n})/ m_{1}

= m_{2} * m_{3} … * m_{n}

Similarly,

M_{2 }= m_{1} * m_{3} … * m_{n}

M_{3} = m_{1} * m_{2} * … * m_{n}

And so on.

- For each i from 1 to n, find the
__modular inverse__Z_{i}of M_{i}modulo m_{i}. To calculate Z_{i,}we will use the congruence M_{i }Z_{i }≅ 1 (mod m_{i}). For example,

M_{1}Z_{1} ≅ 1(mod m_{1})

Similarly,

M_{2}Z_{2} ≅ 1(mod m_{2})

M_{3}Z_{3} ≅ 1(mod m_{3})

And so on.

- We can then compute the solution X as follows:

X = (y_{1} * Z_{1} * M_{1} + y_{2} * Z_{2} * M_{2} + ... + y_{n} * Z_{n} * M_{n}) mod M

where M_{i} * Z_{i} ≅ 1 (mod m_{i}) for each i.

This formula is known as the Chinese Remainder Theorem formula.

Let us illustrate the Chinese Remainder Theorem with an example.

### Example 1

Consider the following system of congruences:

```
X ≅ 1 (mod 5)
X ≅ 1 (mod 7)
X ≅ 3 (mod 11)
```

Here,

y_{1} = 1, y_{2} = 1, y_{3} = 3,

m_{1} = 5, m_{2} = 7, m_{3} = 11

Since 5, 7, and 11 are relatively prime numbers to one another. So, we can find X. We can use CRT to find the unique solution to this system of congruences. The steps to do so are:

- First, we compute the product M.
- M = m
_{1}* m_{2}* m_{3}_{ }= 5 * 7 * 11

= 385

- M = m
- Next, we compute M
_{i}- M₁ = M / m
_{1}_{ }= m_{2}*m_{3}(here, M = m_{1}*m_{2}*m_{3 }/ m_{1})

= 7 * 11

= 77

- M₂ = M / m
_{2}

= m_{1}*m_{3}(here, M = m_{1}*m_{2}*m_{3 }/ m_{2})

= 5 * 11

= 55

- M₃ = M / m
_{3}

= m_{1}*m_{2}(here, M = m_{1}*m_{2}*m_{3}/m_{3})

= 5*7

= 35

- M₁ = M / m
- Find the modular inverses (Z
_{i}) of M₁, M₂, and M₃ modulo 5, 7, and 11, respectively.- M
_{1}Z_{1}≅ 1(mod m_{1})

M_{1}Z_{1}(mod m_{1}) = 1

77*Z_{1}(mod 5) = 1

Now think what value of Z_{1 }should be multiplied by 77 such that when you divide 77*Z_{1 }with 5, you get 1 as a remainder.

77 * 3(mod 5) = 1

So, Z_{1}= 3

- M
_{2}Z_{2}≅ 1(mod m_{2})

M_{2}Z_{2}(mod m_{2}) = 1

55*Z_{2}(mod 7) = 1

Now think what value of Z_{1 }should be multiplied by 55 such that when you divide 55*Z_{2 }with 7, you get 1 as the remainder.

55*6(mod 7) = 1

So, Z_{2}= 6

- M
_{3}Z_{3}≅ 1(mod m_{3})

M_{3}Z_{3}(mod m_{3}) = 1

35*Z_{3}(mod 11) = 1

Now think what value of Z_{3 }should be multiplied by 35 such that when you divide 35*Z_{1 }with 11, you get 1 as a remainder.

35*6(mod 11) = 1

So, Z_{3}= 6

- M
- Now we calculate X as:

X = (y_{1}* Z_{1}* M_{1}+ y_{2}* Z_{2}* M_{2}+ y_{3}* Z_{3}* M_{3}) mod M

= (1 * 3 * 77 + 1 * 6 * 55 + 3 * 6 * 35) mod 385

= (231 + 330 + 630) mod 385

= (1191) mod 385

= 36

Therefore, X = 36.

Now let us look at a real-life example to see where we can use this theorem.

### Example 2

Consider the following example.

Ninja has a friend, Alice, who has a secret number she wants to share with him. But instead of giving the number directly, she decided to give him the remainder of the number when divided by two different factors, say 5 and 7. Let's say her number has a remainder of 1 when divided by 5 and a remainder of 2 when divided by 7

To find the number, Ninja can use the Chinese Remainder Theorem to combine the remainders in a certain way to get a unique solution that satisfies both equations.

The equation that he can form from this will be:

X ≅ 1 (mod 5)

X ≅ 2 (mod 7)

X is Alice’s secret number.

Before moving to the solution, try to find X yourself so the concept of the Chinese Remainder Theorem will be clear to you.

Here,

y_{1 }= 1, y_{2 }= 2

m_{1} = 5, m_{2} = 7

- Calculating M:
- M = m
_{1}*m_{2}

= 5 * 7

= 35

- M = m
- Finding M
_{i}:- M₁ = M / m
_{1}_{ }= m_{2}(here, M = m_{1}*m_{2 }/ m_{1})

= 7

- M₂ = M / m
_{2}

= m_{1}(here, M = m_{1}*m_{2 }/ m_{2})

= 5

- M₁ = M / m
- Finding Z
_{i}for M_{i}:- M
_{1}Z_{1}≅ 1(mod m_{1})

M_{1}Z_{1}(mod m_{1}) = 1

7*Z_{1}(mod 5) = 1

Z_{1}= 3

- M
_{2}Z_{2}≅ 1(mod m_{2})

M_{2}Z_{2}(mod m_{2}) = 1

5*Z_{2}(mod 7) = 1

Z_{2}= 3

- M
- Calculating X:

X = (y_{1}* Z_{1}* M_{1}+ y_{2}* Z_{2}* M_{2}) mod M

= (1 * 3 * 7 + 2 * 3 * 5) mod 35

= (21 + 30) mod 35

= (51) mod 35

= 16

So, Alice’s number was 16.

Let us now code the Chinese Remainder Theorem.

## Algorithm of CRT

We will use the following algorithm to code the CRT.

- Calculate M as the product of all moduli, i.e., M = m[0] * m[1] * ... * m[k-1].

- Calculate the array Mi, where each Mi[i] is equal to M divided by m[i].

- Calculate the array Zi, where each Zi[i] is the inverse modulo m[i] of Mi[i]. This can be done using a simple loop that increments a counter until (Zi[i] * Mi[i]) mod m[i] equals 1.

- Compute the solution X as the sum of (y[i] * Mi[i] * Zi[i]) for all i, modulo M.

- Return X as the final answer.

Let us now look at its implementation in ** C++**, Java, and

__Python__.

## Implementation of CRT

Following is the implementation of the Chinese Remainder Theorem in C++, Java, and Python.

### Implementation in C++

```
#include<bits/stdc++.h>
using namespace std;
int findX(int y[], int m[], int k){
int M = 1, X = 0, temp = 0;
int Mi[k], Z[k];
// Calculating M
for(int i = 0; i < k; i++){
M = M * m[i];
}
// Calculating Mi
for(int i = 0; i < k; i++){
Mi[i] = M / m[i];
}
// Calculating Zi
for(int i = 0; i < k; i++){
int z = 0;
int x = Mi[i];
while((z * x) % m[i] != 1){
z++;
}
Z[i] = z;
}
// Calculating X
for(int i = 0; i < k; i++) {
int temp = temp + (y[i] * Z[i] * Mi[i]);
X = temp % M;
}
// Final answer
return X;
}
int main(){
int y[] = {1, 1, 3};
int m[] = {5, 7, 11};
int k = sizeof(y) / sizeof(y[0]);
int X = findX(y, m, k);
cout << "The answer using CRT is: " << X << endl;
return 0;
}
```

### Output

### Implementation in Java

```
import java.util.*;
class Main {
public static int findX(int y[], int m[], int k){
int M = 1, X = 0, temp = 0;
int Mi[] = new int[k], Z[] = new int[k];
// Calculating M
for(int i = 0; i < k; i++){
M = M * m[i];
}
// Calculating Mi
for(int i = 0; i < k; i++){
Mi[i] = M / m[i];
}
// Calculating Zi
for(int i = 0; i < k; i++){
int z = 0;
int x = Mi[i];
while((z * x) % m[i] != 1){
z++;
}
Z[i] = z;
}
// Calculating X
for(int i = 0; i < k; i++) {
temp = temp + (y[i] * Z[i] * Mi[i]);
X = temp % M;
}
// Final answer
return X;
}
public static void main(String[] args) {
int y[] = {1, 1, 3};
int m[] = {5, 7, 11};
int k = y.length;
int X = findX(y, m, k);
System.out.println("The answer using CRT is: " + X);
}
}
```

### Output

### Implementation in Python

```
def findX(y, m, k):
M = 1
X = 0
temp = 0
Mi = [0]*k
Z = [0]*k
# Calculating M
for i in range(k):
M = M * m[i]
# Calculating Mi
for i in range(k):
Mi[i] = M // m[i]
# Calculating Zi
for i in range(k):
z = 0
x = Mi[i]
while((z * x) % m[i] != 1):
z = z + 1
Z[i] = z
# Calculating X
for i in range(k):
temp = temp + (y[i] * Z[i] * Mi[i])
X = temp % M
# Final answer
return X
y = [1, 1, 3]
m = [5, 7, 11]
k = len(y)
X = findX(y, m, k)
print("The answer using CRT is:", X)
```

### Output

Moving forward to the complexity analysis of this code.

## Complexity Analysis

The space and time complexities of this code are as follows:

### Time Complexity

**O(k)** is the time complexity of this code. Here, k is the size of the arrays.

**Reason: **This code has four loops, iterating up to k. The time complexity of each of these loops is O(k). Summing them up, we get O(4k). Since we ignore the constant part while calculating the time complexity, the time complexity of this code becomes O(k).

### Space Complexity

O(k) is the space complexity of this code. Here, k is the size of the arrays.**Reason:** We are using auxiliary space equal to k for the arrays Mi and Z.

Let us now learn some of the applications of the Chinese Remainder Theorem.

Read More - __Time Complexity of Sorting Algorithms__

## Applications of CRT

Here are some applications of the Chinese Remainder Theorem:

**Divisibility testing:**The CRT can be used to test the divisibility of a large number by several small numbers.

**Error-correcting codes:**The CRT can be used to construct error-correcting codes that can detect and correct errors in transmitted messages.

**Digital signal processing:**The CRT can be used in digital signal processing to combine two or more signals that have been sampled at different rates. This process is known as**signal resampling**, and it involves finding a common sampling rate that preserves the original signals.

**Cryptography:**The CRT is used in several cryptographic systems to generate and verify digital signatures. For example, the RSA cryptosystem uses CRT to speed up the decryption process. It computes the ciphertext modulo of two different primes and then combines the two results using the CRT.

**Number theory:**CRT has various applications in number theory, including factorization of large integers and solving__Diophantine equations__.

These are just a few examples of the many applications of the Chinese Remainder Theorem in different fields of mathematics and computer science.

It is now time to address some of the frequently asked questions.

## Frequently Asked Questions

### Who created the Chinese Remainder Theorem?

The Chinese Remainder Theorem was contributed by the 3rd-century-ad Chinese mathematician Sun Zi. This theorem gives the necessary conditions for multiple equations to have a single integrated solution.

### What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical tool used to solve a system of linear congruences with pairwise relatively prime moduli. It provides a unique solution to the system of congruences by combining the solutions of each congruence.

### What does it mean for moduli to be pairwise relatively prime?

Moduli are said to be pairwise relatively prime if every pair of moduli mᵢ and mⱼ, where i ≠ j, are relatively prime. That is, gcd(mᵢ, mⱼ) = 1.

### What are linear congruences?

A linear congruence is a congruence of the form ax ≅ b (mod m), where a, b, and m are integers, and m > 0.

### What are some applications of the Chinese Remainder Theorem?

It is used in the RSA public-key cryptosystem, which is widely used for secure communication over the internet. It is also used in error-correcting codes and in the Chinese Remainder Theorem-based algorithm for integer factorization.

## Conclusion

This article covered the Chinese Remainder Theorem in detail. We learned about its working, implementation, and applications. We also discussed some examples to help understand the theorem better.

We hope this blog has helped you enhance your knowledge. If you want to learn more, then check out our articles.

And many more on our platform __Coding Ninjas Studio__.

Refer to our __Guided Path__ to upskill yourself in __DSA__, __Competitive Programming__, __JavaScript__, __System Design__, and many more! If you want to test your competency in coding, you may check out the mock __test series__ and participate in the __contests__ hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the __problems__, __interview experiences,__ and __interview bundles__ for placement preparations.

You may also consider our paid __courses__ to give your career an edge over others!

**Happy Learning!**