Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Chinese Remainder Theorem
3.
Working of Chinese Remainder Theorem
3.1.
Example 1
3.2.
Example 2
4.
Algorithm of Chinese Remainder Theorem
5.
Implementation of Chinese Remainder Theorem
5.1.
C++
5.2.
Java
5.3.
Python
5.4.
Javascript
5.5.
C#
5.6.
PHP
5.7.
Output
6.
Complexity Analysis
6.1.
Time Complexity
6.2.
Space Complexity
7.
Applications of Chinese Remainder Theorem
8.
8.1.
Who created the Chinese Remainder Theorem?
8.2.
Why is it called the Chinese Remainder Theorem?
8.3.
What is the general formula for the Chinese Remainder Theorem?
8.4.
What does it mean for moduli to be pairwise relatively prime?
8.5.
What are linear congruences?
9.
Conclusion
Last Updated: Jul 25, 2024
Easy

# Chinese Remainder Theorem

Gaurangi Tyagi

## Introduction

The Chinese Remainder Theorem (CRT) is a powerful and ancient mathematical tool that originated in China during the 3rd century AD. It provides a way to solve systems of simultaneous congruences with different moduli. The theorem is named after the Chinese mathematician Sun Tzu, who first articulated the concept in his work "Sunzi Suanjing."

At its core, the Chinese Remainder Theorem addresses the problem of finding an unknown number that simultaneously satisfies multiple modular conditions.

## Chinese Remainder Theorem

Chinese Remainder 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 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.

## Working of Chinese Remainder Theorem

Suppose we have a system of congruences:

where m1, m2, ..., mn are co-prime (pairwise relatively prime) integers, and y1, y2, ..., yn are arbitrary integers.

Note: The equation X ≅ Yi(mod mi) means that X leaves a remainder of Yi when divided by mi. 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, mi).

The Chinese Remainder Theorem states that this system of congruences has a unique solution x modulo ‘M’ (the product of the moduli m1, m2, ..., mn.)

To find this unique solution:

• We first compute the product M = m1 * m2 * … * mn.

• For each i from 1 to n, we then compute “Mi = M / mi” For example,

M1 = M/m1

= (m1 * m2 * m3 … * mn)/ m1

= m2 * m3 … * mn

Similarly,

M= m1 * m3 … * mn

M3 = m1 * m2 * … * mn

And so on.

• For each i from 1 to n, find the modular inverse Zi of Mi modulo mi. To calculate Zi, we will use the congruence MZ≅ 1 (mod mi). For example,

M1Z1 ≅ 1(mod m1)

Similarly,

M2Z2 ≅ 1(mod m2)

M3Z3 ≅ 1(mod m3)

And so on.

• We can then compute the solution X as follows:

X = (y1 * Z1 * M1 + y2 * Z2 * M2 + ... + yn * Zn * Mn) mod M

where Mi * Zi ≅ 1 (mod mi) 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,

y1 = 1, y2 = 1, y3 = 3,

m1 = 5, m2 = 7, m3 = 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 = m1 * m2 * m3
= 5 * 7 * 11
= 385

• Next, we compute Mi

• M₁ = M / m1
= m2*m3 (here, M = m1*m2*m/ m1)
= 7 * 11
= 77

• M₂ = M / m2
= m1*m3 (here, M = m1*m2*m/ m2)
= 5 * 11
= 55

