Chinese remainder theorem

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.

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₁, m₂, ..., m_n are co-prime (pairwise relatively prime) integers, and y₁, y₂, ..., 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₁, m₂, ..., m_n.)

To find this unique solution:

• We first compute the product M = m₁ * m₂ * … * m_n.
   
• For each i from 1 to n, we then compute “M_i = M / m_i” For example,
   

M₁ = M/m₁

     = (m₁ * m₂ * m₃ … * m_n)/ m₁

     = m₂ * m₃ … * m_n

Similarly, 

M₂ = m₁ * m₃ … * m_n

M₃ = m₁ * m₂ * … * 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₁Z₁ ≅ 1(mod m₁)

Similarly,

M₂Z₂ ≅ 1(mod m₂)

M₃Z₃ ≅ 1(mod m₃)

And so on.
 

• We can then compute the solution X as follows:
   

X = (y₁ * Z₁ * M₁ + y₂ * Z₂ * M₂ + ... + 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, y₂ = 1, y₃ = 3,

m₁ = 5, m₂ = 7, m₃ = 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₁ * m₂ * m₃
          = 5 * 7 * 11
         = 385
     
• Next, we compute M_i
  
  
  • M₁ = M / m₁
           = m₂*m₃ (here, M = m₁*m₂*m₃ / m₁)
          = 7 * 11
          = 77
     
  • M₂ = M / m₂ 
         = m₁*m₃ (here, M = m₁*m₂*m₃ / m₂)
         = 5 * 11
         = 55
     
  • M₃ = M / m₃
         = m₁*m₂ (here, M = m₁*m₂*m₃/m₃) 
         = 5*7
         = 35
     
• Find the modular inverses (Z_i) of M₁, M₂, and M₃ modulo 5, 7, and 11, respectively. 
  
  
  • M₁Z₁ ≅ 1(mod m₁)
    M₁Z₁(mod m₁) = 1
    77*Z₁(mod 5) = 1
    
    Now think what value of Z₁ should be multiplied by 77 such that when you divide 77*Z₁ with 5, you get 1 as a remainder. 
    
    77 * 3(mod 5) = 1
    So, Z₁ = 3
    
     
  • M₂Z₂ ≅ 1(mod m₂)
    M₂Z₂(mod m₂) = 1
    55*Z₂(mod 7) = 1
    
    Now think what value of Z₁ should be multiplied by 55 such that when you divide 55*Z₂ with 7, you get 1 as the remainder. 
    
    55*6(mod 7) = 1
    So, Z₂ = 6
    
     
  • M₃Z₃ ≅ 1(mod m₃)
    M₃Z₃(mod m₃) = 1
    35*Z₃(mod 11) = 1
    
    Now think what value of Z₃ should be multiplied by 35 such that when you divide 35*Z₁ with 11, you get 1 as a remainder. 
    
    35*6(mod 11) = 1
    So, Z₃ = 6
     
• Now we calculate X as: 
  X = (y₁ * Z₁ * M₁ + y₂ * Z₂ * M₂ + y₃ * Z₃ * M₃) 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

m₁ = 5, m₂ = 7

• Calculating M:
  
  
  • M = m₁*m₂
        = 5 * 7
        = 35
     
• Finding M_i:
  
  
  • M₁ = M / m₁
           = m₂ (here, M = m₁*m₂ / m₁)
          = 7
    
     
  • M₂ = M / m₂ 
         = m₁ (here, M = m₁*m₂ / m₂)
         = 5
     
• Finding Z_i for M_i:
  
  
  • M₁Z₁ ≅ 1(mod m₁)
    M₁Z₁(mod m₁) = 1
    7*Z₁(mod 5) = 1
    Z₁ = 3
     
  • M₂Z₂ ≅ 1(mod m₂)
    M₂Z₂(mod m₂) = 1
    5*Z₂(mod 7) = 1
    Z₂ = 3
     
• Calculating X: 
  
  X = (y₁ * Z₁ * M₁ + y₂ * Z₂ * M₂) 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.
 

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.
    

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.

• Modulo Fermat's Theorem
• Binary Exponentiation
• Modular exponentiation
   

And many more on our platform CodeStudio.

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 CodeStudio!

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!