Chinese Remainder Theorem

Introduction

The “Unknown Number of Objects” problem: there is an unknown number of objects; counting them in threes leaves two, counting them in fives leaves three, and counting them in sevens leaves two. What is the number?

That is, find an integer satisfying the following conditions: its remainder upon division by $3$ is $2$, its remainder upon division by $5$ is $3$, and its remainder upon division by $7$ is $2$.

This problem first appeared in The Mathematical Classic of Sun Zi, which also gave a specific method for solving it. In 1247, the Song mathematician Qin Jiushao gave a complete and systematic solution to the “Unknown Number of Objects” problem in volumes 1 and 2, “Dayan Class,” of Shushu Jiuzhang. The mnemonic for the specific problem above was given by the Ming mathematician Cheng Dawei in Suanfa Tongzong:

Three people walking together: seventy; five trees with plum blossoms: twenty-one; seven sons reunited: the middle of the month; subtract one hundred and five to find the answer.

$2\times 70+3\times 21+2\times 15=233=2\times 105+23$, so the answer is $23$.

Definition

The Chinese Remainder Theorem (CRT) solves a system of univariate linear congruences of the following form, where $n_1, n_2, \cdots, n_k$ are pairwise coprime:

The “Unknown Number of Objects” problem above is an instance of a system of univariate linear congruences.

Procedure

1. Compute the product of all moduli $n$;
2. For the $i$-th congruence:
   1. Compute $m_i=\frac{n}{n_i}$;
   2. Compute $m_i$ modulo $n_i$ and then its inverse $m_i^{-1}$;
   3. Compute $c_i=m_im_i^{-1}$ (do not take it modulo $n_i$).
3. The unique solution of the system modulo $n$ is $x=\sum_{i=1}^k a_ic_i \pmod n$.

Implementation

C++

LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

Python

def CRT(k, a, r):
    n = 1
    ans = 0
    for i in range(1, k + 1):
        n = n * r[i]
    for i in range(1, k + 1):
        m = n // r[i]
        b = y = 0
        exgcd(m, r[i], b, y)  # b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n
    return (ans % n + n) % n

Proof

We need to prove that the $x$ computed by the algorithm above satisfies, for every $i=1,2,\cdots,k$, $x\equiv a_i \pmod {n_i}$.

When $i\neq j$, we have $m_j \equiv 0 \pmod {n_i}$, so $c_j \equiv m_j \equiv 0 \pmod {n_i}$. Also, $c_i \equiv m_i \cdot (m_i^{-1} \bmod {n_i}) \equiv 1 \pmod {n_i}$, and therefore:

Thus, for every $i=1,2,\cdots,k$, the $x$ obtained by the algorithm above always satisfies $x\equiv a_i \pmod{n_i}$, proving the correctness of the algorithm for solving the system of congruences.

Because we impose no special restrictions on the input $a_i$, every set of inputs $\{a_i\}$ corresponds to a solution $x$. Moreover, if $x\neq y$, there is always an $i$ such that $x$ and $y$ are not congruent modulo $n_i$. Therefore, the coefficient list $\{a_i\}$ and the solution $x$ are in a one-to-one correspondence, and the system always has a unique solution.

Explanation

The following demonstrates how CRT solves the “Unknown Number of Objects” problem.

1. $n=3\times 5\times 7=105$;
2. Three people walking together, seventy: $n_1=3, m_1=n/n_1=35, m_1^{-1}\equiv 2\pmod 3$, so $c_1=35\times 2=70$;
3. Five trees with plum blossoms, twenty-one: $n_2=5, m_2=n/n_2=21, m_2^{-1}\equiv 1\pmod 5$, so $c_2=21\times 1=21$;
4. Seven sons reunited, the middle of the month: $n_3=7, m_3=n/n_3=15, m_3^{-1}\equiv 1\pmod 7$, so $c_3=15\times 1=15$;
5. Therefore, the unique solution of the system is $x\equiv 2\times 70+3\times 21+2\times 15\equiv 233\equiv 23 \pmod {105}$. (Subtract one hundred and five to find the answer.)

Garner algorithm

Another use of CRT is to represent a large integer using a set of relatively small primes.

For example, suppose that $a$ satisfies the following system of linear congruences and $a < \prod_{i=1}^k p_i$, where $p_i$ are primes:

We can represent $a$ in the following form, called the mixed-radix representation of $a$:

The Garner algorithm computes the coefficients $x_1, \ldots, x_k$.

Let $r_{ij}$ denote the value for $p_i$ modulo $p_j$, using the inverse operation:

Substituting $a$ into the first equation gives:

Substituting it into the second equation gives:

Subtracting $x_1$ from both sides and dividing by $p_1$ gives

Similarly, we obtain:

for (int i = 0; i < k; ++i) {
  x[i] = a[i];
  for (int j = 0; j < i; ++j) {
    x[i] = r[j][i] * (x[i] - x[j]);
    x[i] = x[i] % p[i];
    if (x[i] < 0) x[i] += p[i];
  }
}

for i in range(0, k):
    x[i] = a[i]
    for j in range(0, i):
        x[i] = r[j][i] * (x[i] - x[j])
        x[i] = x[i] % p[i]
        if x[i] < 0:
            x[i] = x[i] + p[i]

The time complexity of this algorithm is $O(k^2)$. In fact, the Garner algorithm does not require the moduli to be prime; it only requires them to be pairwise coprime. We have the following pseudocode:

It can be seen that the calculation in line 6 corresponds to the mixed-radix representation above.

Applications

For some counting or number-theoretic problems, the given modulus is not prime because the code is to be lengthened, the difficulty increased, or for some other reason!

However, factoring it reveals that it has no repeated prime factors; that is, the modulus is a product of distinct primes.

We can calculate modulo each of these primes separately and finally combine the answers with CRT.

The following problem is a good example.

First, when $G=999~911~659$, the answer is clearly $0$.

Otherwise, by Euler's theorem, the answer is

Now consider how to compute

Because $999~911~658$ is not prime, we cannot guarantee that $\forall x \in [1,999~911~657]$, every $x$ has an inverse, so the expression above cannot be computed directly.

Observe that $999~911~658=2 \times 3 \times 4679 \times 35617$, and each prime factor occurs only once. We can separately compute $\sum_{k\mid n}\binom{n}{k}$ modulo the primes $2$, $3$, $4679$, and $35617$, and finally combine the results with the Chinese Remainder Theorem.

In other words, we need to solve the following system of linear congruences:

To compute a binomial coefficient modulo a small prime, we can use Lucas's theorem.

Extension: non-coprime moduli

Two congruences

Suppose the two congruences are $x\equiv a_1 \pmod {m_1}$ and $x\equiv a_2 \pmod {m_2}$.

Convert them into a Diophantine equation: $x=m_1p+a_1=m_2q+a_2$, where $p, q$ are integers. Then $m_1p-m_2q=a_2-a_1$.

By Bézout's identity, there is no solution when $a_2-a_1$ is not divisible by $\gcd(m_1,m_2)$.

Otherwise, the extended Euclidean algorithm gives a feasible solution pair $(p, q)$.

The solution of the original two-congruence system is $x\equiv b\pmod M$, where $b=m_1p+a_1$ and $M=\text{lcm}(m_1, m_2)$.

Multiple congruences

Merge them pairwise using the method above.

Exercises

• Chinese Remainder Theorem (CRT) / Cao Chong Raises Pigs

• Extended Chinese Remainder Theorem

• NOI2018 Dragon Warrior

• TJOI2009 Guess the Number

  Part of this page was translated from the blog post Chinese Remainder Theorem and its English translation Chinese Remainder Theorem. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.