# How to execute the Chinese Remainder Theorem

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

#### 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).