• M₃ = M / m3
= m1*m2 (here, M = m1*m2*m3/m3
= 5*7
= 35

• Find the modular inverses (Zi) of M₁, M₂, and M₃ modulo 5, 7, and 11, respectively.

• M1Z1 ≅ 1(mod m1)
M1Z1(mod m1) = 1
77*Z1(mod 5) = 1

Now think what value of Zshould be multiplied by 77 such that when you divide 77*Zwith 5, you get 1 as a remainder.

77 * 3(mod 5) = 1
So, Z1 = 3

• M2Z2 ≅ 1(mod m2)
M2Z2(mod m2) = 1
55*Z2(mod 7) = 1

Now think what value of Zshould be multiplied by 55 such that when you divide 55*Zwith 7, you get 1 as the remainder.

55*6(mod 7) = 1
So, Z2 = 6

• M3Z3 ≅ 1(mod m3)
M3Z3(mod m3) = 1
35*Z3(mod 11) = 1

Now think what value of Zshould be multiplied by 35 such that when you divide 35*Zwith 11, you get 1 as a remainder.

35*6(mod 11) = 1
So, Z3 = 6

• Now we calculate X as:
X = (y1 * Z1 * M1 + y2 * Z2 * M2 + y3 * Z3 * M3) 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, y= 2

m1 = 5, m2 = 7

• Calculating M:

• M = m1*m2
= 5 * 7
= 35

• Finding Mi:

• M₁ = M / m1
= m2 (here, M = m1*m/ m1)
= 7

• M₂ = M / m2
= m1 (here, M = m1*m/ m2)
= 5

• Finding Zi for Mi:

• M1Z1 ≅ 1(mod m1)
M1Z1(mod m1) = 1
7*Z1(mod 5) = 1
Z1 = 3

• M2Z2 ≅ 1(mod m2)
M2Z2(mod m2) = 1
5*Z2(mod 7) = 1
Z2 = 3

• Calculating X:

X = (y1 * Z1 * M1 + y2 * Z2 * M2) 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 Chinese Remainder Theorem

We will use the following algorithm to code the CRT.

1. Calculate M as the product of all moduli, i.e., M = m[0] * m[1] * ... * m[k-1].
2. Calculate the array Mi, where each Mi[i] is equal to M divided by m[i].
3. 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.
4. Compute the solution X as the sum of (y[i] * Mi[i] * Zi[i]) for all i, modulo M.
5. Return X as the final answer.

## Implementation of Chinese Remainder Theorem

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

• C++
• Java
• Python
• Javascript
• C#
• PHP

### 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;}``

### Java

``public class ChineseRemainderTheorem {    public static int findX(int[] y, int[] m, int k) {        int M = 1, X = 0, temp = 0;        int[] Mi = new int[k];        int[] Z = new int[k];        // Calculating M        for (int i = 0; i < k; i++) {            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 += (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);    }}``

### Python

``def find_x(y, m, k):    M = 1    X = 0    temp = 0    Mi = [0] * k    Z = [0] * k    # Calculating M    for i in range(k):        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 += 1        Z[i] = z    # Calculating X    for i in range(k):        temp += (y[i] * Z[i] * Mi[i])        X = temp % M    # Final answer    return Xy = [1, 1, 3]m = [5, 7, 11]k = len(y)X = find_x(y, m, k)print("The answer using CRT is:", X)``

### Javascript

``function findX(y, m, k) {    let M = 1, X = 0, temp = 0;    let Mi = new Array(k);    let Z = new Array(k);    // Calculating M    for (let i = 0; i < k; i++) {        M *= m[i];    }    // Calculating Mi    for (let i = 0; i < k; i++) {        Mi[i] = M / m[i];    }    // Calculating Zi    for (let i = 0; i < k; i++) {        let z = 0;        let x = Mi[i];        while ((z * x) % m[i] !== 1) {            z++;        }        Z[i] = z;    }    // Calculating X    for (let i = 0; i < k; i++) {        temp += (y[i] * Z[i] * Mi[i]);        X = temp % M;    }    // Final answer    return X;}let y = [1, 1, 3];let m = [5, 7, 11];let k = y.length;let X = findX(y, m, k);console.log("The answer using CRT is:", X);``

### C#

``using System;public class ChineseRemainderTheorem {    public static int FindX(int[] y, int[] m, int k) {        int M = 1, X = 0, temp = 0;        int[] Mi = new int[k];        int[] Z = new int[k];        // Calculating M        for (int i = 0; i < k; i++) {            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 += (y[i] * Z[i] * Mi[i]);            X = temp % M;        }        // Final answer        return X;    }    public static void Main() {        int[] y = {1, 1, 3};        int[] m = {5, 7, 11};        int k = y.Length;        int X = FindX(y, m, k);        Console.WriteLine("The answer using CRT is: " + X);    }}``

### PHP

``<?phpfunction findX(\$y, \$m, \$k) {    \$M = 1;    \$X = 0;    \$temp = 0;    \$Mi = array_fill(0, \$k, 0);    \$Z = array_fill(0, \$k, 0);    // Calculating M    for (\$i = 0; \$i < \$k; \$i++) {        \$M *= \$m[\$i];    }    // Calculating Mi    for (\$i = 0; \$i < \$k; \$i++) {        \$Mi[\$i] = \$M / \$m[\$i];    }    // Calculating Zi    for (\$i = 0; \$i < \$k; \$i++) {        \$z = 0;        \$x = \$Mi[\$i];        while ((\$z * \$x) % \$m[\$i] != 1) {            \$z++;        }        \$Z[\$i] = \$z;    }    // Calculating X    for (\$i = 0; \$i < \$k; \$i++) {        \$temp += (\$y[\$i] * \$Z[\$i] * \$Mi[\$i]);        \$X = \$temp % \$M;    }    // Final answer    return \$X;}\$y = [1, 1, 3];\$m = [5, 7, 11];\$k = count(\$y);\$X = findX(\$y, \$m, \$k);echo "The answer using CRT is: " . \$X . "\n";?>``

### 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 Chinese Remainder Theorem

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.

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

### Why is it called the Chinese Remainder Theorem?

The Chinese Remainder Theorem is named after the Chinese mathematician Sun Tzu, who first articulated its concept in the 3rd century AD in his work "Sunzi Suanjing," addressing the solution of simultaneous congruences.

### What is the general formula for the Chinese Remainder Theorem?

The general formula for the Chinese Remainder Theorem is x≡∑i=1k yi⋅ Mi ⋅ Zi mod  M where M=∏i=1kmi, Mi​=M/mi​, and Zi is the modular inverse of Mi mod mi.

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

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

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem 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 Code360!

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 problemsinterview experiences, and interview bundles for placement preparations.

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

Happy Learning!

Live masterclass