Chinese remainder theorem

Introduction: 

Chinese remainder theorem states that there always exists an integer ‘X’, that satisfies the given congruence:

And all these numbers(num[0], num[1]....num[m-1]) must be coprime to each other.

Now, doesn't it sound confusing?

Come let’s figure it out in a little detail.

Working of Chinese remainder theorem:

Let’s take an example, that will help in better clarity. Example: 

If we have to apply the Chinese remainder theorem here, then 5 and 7 should be coprime to each other and they should have GCD = 1. Now, take three equations:

To apply this theorem here, 3, 4, and 5 should be co-primes, and they must have gcd = 1.

For X, GCD(3,4) = GCD(4,5) = GCD(3,5) = 1

When we divide a number by some particular number, we get some remainder, right?

If we divide the same number with some other number, some other remainder will be produced. In such cases, we use the Chinese remainder theorem. In general,

Here, X is congruent to a1 mod m1, X is congruent to a2 mod m2 and x is congruent to a3 mod m3. 

Step 1: gcd(m1,m2) = gcd(m2,m3) = gcd(m1,m3)=1 , that is all should be coprime.

Step 2: for finding x, there exists a simple formula:

The a1,a2… an values will be given to us. M will be the product of the numbers. Now, we should be finding the values of M1, M2 and so on, then Xi will be calculated.

Similarly,

Now, we know Xi is just the multiplicative inverse of the Mi value. To calculate Xi :

Let’s understand  with the help of an example:

                                                                Source: Giphy

Since, 5 ,7 and 11 are relatively prime numbers to one another. So, we can find X :

We can also find this with the help of Garner’s Algorithm. So, let’s jump into that.

Garner’s Algorithm:

For Garner’s algorithm, one first computes representatives for:

Using the extended Euclidean theorem again for values of j=2,3,...k. Note that this step needs to be performed only once if several applications of the Chinese Remainder Theorem is required (for the same modulus).

We will be computing the mixed-radix digits r1, r2, . . . , rk. 

Note: There also exists a polynomial equivalent (univariate polynomials over a field) of Garner’s algorithm as well: Newton interpolation.

Example of Garner’s Algorithm:

Use Garner’s algorithm to find the unique integer 0 ≤ x < 5 · 7 · 11 that satisfies the following three modular equations:

• x = 4 mod 5
• x = 1 mod 7
• x = 2 mod 11

The mixed-radix representation of the unique integer x is of the form

x = v0 + v1 · 5 + v2 · 5 · 7

Hence, the solution is found by determining the integers v0, v1, and v2 as follows:

x = 4 mod 5  v0 + v1 · 5 + v2 · 5 · 7 = 4 mod 5  v0 = 4 mod 5

∴ x = 4+ v1 · 5 + v2 · 5 · 7 

x = 1 mod 7  4 + v1 · 5 + v2 · 5 · 7 = 1 mod 7  4+5v1 = 1 mod 7

5v1 = −3 = 4 mod 7 

But 5-1mod 7 = 3. Hence, v1 = 12 = 5 mod 7 

∴ x =4+5 · 5 + v2 · 5 · 7

x = 2 mod 11  4+5 · 5 + v2 · 5 · 7 = 2 mod 11  29 + 35v2 = 2 mod 11 

7+2v2 = 2 mod 11  2v2 = −5 = 6 mod 11

But 2-1 mod 11 = 6. Hence, v2 = 36 = 3 mod 11

x =4+5 · 5+3 · 5 · 7 = 29 + 105 = 134

Hence, the answer is x = 134 mod 5 · 7 · 11

Implementation using C++:

Naive Approach for Chinese remainder theorem:

Output:

Complexity of Chinese remainder theorem:

Time Complexity: O(M)

The time complexity for this approach is O(M), where ‘M’ is the product of all elements of the number[] array. 

Space Complexity: O(1)

As no extra space is used, therefore space complexity is O(1).

Better Approach:

The basic approach for solving this problem is the one that we have already seen before in this blog. Now, the question is can we make that approach more efficient in terms of time?

This will give rise  to the immersion of inverse module based implementation. 

The solution is based on an interesting trick:

Where Rem[i] represents array of remainders

Prod represents product of all the numbers

i.e  num[0] * num[1] * num[2] * … * num[k-1]

Arr[i] represents the product of all the elements divided by num[i]

i.e  arr[i] = prod / num[i]

And inv[i] represents the modular multiplicative inverse of arr[i] with respect to num[i].

Output:

Complexity of Chinese remainder theorem:

Time complexity: O(N log N) where ‘N’ is the number of elements

As, ‘findMinX()’ function is running for ‘N’ times and at every element we are calling the ‘inverse()’ function which is taking log(N) time. So, overall time complexity will be O(N logN).

Space complexity: O(1)

Frequently asked questions:

1. 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.
2. Why is the Chinese theorem preferred?
   Chinese remainder theorem is generally preferred for calculating large integer values. It allows replacing the values computed through small computation with integers. The integers used for small computation have some bounded values known to the user.
3. Does the Chinese remainder theorem give unique solutions to problems?
   The Chinese remainder theorem gives unique solutions to simultaneous congruences done with the coprime module.

Key Takeaways:

This article gives a pretty good idea about the Chinese remainder theorem, how it works and how to implement it starting from scratch to an efficient solution. The better approach is based on modulo inverse.

But this isn’t the end, right? 

Keeping the theoretical knowledge at our fingertips helps us get about half the work done. To gain complete understanding, practice is a must. To practice more problems you can visit Code Studio 

Happy Learning!!

~ Pradipta Choudhury