October 16, 2023

Chinese Remainder Theorem¶

The Chinese Remainder Theorem (which will be referred to as CRT in the rest of this article) was discovered by Chinese mathematician Sun Zi.

Formulation¶

Let $m = m_{1} \cdot m_{2} \dots m_{k}$ , where $m_{i}$ are pairwise coprime. In addition to $m_{i}$ , we are also given a system of congruences

{\begin{array}{rcl} a & \equiv & a_{1} (\mod m_{1}) \\ a & \equiv & a_{2} (\mod m_{2}) \\ ⋮ \\ a & \equiv & a_{k} (\mod m_{k}) \end{array}

where $a_{i}$ are some given constants. The original form of CRT then states that the given system of congruences always has one and exactly one solution modulo $m$ .

E.g. the system of congruences

{\begin{array}{rcl} a & \equiv & 2 (\mod 3) \\ a & \equiv & 3 (\mod 5) \\ a & \equiv & 2 (\mod 7) \end{array}

has the solution $23$ modulo $105$ , because $23 mod 3 = 2$ , $23 mod 5 = 3$ , and $23 mod 7 = 2$ . We can write down every solution as $23 + 105 \cdot k$ for $k \in Z$ .

Corollary¶

A consequence of the CRT is that the equation

x \equiv a (\mod m)

is equivalent to the system of equations

{\begin{array}{rcl} x & \equiv & a_{1} (\mod m_{1}) \\ ⋮ \\ x & \equiv & a_{k} (\mod m_{k}) \end{array}

(As above, assume that $m = m_{1} m_{2} \dots m_{k}$ and $m_{i}$ are pairwise coprime).

Solution for Two Moduli¶

Consider a system of two equations for coprime $m_{1}, m_{2}$ :

{\begin{aligned} a & \equiv a_{1} (\mod m_{1}) \\ a & \equiv a_{2} (\mod m_{2}) \end{aligned}

We want to find a solution for $a (\mod m_{1} m_{2})$ . Using the Extended Euclidean Algorithm we can find Bézout coefficients $n_{1}, n_{2}$ such that

n_{1} m_{1} + n_{2} m_{2} = 1.

In fact $n_{1}$ and $n_{2}$ are just the modular inverses of $m_{1}$ and $m_{2}$ modulo $m_{2}$ and $m_{1}$ . We have $n_{1} m_{1} \equiv 1 (\mod m_{2})$ so $n_{1} \equiv m_{1}^{- 1} (\mod m_{2})$ , and vice versa $n_{2} \equiv m_{2}^{- 1} (\mod m_{1})$ .

With those two coefficients we can define a solution:

a = a_{1} n_{2} m_{2} + a_{2} n_{1} m_{1} mod m_{1} m_{2}

It's easy to verify that this is indeed a solution by computing $a mod m_{1}$ and $a mod m_{2}$ .

\begin{array}{rcll} a & \equiv & a_{1} n_{2} m_{2} + a_{2} n_{1} m_{1} & (\mod m_{1}) \\ \equiv & a_{1} (1 - n_{1} m_{1}) + a_{2} n_{1} m_{1} & (\mod m_{1}) \\ \equiv & a_{1} - a_{1} n_{1} m_{1} + a_{2} n_{1} m_{1} & (\mod m_{1}) \\ \equiv & a_{1} & (\mod m_{1}) \end{array}

Notice, that the Chinese Remainder Theorem also guarantees, that only 1 solution exists modulo $m_{1} m_{2}$ . This is also easy to prove.

Lets assume that you have two different solutions $x$ and $y$ . Because $x \equiv a_{i} (\mod m_{i})$ and $y \equiv a_{i} (\mod m_{i})$ , it follows that $x - y \equiv 0 (\mod m_{i})$ and therefore $x - y \equiv 0 (\mod m_{1} m_{2})$ or equivalently $x \equiv y (\mod m_{1} m_{2})$ . So $x$ and $y$ are actually the same solution.

Solution for General Case¶

Inductive Solution¶

As $m_{1} m_{2}$ is coprime to $m_{3}$ , we can inductively repeatedly apply the solution for two moduli for any number of moduli. First you compute $b_{2} := a (\mod m_{1} m_{2})$ using the first two congruences, then you can compute $b_{3} := a (\mod m_{1} m_{2} m_{3})$ using the congruences $a \equiv b_{2} (\mod m_{1} m_{2})$ and $a \equiv a_{3} (\mod m_{3})$ , etc.

Direct Construction¶

A direct construction similar to Lagrange interpolation is possible.

Let $M_{i} := \prod_{i \neq j} m_{j}$ , the product of all moduli but $m_{i}$ , and $N_{i}$ the modular inverses $N_{i} := M_{i}^{- 1} mod m_{i}$ . Then a solution to the system of congruences is:

a \equiv \sum_{i = 1}^{k} a_{i} M_{i} N_{i} (\mod m_{1} m_{2} \dots m_{k})

We can check this is indeed a solution, by computing $a mod m_{i}$ for all $i$ . Because $M_{j}$ is a multiple of $m_{i}$ for $i \neq j$ we have

\begin{array}{rcll} a & \equiv & \sum_{j = 1}^{k} a_{j} M_{j} N_{j} & (\mod m_{i}) \\ \equiv & a_{i} M_{i} N_{i} & (\mod m_{i}) \\ \equiv & a_{i} M_{i} M_{i}^{- 1} & (\mod m_{i}) \\ \equiv & a_{i} & (\mod m_{i}) \end{array}

Implementation¶

struct Congruence {
    long long a, m;
};

long long chinese_remainder_theorem(vector<Congruence> const& congruences) {
    long long M = 1;
    for (auto const& congruence : congruences) {
        M *= congruence.m;
    }

    long long solution = 0;
    for (auto const& congruence : congruences) {
        long long a_i = congruence.a;
        long long M_i = M / congruence.m;
        long long N_i = mod_inv(M_i, congruence.m);
        solution = (solution + a_i * M_i % M * N_i) % M;
    }
    return solution;
}

Solution for not coprime moduli¶

As mentioned, the algorithm above only works for coprime moduli $m_{1}, m_{2}, \dots m_{k}$ .

In the not coprime case, a system of congruences has exactly one solution modulo $lcm (m_{1}, m_{2}, \dots, m_{k})$ , or has no solution at all.

E.g. in the following system, the first congruence implies that the solution is odd, and the second congruence implies that the solution is even. It's not possible that a number is both odd and even, therefore there is clearly no solution.

{\begin{aligned} a & \equiv 1 (\mod 4) \\ a & \equiv 2 (\mod 6) \end{aligned}

It is pretty simple to determine is a system has a solution. And if it has one, we can use the original algorithm to solve a slightly modified system of congruences.

A single congruence $a \equiv a_{i} (\mod m_{i})$ is equivalent to the system of congruences $a \equiv a_{i} (\mod p_{j}^{n_{j}})$ where $p_{1}^{n_{1}} p_{2}^{n_{2}} \dots p_{k}^{n_{k}}$ is the prime factorization of $m_{i}$ .

With this fact, we can modify the system of congruences into a system, that only has prime powers as moduli. E.g. the above system of congruences is equivalent to:

{\begin{cases} a \equiv 1 & (\mod 4) \\ a \equiv 2 \equiv 0 & (\mod 2) \\ a \equiv 2 & (\mod 3) \end{cases}

Because originally some moduli had common factors, we will get some congruences moduli based on the same prime, however possibly with different prime powers.

You can observe, that the congruence with the highest prime power modulus will be the strongest congruence of all congruences based on the same prime number. Either it will give a contradiction with some other congruence, or it will imply already all other congruences.

In our case, the first congruence $a \equiv 1 (\mod 4)$ implies $a \equiv 1 (\mod 2)$ , and therefore contradicts the second congruence $a \equiv 0 (\mod 2)$ . Therefore this system of congruences has no solution.

If there are no contradictions, then the system of equation has a solution. We can ignore all congruences except the ones with the highest prime power moduli. These moduli are now coprime, and therefore we can solve this one with the algorithm discussed in the sections above.

E.g. the following system has a solution modulo $lcm (10, 12) = 60$ .

{\begin{aligned} a & \equiv 3 (\mod 10) \\ a & \equiv 5 (\mod 12) \end{aligned}

The system of congruence is equivalent to the system of congruences:

{\begin{aligned} a & \equiv 3 \equiv 1 (\mod 2) \\ a & \equiv 3 \equiv 3 (\mod 5) \\ a & \equiv 5 \equiv 1 (\mod 4) \\ a & \equiv 5 \equiv 2 (\mod 3) \end{aligned}

The only congruence with same prime modulo are $a \equiv 1 (\mod 4)$ and $a \equiv 1 (\mod 2)$ . The first one already implies the second one, so we can ignore the second one, and solve the following system with coprime moduli instead:

{\begin{aligned} a & \equiv 3 \equiv 3 (\mod 5) \\ a & \equiv 5 \equiv 1 (\mod 4) \\ a & \equiv 5 \equiv 2 (\mod 3) \end{aligned}

It has the solution $53 (\mod 60)$ , and indeed $53 mod 10 = 3$ and $53 mod 12 = 5$ .

Garner's Algorithm¶

Another consequence of the CRT is that we can represent big numbers using an array of small integers.

Instead of doing a lot of computations with very large numbers numbers, which might be expensive (think of doing divisions with 1000-digit numbers), you can pick a couple of coprime moduli and represent the large number as a system of congruences, and perform all operations on the system of equations. Any number $a$ less than $m_{1} m_{2} \dots m_{k}$ can be represented as an array $a_{1}, \dots, a_{k}$ , where $a \equiv a_{i} (\mod m_{i})$ .

By using the above algorithm, you can again reconstruct the large number whenever you need it.

Alternatively you can represent the number in the mixed radix representation:

a = x_{1} + x_{2} m_{1} + x_{3} m_{1} m_{2} + \dots + x_{k} m_{1} \dots m_{k - 1} with x_{i} \in [0, m_{i})

Garner's algorithm, which is discussed in the dedicated article Garner's algorithm, computes the coefficients $x_{i}$ . And with those coefficients you can restore the full number.

Practice Problems:¶

Contributors:

jakobkogler (74.78%)
jxu (13.04%)
algmyr (5.65%)
adamant-pwn (3.04%)
thanhtnguyen (1.74%)
vatsalsharma376 (0.87%)
jatingaur18 (0.43%)
MayankPratap (0.43%)