Bootstrap
  C.R.T. .com
It doesn't have to be difficult if someone just explains it right.

How to execute the Chinese Remainder Theorem

Here we explain all of the steps in the algorithm of the Chinese Remainder Theorem

Table of contents:

The algorithm

Here we provide the general solution of the algorithm. If this sounds confusing, have a look at the example.

We use this algorithm when we have multiple equations of the form x ≡ a (mod m), but with different moduli.
So let's say we have a set of k equations that looks like this:
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ a3 (mod mk)

Here all of the a's, all of the m's and x are some integers.
Now we want to find x. It needs to be one x that satisfies all of the equations.
Here are the steps to find such an x:

  1. Find the common modulus
    We can find this by multiplying all of the moduli:
    M = m1 × m2 × ... × mk
  2. Divide the common modulus by each modulus to get some new numbers.
    Find M1 = (M/m1),  M2 = (M/m2),  ...,  Mk = (M/mk)
  3. Now find the modular multiplicative inverses of the new numbers
    using their corresponding modulus. We denote the inverse with a -1 in superscript.
    In other words, we need to calculate M1-1 to Mk-1, where...
    M1-1 = the multiplicative inverse of M1 mod m1
    M2-1 = the multiplicative inverse of M2 mod m2
    ...
    Mk-1 = the multiplicative inverse of Mk mod mk
    Have a look at our page that explains how to calculate modular multiplicative inverse.
  4. Calculate the solution by multiplying some stuff
    We can now find x by calculating this:
    x = (a1 × M1 × M1-1   +   a2 × M2 × M2-1   + ... +   ak × Mk × Mk-1)   mod M

Example

We have
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Find x.

We proceed by performing the steps described above.

  1. Find the common modulus M
    M = m1 × m2 × ... × mk = 3 × 5 × 7 = 105
  2. We calculate the numbers M1 to M3
    M1 = (M/m1) = 105/3 = 35,   M2 = (M/m2) = 105/5 = 21,   M3 = (M/m3) = 105/7 = 15
  3. We now calculate the modular multiplicative inverses M1-1 to M3-1
    Have a look at the page that explains how to calculate modular multiplicative inverse.
    Using, for example, the Extended Euclidean Algorithm, we will find that:
    M1-1 = (the multiplicative inverse of M1 mod m1) = (the multiplicative inverse of 35 mod 3) = 2
    M2-1 = (the multiplicative inverse of M2 mod m2) = (the multiplicative inverse of 21 mod 5) = 1
    M3-1 = (the multiplicative inverse of M3 mod m3) = (the multiplicative inverse of 15 mod 7) = 1
  4. Now we can calculate x with the equation we saw earlier
    x = (a1 × M1 × M1-1   +   a2 × M2 × M2-1   + ... +   ak × Mk × Mk-1)   mod M
    = (2 × 35 × 2   +   3 × 21 × 1   + 2 × 15 × 1)   mod 105
    = 23 mod 105

So our answer is x = 23 (mod 105).

What if we have equations of the form bx ≡ a (mod m)?

In our earlier example, our equations were of the form x ≡ a (mod m).
But what if our equations have some extra integer b on the left of the equation?
So we have:
b1x ≡ a1 (mod m1)
b2x ≡ a2 (mod m2)
...
bkx ≡ a3 (mod mk)

In that case we first have to move the b's to the right side of the equation:
x ≡ a1 × b1-1 (mod m1)
x ≡ a2 × b2-1(mod m2)
...
x ≡ a3 × bk-1(mod mk)

It almost looks as if we have divided both sides by the b's, but that's not the case.
The b-1 doesn't mean 1/b, but it means the modular multiplicative inverse of b.
So in order to move the b's to the right sides of the equations, we have to calculate their multiplicative inverse modulo their corresponsive m.

So we need to calculate b1-1, b2-1, ..., bk-1, where:
b1-1 = the multiplicative inverse of b1 mod m1
b2-1 = the multiplicative inverse of b2 mod m2
...
bk-1 = the multiplicative inverse of bk mod mk

How do we do that? See our page about how to calculate modular multiplicative inverse.

Once we have done that, we can calculate the a × b-1 (mod m) on the right side of each equation to get some new a' (mod m) on the right side of each equation.

After that, we can proceed as normal with all of the steps described in the earlier example.

Example with equations of the form bx ≡ a (mod m)

Solve the system of congruences relations (i.e. find x):
3x ≡ 2 (mod 11)
7x ≡ 9 (mod 13)
4x ≡ 14 (mod 15)

We now start by moving the b's to the right sides of the equation:
x ≡ 2 × 3-1 (mod 11)
x ≡ 9 × 7-1 (mod 13)
x ≡ 14 × 4-1 (mod 15)

As a result, we get multiplicative inverses on the right. So now we have to calculate those multiplicative inverses:
3-1 mod 11 = (the multiplicative inverse of 3 mod 11) = 4
7-1 mod 13 = (the multiplicative inverse of 7 mod 13) = 2
4-1 mod 15 = (the multiplicative inverse of 4 mod 15) = 4

Alright, now back to the equations. Let's fill in the multiplicative inverses we just found:
x ≡ 2 × 3-1 ≡ 2 × 4 (mod 11) ≡ 8 (mod 11)
x ≡ 9 × 7-1 ≡ 9 × 2 (mod 13) ≡ 18 (mod 13) ≡ 5 (mod 13)
x ≡ 14 × 4-1 ≡ 14 × 4 (mod 15) ≡ 56 (mod 15) ≡ 11 (mod 15)

So we now have:
x ≡ 8 (mod 11)
x ≡ 5 (mod 13)
x ≡ 11 (mod 15)

We can now solve this using the steps we saw before:

  1. Find the common modulus M
    M = m1 × m2 × ... × mk = 11 × 13 × 15 = 2145
  2. We calculate the numbers M1 to M3
    M1 = (M/m1) = 2145/11 = 195,   M2 = (M/m2) = 2145/13 = 165,   M3 = (M/m3) = 2145/15 = 143
  3. We now calculate the modular multiplicative inverses M1-1 to M3-1
    Using, for example, the Extended Euclidean Algorithm, we will find that:
    M1-1 = (the multiplicative inverse of M1 mod m1) = (the multiplicative inverse of 195 mod 11) = 7
    M2-1 = (the multiplicative inverse of M2 mod m2) = (the multiplicative inverse of 165 mod 13) = 3
    M3-1 = (the multiplicative inverse of M3 mod m3) = (the multiplicative inverse of 143 mod 15) = 2
  4. Now we can calculate x with the equation we saw earlier
    x = (a1 × M1 × M1-1   +   a2 × M2 × M2-1   + ... +   ak × Mk × Mk-1)   mod M
    = (8 × 195 × 7   +   5 × 165 × 3   + 11 × 143 × 2)   mod 2145
    = 1526 mod 2145

So our x ≡ 1526 (mod 2145).