Chinese remainder theorem

Pradipta Choudhury
Last Updated: May 13, 2022

Introduction: 

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

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mi>r</mi><mi>e</mi><mi>m</mi><mfenced open="[" close="]"><mn>0</mn></mfenced><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>n</mi><mi>u</mi><mi>m</mi><mfenced open="[" close="]"><mn>0</mn></mfenced></mrow></mfenced><mspace linebreak="newline"/><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mi>r</mi><mi>e</mi><mi>m</mi><mfenced open="[" close="]"><mn>1</mn></mfenced><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>n</mi><mi>u</mi><mi>m</mi><mfenced open="[" close="]"><mn>1</mn></mfenced></mrow></mfenced></mstyle></math>

 

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: 

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mtable columnalign="left"><mtr><mtd><mi>x</mi><mo>&#x2245;</mo><mfenced><mrow><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>5</mn></mrow></mfenced></mtd></mtr><mtr><mtd><mi>x</mi><mo>&#x2245;</mo><mfenced><mrow><mn>3</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>7</mn></mrow></mfenced></mtd></mtr></mtable></mstyle></math>

 

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

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="26px"><mi>X</mi><mo>&#xA0;</mo><mo>&#x2245;</mo><mfenced><mrow><mn>2</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>3</mn></mrow></mfenced><mspace linebreak="newline"/><mi>X</mi><mo>&#xA0;</mo><mo>&#x2245;</mo><mo>&#xA0;</mo><mfenced><mrow><mn>3</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>4</mn></mrow></mfenced><mspace linebreak="newline"/><mi>X</mi><mo>&#xA0;</mo><mo>&#x2245;</mo><mfenced><mrow><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>5</mn></mrow></mfenced></mstyle></math>

 

