Skip to content

Chinese Remainder Theorem

Introduction

"The problem of unknown numbers": There is an unknown number. When counted by threes, the remainder is 2; when counted by fives, the remainder is 3; when counted by sevens, the remainder is 2. What is the number?

That is, find an integer that satisfies: remainder 2 when divided by \(3\), remainder 3 when divided by \(5\), and remainder 2 when divided by \(7\).

This problem first appeared in Sunzi Suanjing, which also provided a specific solution. The Song dynasty mathematician Qin Jiushao gave a complete and systematic solution to the "unknown numbers" problem in volumes 1 and 2 of Shushu Jiuzhang (1247). The mnemonic for the specific problem above was provided by the Ming dynasty mathematician Cheng Dawei in Suanfa Tongzong:

Three people walk together, seventy is rare; five plum trees, twenty-one branches; seven sons reunite on the full moon, subtract one hundred and five to know.

\(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) can solve a system of univariate linear congruences of the following form (where \(n_1, n_2, \cdots, n_k\) are pairwise coprime):

\[ \begin{cases} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ &\vdots \\ x &\equiv a_k \pmod {n_k} \\ \end{cases} \]

The "unknown numbers" problem above is an instance of such a system.

Process

  1. Compute the product of all moduli \(n\);
  2. For the \(i\)-th equation:
    1. Compute \(m_i=\frac{n}{n_i}\);
    2. Compute the modular inverse \(m_i^{-1}\) of \(m_i\) modulo \(n_i\);
    3. Compute \(c_i=m_im_i^{-1}\) (do not reduce modulo \(n_i\)).
  3. The unique solution modulo \(n\) is: \(x=\sum_{i=1}^k a_ic_i \pmod n\).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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 above algorithm satisfies \(x\equiv a_i \pmod {n_i}\) for any \(i=1,2,\cdots,k\).

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}\). Therefore:

\[ \begin{aligned} x&\equiv \sum_{j=1}^k a_jc_j &\pmod {n_i} \\ &\equiv a_ic_i &\pmod {n_i} \\ &\equiv a_i \cdot m_i \cdot (m^{-1}_i \bmod n_i) &\pmod {n_i} \\ &\equiv a_i &\pmod {n_i} \end{aligned} \]

That is, for any \(i=1,2,\cdots,k\), the \(x\) obtained by the algorithm always satisfies \(x\equiv a_i \pmod{n_i}\), proving the correctness of the algorithm for solving the congruence system.

Since we impose no special restrictions on the input \(\{a_i\}\), any set of inputs \(\{a_i\}\) corresponds to a solution \(x\). Moreover, if \(x\neq y\), there always exists an \(i\) such that \(x\) and \(y\) are incongruent modulo \(n_i\). Hence, there is a bijection between the coefficient list \(\{a_i\}\) and the solution \(x\), and the system always has a unique solution.

Explanation

The following demonstrates how CRT solves the "unknown numbers" problem.

  1. \(n=3\times 5\times 7=105\);
  2. Three people walk together, seventy is rare: \(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 plum trees, twenty-one branches: \(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 reunite on the full half-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. Thus, the unique solution is \(x\equiv 2\times 70+3\times 21+2\times 15\equiv 233\equiv 23 \pmod {105}\). (Subtract one hundred and five to know.)

Garner's Algorithm

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

For example, if \(a\) satisfies the following linear system and \(a < \prod_{i=1}^k p_i\) (where \(p_i\) are primes):

\[ \begin{cases} a &\equiv a_1 \pmod {p_1} \\ a &\equiv a_2 \pmod {p_2} \\ &\vdots \\ a &\equiv a_k \pmod {p_k} \\ \end{cases} \]

We can represent \(a\) in the following form (called the mixed-radix representation of \(a\)):

\[ a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \ldots p_{k-1} \]

Garner's Algorithm will compute the coefficients \(x_1, \ldots, x_k\).

Let \(r_{ij}\) be the inverse of \(p_i\) modulo \(p_j\):

\[ p_i \cdot r_{i,j} \equiv 1 \pmod{p_j} \]

Substituting \(a\) into the first equation we get:

\[ a_1 \equiv x_1 \pmod{p_1} \]

Substituting into the second equation gives:

\[ a_2 \equiv x_1 + x_2 p_1 \pmod{p_2} \]

Subtract \(x_1\) from both sides and divide by \(p_1\):

\[ \begin{aligned} a_2 - x_1 &\equiv x_2 p_1 &\pmod{p_2} \\ (a_2 - x_1) r_{1,2} &\equiv x_2 &\pmod{p_2} \\ x_2 &\equiv (a_2 - x_1) r_{1,2} &\pmod{p_2} \end{aligned} \]

Similarly, we can obtain:

\[ x_k=(\dots((a_k-x_1)r_{1,k}-x_2)r_{2,k})-\dots)r_{k-1,k} \bmod p_k \]
Implementation 
1
2
3
4
5
6
7
8
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];
  }
}

