# 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
- Example
- What if we have equations of the form bx ≡ a (mod m)?
- Example with equations of the form bx ≡ a (mod m)

#### 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 ≡ a`

_{1} (mod m_{1})

x ≡ a_{2} (mod m_{2})

...

x ≡ a_{3} (mod m_{k})

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:

**Find the common modulus**

We can find this by multiplying all of the moduli:

`M = m`

_{1}× m_{2}× ... × m_{k}**Divide the common modulus by each modulus to get some new numbers.**

Find`M`

,_{1}= (M/m_{1})`M`

, ...,_{2}= (M/m_{2})`M`

_{k}= (M/m_{k})**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`M`

to_{1}^{-1}`M`

, where..._{k}^{-1}

`M`

the multiplicative inverse of_{1}^{-1}=`M`

_{1}mod m_{1}

`M`

the multiplicative inverse of_{2}^{-1}=`M`

_{2}mod m_{2}

...

`M`

the multiplicative inverse of_{k}^{-1}=`M`

_{k}mod m_{k}

Have a look at our page that explains how to calculate modular multiplicative inverse.**Calculate the solution by multiplying some stuff**

We can now find`x`

by calculating this:

`x = (a`

_{1}× M_{1}× M_{1}^{-1}+ a_{2}× M_{2}× M_{2}^{-1}+ ... + a_{k}× M_{k}× M_{k}^{-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.

**Find the common modulus M**

`M = m`

_{1}× m_{2}× ... × m_{k}= 3 × 5 × 7 = 105**We calculate the numbers M**_{1}to M_{3}

`M`

,_{1}= (M/m_{1}) = 105/3 = 35`M`

,_{2}= (M/m_{2}) = 105/5 = 21`M`

_{3}= (M/m_{3}) = 105/7 = 15**We now calculate the modular multiplicative inverses M**_{1}^{-1}to M_{3}^{-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:

`M`

the multiplicative inverse of_{1}^{-1}= (`M`

the multiplicative inverse of_{1}mod m_{1}) = (`35 mod 3) = 2`

`M`

the multiplicative inverse of_{2}^{-1}= (`M`

the multiplicative inverse of_{2}mod m_{2}) = (`21 mod 5) = 1`

`M`

the multiplicative inverse of_{3}^{-1}= (`M`

the multiplicative inverse of_{3}mod m_{3}) = (`15 mod 7) = 1`

**Now we can calculate x with the equation we saw earlier**

`x = (a`

_{1}× M_{1}× M_{1}^{-1}+ a_{2}× M_{2}× M_{2}^{-1}+ ... + a_{k}× M_{k}× M_{k}^{-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:

`b`

_{1}x ≡ a_{1} (mod m_{1})

b_{2}x ≡ a_{2} (mod m_{2})

...

b_{k}x ≡ a_{3} (mod m_{k})

In that case we first have to move the `b`

's to the right side of the equation:

`x ≡ a`

_{1} × b_{1}^{-1} (mod m_{1})

x ≡ a_{2} × b_{2}^{-1}(mod m_{2})

...

x ≡ a_{3} × b_{k}^{-1}(mod m_{k})

It almost looks as if we have divided both sides by the `b`

's, but that's not the case.

The `b`

doesn't mean ^{-1}`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 `b`

, _{1}^{-1}`b`

, ..., _{2}^{-1}`b`

, where:_{k}^{-1}

`b`

= the multiplicative inverse of _{1}^{-1}`b`

_{1} mod m_{1}

`b`

= the multiplicative inverse of _{2}^{-1}`b`

_{2} mod m_{2}

...

`b`

= the multiplicative inverse of _{k}^{-1}`b`

_{k} mod m_{k}

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`

on the right side of each equation to get some new ^{-1} (mod m)`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`

the multiplicative inverse of ^{-1} mod 11 = (`3 mod 11) = 4`

`7`

the multiplicative inverse of ^{-1} mod 13 = (`7 mod 13) = 2`

`4`

the multiplicative inverse of ^{-1} mod 15 = (`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:

**Find the common modulus M**

`M = m`

_{1}× m_{2}× ... × m_{k}= 11 × 13 × 15 = 2145**We calculate the numbers M**_{1}to M_{3}

`M`

,_{1}= (M/m_{1}) = 2145/11 = 195`M`

,_{2}= (M/m_{2}) = 2145/13 = 165`M`

_{3}= (M/m_{3}) = 2145/15 = 143**We now calculate the modular multiplicative inverses M**_{1}^{-1}to M_{3}^{-1}

Using, for example, the Extended Euclidean Algorithm, we will find that:

`M`

the multiplicative inverse of_{1}^{-1}= (`M`

the multiplicative inverse of_{1}mod m_{1}) = (`195 mod 11) = 7`

`M`

the multiplicative inverse of_{2}^{-1}= (`M`

the multiplicative inverse of_{2}mod m_{2}) = (`165 mod 13) = 3`

`M`

the multiplicative inverse of_{3}^{-1}= (`M`

the multiplicative inverse of_{3}mod m_{3}) = (`143 mod 15) = 2`

**Now we can calculate x with the equation we saw earlier**

`x = (a`

_{1}× M_{1}× M_{1}^{-1}+ a_{2}× M_{2}× M_{2}^{-1}+ ... + a_{k}× M_{k}× M_{k}^{-1})**mod M**

`= (8 × 195 × 7 + 5 × 165 × 3 + 11 × 143 × 2)`

**mod 2145**

`= 1526 mod 2145`

So our x ≡ 1526 (mod 2145).