To apply this theorem here, 34, 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,

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mi>a</mi><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi><mn>1</mn></mrow></mfenced><mspace linebreak="newline"/><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mi>a</mi><mn>2</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi><mn>2</mn></mrow></mfenced><mspace linebreak="newline"/><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mi>a</mi><mn>3</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi><mn>3</mn></mrow></mfenced></mstyle></math>

 

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:

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="26px"><mtable columnalign="left"><mtr><mtd><mi>x</mi><mo>=</mo><mfenced><mrow><msub><mi>M</mi><mn>1</mn></msub><msub><mi>X</mi><mn>1</mn></msub><msub><mi>a</mi><mn>1</mn></msub><mo>+</mo><msub><mi>M</mi><mn>2</mn></msub><msub><mi>X</mi><mn>2</mn></msub><msub><mi>a</mi><mn>2</mn></msub><mo>+</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>+</mo><msub><mi>M</mi><mi>n</mi></msub><msub><mi>X</mi><mi>n</mi></msub><msub><mi>a</mi><mi>n</mi></msub></mrow></mfenced><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>M</mi></mtd></mtr><mtr><mtd/></mtr></mtable></mstyle></math>

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mtable columnalign="left"><mtr><mtd><mi>M</mi><mo>=</mo><mo>(</mo><msub><mi>m</mi><mn>1</mn></msub><mo>&#xD7;</mo><msub><mi>m</mi><mn>2</mn></msub><mo>&#xD7;</mo><msub><mi>m</mi><mn>3</mn></msub><mo>&#xD7;</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>&#xD7;</mo><msub><mi>m</mi><mi>n</mi></msub><mo>)</mo></mtd></mtr><mtr><mtd/></mtr></mtable></mstyle></math>

 

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.

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="26px"><mrow><msub><mi>M</mi><mi>i</mi></msub><mo>=</mo><mfrac><mi>M</mi><msubsup><mi>m</mi><mi>i</mi><mrow/></msubsup></mfrac></mrow></mstyle></math>

      

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><msub><mi>M</mi><mn>1</mn></msub><mo>=</mo><mfrac><mi>M</mi><msub><mi>m</mi><mn>1</mn></msub></mfrac><mo>=</mo><mfrac><mrow><msub><mi>m</mi><mn>1</mn></msub><msub><mi>m</mi><mn>2</mn></msub><msub><mi>m</mi><mn>3</mn></msub></mrow><msub><mi>m</mi><mn>1</mn></msub></mfrac><mo>=</mo><msub><msubsup><mi>m</mi><mn>2</mn><mrow/></msubsup><mrow/></msub><msub><mi>m</mi><mn>3</mn></msub></mrow></mstyle></math>

Similarly,

 

 <math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><msub><mi>M</mi><mn>2</mn></msub><mo>=</mo><msub><mi>m</mi><mn>1</mn></msub><msub><mi>m</mi><mn>3</mn></msub><mspace linebreak="newline"/><msub><mi>M</mi><mn>3</mn></msub><mo>=</mo><msub><mi>m</mi><mn>1</mn></msub><msub><mi>m</mi><mn>2</mn></msub></mrow></mstyle></math>

 

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

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><msub><msub><mi>M</mi><mi>i</mi></msub><mrow/></msub><msup><msub><mi>X</mi><mi>i</mi></msub><mrow/></msup><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mi>i</mi></msub><mspace linebreak="newline"/><mi>e</mi><mi>x</mi><mi>a</mi><mi>m</mi><mi>p</mi><mi>l</mi><mi>e</mi><mo>:</mo><mo>&#xA0;</mo><mo>&#xA0;</mo><msub><mi>M</mi><mn>1</mn></msub><msub><mi>X</mi><mn>1</mn></msub><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mn>1</mn></msub></mstyle></math>

 

Let’s understand  with the help of an example:

                                                                Source: Giphy

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mrow><mn>1</mn><mo>.</mo><mo>&#xA0;</mo><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>5</mn></mrow></mfenced><mo>&#xA0;</mo><mo>&#xA0;</mo><mo>&#xA0;</mo><mo>&#xA0;</mo><mspace linebreak="newline"/><mn>2</mn><mo>.</mo><mo>&#xA0;</mo><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>7</mn></mrow></mfenced><mspace linebreak="newline"/><mn>3</mn><mo>.</mo><mo>&#xA0;</mo><mi>X</mi><mo>&#x2245;</mo><mfenced><mrow><mn>3</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>11</mn></mrow></mfenced><mspace linebreak="newline"/><mi>w</mi><mi>e</mi><mo>&#xA0;</mo><mi>k</mi><mi>n</mi><mi>o</mi><mi>w</mi><mo>,</mo><mo>&#xA0;</mo><mi>x</mi><mo>&#x2245;</mo><msub><mi>a</mi><mi>i</mi></msub><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mi>i</mi></msub><mspace linebreak="newline"/><mi>s</mi><mi>o</mi><mo>,</mo><mo>&#xA0;</mo><msub><mi>a</mi><mn>1</mn></msub><mo>=</mo><mn>1</mn><mo>,</mo><mo>&#xA0;</mo><msub><mi>a</mi><mn>2</mn></msub><mo>=</mo><mn>1</mn><mo>,</mo><mo>&#xA0;</mo><msub><mi>a</mi><mn>3</mn></msub><mo>=</mo><mn>3</mn><mo>&#xA0;</mo><mi>a</mi><mi>n</mi><mi>d</mi><mo>&#xA0;</mo><mo>&#xA0;</mo><msub><mi>m</mi><mn>1</mn></msub><mo>=</mo><mn>5</mn><mo>,</mo><mo>&#xA0;</mo><msub><mi>m</mi><mn>2</mn></msub><mo>=</mo><mn>7</mn><mo>,</mo><mo>&#xA0;</mo><msub><mi>m</mi><mn>3</mn></msub><mo>=</mo><mn>11</mn></mrow></mstyle></math>

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

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><mi>M</mi><mo>=</mo><msub><mi>m</mi><mn>1</mn></msub><mo>&#xD7;</mo><msub><mi>m</mi><mn>2</mn></msub><mo>&#xD7;</mo><msub><mi>m</mi><mn>3</mn></msub><mo>&#xA0;</mo><mspace linebreak="newline"/><mo>=</mo><mn>5</mn><mo>&#xD7;</mo><mn>7</mn><mo>&#xD7;</mo><mn>11</mn><mspace linebreak="newline"/><mo>=</mo><mn>385</mn></mrow></mstyle></math>

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mrow><msub><mi>M</mi><mn>1</mn></msub><mo>=</mo><mfrac><mi>M</mi><msub><mi>m</mi><mn>1</mn></msub></mfrac><mo>=</mo><msub><mi>m</mi><mn>2</mn></msub><msub><mi>m</mi><mn>3</mn></msub><mo>=</mo><mn>7</mn><mo>&#xD7;</mo><mn>11</mn><mo>=</mo><mn>77</mn><mspace linebreak="newline"/><msub><mi>M</mi><mn>2</mn></msub><mo>=</mo><msub><mi>m</mi><mn>1</mn></msub><msub><mi>m</mi><mn>3</mn></msub><mo>=</mo><mn>5</mn><mo>&#xD7;</mo><mn>11</mn><mo>=</mo><mn>55</mn><mspace linebreak="newline"/><msub><mi>M</mi><mn>3</mn></msub><mo>=</mo><msub><mi>m</mi><mn>1</mn></msub><msub><mi>m</mi><mn>2</mn></msub><mo>=</mo><mn>5</mn><mo>&#xD7;</mo><mn>7</mn><mo>=</mo><mn>35</mn><mspace linebreak="newline"/><mi>N</mi><mi>o</mi><mi>w</mi><mo>,</mo><mo>&#xA0;</mo><mi>w</mi><mi>e</mi><mo>&#xA0;</mo><mi>w</mi><mi>i</mi><mi>l</mi><mi>l</mi><mo>&#xA0;</mo><mi>c</mi><mi>a</mi><mi>l</mi><mi>c</mi><mi>u</mi><mi>l</mi><mi>a</mi><mi>t</mi><mi>e</mi><mo>&#xA0;</mo><mi>f</mi><mi>o</mi><mi>r</mi><mo>&#xA0;</mo><msub><mi>X</mi><mi>i</mi></msub><mo>&#xA0;</mo><mo>&#xA0;</mo><mo>:</mo><mo>-</mo><mspace linebreak="newline"/><mspace linebreak="newline"/></mrow></mstyle></math>

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><msub><mi>M</mi><mn>1</mn></msub><msub><mi>X</mi><mn>1</mn></msub><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mrow><mn>1</mn><mo>&#xA0;</mo></mrow></msub><mo>&#xA0;</mo><mo>&#xA0;</mo><mi>o</mi><mi>r</mi><mo>&#xA0;</mo><mo>&#xA0;</mo><mo>&#xA0;</mo><msub><mi>M</mi><mn>1</mn></msub><msub><mi>X</mi><mn>1</mn></msub><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mn>1</mn></msub></mrow></mfenced><mo>=</mo><mn>1</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>77</mn><mo>&#xD7;</mo><msub><mi>x</mi><mn>1</mn></msub><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>5</mn></mrow></mfenced><mo>=</mo><mn>1</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>2</mn><mo>&#xD7;</mo><msub><mi>x</mi><mn>1</mn></msub><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>5</mn></mrow></mfenced><mo>=</mo><mn>1</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><mo>&#xA0;</mo><msub><mi>x</mi><mn>1</mn></msub><mo>=</mo><mn>3</mn></mstyle></math>

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mi>S</mi><mi>i</mi><mi>m</mi><mi>i</mi><mi>l</mi><mi>a</mi><mi>r</mi><mi>l</mi><mi>y</mi><mo>,</mo><mo>&#xA0;</mo><msub><mi>M</mi><mn>2</mn></msub><msub><mi>X</mi><mn>2</mn></msub><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mn>2</mn></msub><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>55</mn><mo>&#xD7;</mo><msub><mi>x</mi><mrow><mn>2</mn><mo>&#xA0;</mo></mrow></msub><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>7</mn></mrow></mfenced><mo>=</mo><mn>1</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>6</mn><mo>&#xD7;</mo><msub><mi>x</mi><mn>2</mn></msub><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>7</mn></mrow></mfenced><mo>=</mo><mn>1</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><msub><mi>x</mi><mn>2</mn></msub><mo>=</mo><mn>6</mn></mstyle></math>

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>M</mi><mn>3</mn></msub><mo>&#xD7;</mo><msub><mi>x</mi><mn>3</mn></msub><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mn>3</mn></msub><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>35</mn><mo>&#xD7;</mo><msub><mi>x</mi><mn>3</mn></msub><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>11</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>2</mn><mo>&#xD7;</mo><msub><mi>x</mi><mn>3</mn></msub><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>11</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><mn>2</mn><mo>&#xD7;</mo><msub><mi>x</mi><mn>3</mn></msub><mo>&#xD7;</mo><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>11</mn></mrow></mfenced><mo>=</mo><mn>1</mn><mspace linebreak="newline"/><mo>&#x21D2;</mo><msub><mi>x</mi><mn>3</mn></msub><mo>=</mo><mn>6</mn></math>

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mrow><mi>N</mi><mi>o</mi><mi>w</mi><mo>,</mo><mo>&#xA0;</mo><mi>x</mi><mo>=</mo><mfenced><mrow><msub><mi>M</mi><mn>1</mn></msub><msub><mi>X</mi><mn>1</mn></msub><msub><mi>a</mi><mrow><mn>1</mn><mo>&#xA0;</mo></mrow></msub><mo>&#xA0;</mo><mo>&#xD7;</mo><mo>&#xA0;</mo><msub><mi>M</mi><mn>2</mn></msub><msub><mi>X</mi><mn>2</mn></msub><msub><mi>a</mi><mn>2</mn></msub><mo>&#xA0;</mo><mo>&#xD7;</mo><mo>&#xA0;</mo><msub><mi>M</mi><mn>3</mn></msub><msub><mi>X</mi><mn>3</mn></msub><msub><mi>a</mi><mn>3</mn></msub></mrow></mfenced><mspace linebreak="newline"/><mi>x</mi><mo>=</mo><mfenced><mrow><mn>77</mn><mo>&#xD7;</mo><mn>3</mn><mo>&#xD7;</mo><mn>1</mn><mo>+</mo><mn>55</mn><mo>&#xD7;</mo><mn>6</mn><mo>&#xD7;</mo><mn>1</mn><mo>+</mo><mn>35</mn><mo>&#xD7;</mo><mn>6</mn><mo>&#xD7;</mo><mn>3</mn></mrow></mfenced><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>385</mn><mspace linebreak="newline"/><mi>x</mi><mo>=</mo><mfenced><mrow><mn>231</mn><mo>+</mo><mn>330</mn><mo>+</mo><mn>630</mn></mrow></mfenced><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>385</mn><mspace linebreak="newline"/><mi>x</mi><mo>=</mo><mn>1191</mn><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>385</mn><mspace linebreak="newline"/><mi>x</mi><mo>=</mo><mn>36</mn></mrow></mstyle></math>

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:

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mrow><msub><mi>y</mi><mi>j</mi></msub><mo>=</mo><msup><mfenced><mrow><msub><mi>m</mi><mn>1</mn></msub><mo>&#xA0;</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>&#xA0;</mo><msub><mi>m</mi><mrow><mi>j</mi><mo>-</mo><mn>1</mn></mrow></msub></mrow></mfenced><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><msub><mi>m</mi><mi>j</mi></msub><mspace linebreak="newline"/></mrow></mstyle></math>

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:

 

#include<bits/stdc++.h>
using namespace std;

/****
    K is the size of the number and reminder arrays.
    We need to return the smallest number x such that:
    x % num[0] = rem[0]
    x % num[1] = rem[1] and continue till ...
    x % num[k-2] = rem[k-1]
    Note: elements in num[] array are
    pairwise coprime i.e
    gcd of every pair is 1
    
****/
int findMinX(int num[], int rem[], int k)
{
    // Initialize result
    int x = 1;

    /**
        For chinese remainder theorem
        this loop will break always
    **/
    while (true)
    {
        /***
            Checking the condition if remainder
            of x % num[j] gives rem[j] or not
            for all j from 0 till k-1
        ***/
        int j;
        for (j = 0; j < k; j++ )
        {
            if (x % num[j] != rem[j])
                {
                    break;
                }
        }

        // all the remainders matched with value k
        if (j == k)
        {
            return x;
        }

        // Else try next number
        x++;
    }

    return x;
}

// Driver method
int main()
{
    int number[] = {5711};
    int reminder[] = {113};
    int k = sizeof(number) / sizeof(number[0]);
    cout << "The value of x is " <<
    findMinX(number, reminder, k);
    return 0;
}

 

 

Output:

 

The value of x is 36

 

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:

 

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mi>X</mi><mo>&#xA0;</mo><mo>=</mo><mo>&#xA0;</mo><mfenced><mrow><munder><mo>&#x2211;</mo><mrow/></munder><mfenced><mrow><mi>r</mi><mi>e</mi><mi>m</mi><mfenced open="[" close="]"><mi>i</mi></mfenced><mo>&#xD7;</mo><mi>a</mi><mi>r</mi><mi>r</mi><mfenced open="[" close="]"><mi>i</mi></mfenced><mo>&#xD7;</mo><mi>i</mi><mi>n</mi><mi>v</mi><mfenced open="[" close="]"><mi>i</mi></mfenced></mrow></mfenced></mrow></mfenced><mo>%</mo><mi>p</mi><mi>r</mi><mi>o</mi><mi>d</mi><mspace linebreak="newline"/><mi>w</mi><mi>h</mi><mi>e</mi><mi>r</mi><mi>e</mi><mo>&#xA0;</mo><mn>0</mn><mo>&#x2264;</mo><mi>i</mi><mo>&#x2264;</mo><mfenced><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></mfenced></mstyle></math>

 

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

 

#include <bits/stdc++.h>
using namespace std;

/*
    function inv which returns modulo
    inverse of a number with respect to m.
    Here, extended euclid algorithm is applied
*/
int inverse(int a, int rem)
{
    int m0 = rem, t, q;
    int x0 = 0, x1 = 1;

    if (rem == 1)
    {
        return 0;
    }

    // Apply extended Euclid Algorithm
    while (a > 1) {


        // q is quotient
        q = a / rem;

        t = rem;

        // m is remainder now, process same as euclid's algo
        rem = a % rem, a = t;

        t = x0;

        x0 = x1 - q * x0;

        x1 = t;
    }

    // x1 should be positive always
    if (x1 < 0)
        {
            x1 += m0;
        }

    return x1;
}

/*
    Function which returns the value of x
    such that x % num[0] = rem[0], and so on
    and numbers in num[] array is co-prime
*/
int findMinX(int number[], int reminder[], int n)
{
    /*
        Computing product of all numbers
        from the num[] array
    */
    int prod = 1;
    for (int i = 0; i < n; i++)
        {
            prod *= number[i];
        }

    // Initialize result
    int result = 0;

    // Apply above formula
    for (int i = 0; i < n; i++) {
        int temp = prod / number[i];
        result += reminder[i] * inverse(temp, number[i]) * temp;
    }

    return result % prod;
}

// Driver method
int main()
{
    int number[] = { 5711 };
    int reminder[] = { 113 };
    int n = sizeof(number) / sizeof(number[0]);
    cout << "The value of x is: " << findMinX(number, reminder, n);
    return 0;
}

 

 

Output:

 

The value of x is: 36

 

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think