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.
What is 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,
M2 = 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 Mi Zi ≅ 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*m3 / m1) = 7 * 11 = 77
M₂ = M / m2 = m1*m3 (here, M = m1*m2*m3 / 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.
Now think what value of Z3 should be multiplied by 35 such that when you divide 35*Z1 with 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.
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.
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.
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; }
You can also try this code with Online C++ Compiler
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); } }
You can also try this code with Online Java Compiler
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); } }
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.
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.