1
2
3
4
5
6
7
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, Garner's algorithm does not require the moduli to be prime, only pairwise coprime. We have the following pseudocode:

\[ \begin{array}{ll} &\textbf{Chinese Remainder Algorithm }\operatorname{cra}(\mathbf{v}, \mathbf{m})\text{:} \\ &\textbf{Input}\text{: }\mathbf{m}=(m_0,m_1,\dots ,m_{n-1})\text{, }m_i\in\mathbb{Z}^+\land\gcd(m_i,m_j)=1\text{ for all } i\neq j\text{,} \\ &\qquad \mathbf{v}=(v_0,\dots ,v_{n-1}) \text{ where }v_i=x\bmod m_i\text{.} \\ &\textbf{Output}\text{: }x\bmod{\prod_{i=0}^{n-1} m_i}\text{.} \\ 1&\qquad \textbf{for }i\text{ from }1\text{ to }(n-1)\textbf{ do} \\ 2&\qquad \qquad C_i\gets \left(\prod_{j=0}^{i-1}m_j\right)^{-1}\bmod{m_i} \\ 3&\qquad x\gets v_0 \\ 4&\qquad \textbf{for }i\text{ from }1\text{ to }(n-1)\textbf{ do} \\ 5&\qquad \qquad u\gets (v_i-x)\cdot C_i\bmod{m_i} \\ 6&\qquad \qquad x\gets x+u\prod_{j=0}^{i-1}m_j \\ 7&\qquad \textbf{return }(x) \end{array} \]

Note that the computation in line 6 corresponds to the mixed-radix representation above.

Applications

Some counting or number theory problems, for reasons such as lengthening code, increasing difficulty, or other factors, give a modulus that is not prime!

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

We can then compute the answer modulo each of these primes separately and finally merge the results using CRT.

The following problem is a good example.

Luogu P2480 [SDOI2010] Ancient Pig Script

Given \(G,n\) (\(1 \leq G,n \leq 10^9\)), compute:

\[ G^{\sum_{k\mid n}\binom{n}{k}} \bmod 999~911~659 \]

First, when \(G=999~911~659\), the result is clearly \(0\).

Otherwise, by Euler's theorem, the desired value is:

\[ G^{\sum_{k\mid n}\binom{n}{k} \bmod 999~911~658} \bmod 999~911~659 \]

Now consider how to compute:

\[ \sum_{k\mid n}\binom{n}{k} \bmod 999~911~658 \]

Since \(999~911~658\) is not prime, we cannot guarantee that \(\forall x \in [1,999~911~657]\), \(x\) has a modular inverse. Thus, we cannot compute this expression directly.

Note that \(999~911~658=2 \times 3 \times 4679 \times 35617\), where each prime factor appears with exponent 1. We can compute \(\sum_{k\mid n}\binom{n}{k}\) modulo \(2\), \(3\), \(4679\), and \(35617\) separately, and finally use the Chinese Remainder Theorem to combine the answers.

That is, we actually need to solve the following linear system:

\[ \begin{cases} x \equiv a_1 \pmod 2\\ x \equiv a_2 \pmod 3\\ x \equiv a_3 \pmod {4679}\\ x \equiv a_4 \pmod {35617} \end{cases} \]

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

Extension: Moduli Not Pairwise Coprime

Two Equations

Let the two equations be \(x\equiv a_1 \pmod {m_1}\) and \(x\equiv a_2 \pmod {m_2}\);

Rewrite them as Diophantine equations: \(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 if \(a_2-a_1\) is not divisible by \(\gcd(m_1,m_2)\);

Otherwise, a feasible solution \((p, q)\) can be found via the extended Euclidean algorithm;

Then the solution to the system formed by the original two equations is \(x\equiv b\pmod M\), where \(b=m_1p+a_1\) and \(M=\text{lcm}(m_1, m_2)\).

Multiple Equations

Combine equations pairwise using the above method.

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用