Skip to content

Chinese Remainder Theorem

Introduction

The "things of unknown number" problem: there are things whose number is unknown. Counted by threes, two remain; counted by fives, three remain; counted by sevens, two remain. How many things are there?

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

The problem first appears in Sunzi Suanjing, together with a concrete method for solving it. In 1247, the Song dynasty mathematician Qin Jiushao gave a complete and systematic treatment of the "things of unknown number" problem in the "Dayan" chapters (volumes 1 and 2) of his Mathematical Treatise in Nine Sections. The mnemonic verse for solving the specific problem above was given by the Ming dynasty mathematician Cheng Dawei in Suanfa Tongzong:

Of three people walking together, few reach seventy; five plum trees bear twenty-one blossoming branches; seven children reunite at exactly the half-month; cast out one hundred and five and the answer is known.

\(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 systems of linear congruences in one unknown 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 "things of unknown number" problem above is an instance of a system of linear congruences in one unknown.

Procedure

  1. Compute the product \(n\) of all the moduli.
  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 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

 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]
        # For Exgcd, see the page on the extended Euclidean algorithm; it returns (gcd, x, y)
        _, b, _ = Exgcd(m, r[i])  # b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n
    return (ans % n + n) % n

Proof

We must show that the \(x\) computed by the algorithm above satisfies \(x\equiv a_i \pmod {n_i}\) for every \(i=1,2,\cdots,k\).

When \(i\neq j\), we have \(m_j \equiv 0 \pmod {n_i}\), hence \(c_j \equiv m_j \equiv 0 \pmod {n_i}\). Moreover, \(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} \]

So for every \(i=1,2,\cdots,k\) the computed \(x\) satisfies \(x\equiv a_i \pmod{n_i}\), which proves that the algorithm solves the system of congruences correctly.

We placed no restriction on the inputs \(a_i\), so every input \(\{a_i\}\) corresponds to a solution \(x\). Moreover, if \(x\neq y\), then for some \(i\) the numbers \(x\) and \(y\) are not congruent modulo \(n_i\). Hence the coefficient lists \(\{a_i\}\) and the solutions \(x\) are in one-to-one correspondence, and the system always has a unique solution.

Explanation

Let us solve the "things of unknown number" problem with the CRT.

  1. \(n=3\times 5\times 7=105\).
  2. Of three people walking together, few reach 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 plum trees bear twenty-one blossoming 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 children reunite at exactly the 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. Hence the unique solution of the system is \(x\equiv 2\times 70+3\times 21+2\times 15\equiv 233\equiv 23 \pmod {105}\). (Cast out one hundred and five and the answer is known.)

Garner's algorithm

The CRT can also be used to represent a large integer by a set of fairly small primes.

For example, suppose \(a\) satisfies the following linear system and \(a < \prod_{i=1}^k p_i\) (where the \(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} \]

Then \(a\) can be written 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 computes 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 obtain:

\[ 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} \]

Subtracting \(x_1\) from both sides and then dividing by \(p_1\), we get

\[ \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 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]

Its time complexity is \(O(k^2)\). In fact, Garner's algorithm does not need the moduli to be prime, only pairwise coprime. In 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} \]

The computation in line 6 corresponds to the mixed radix representation above.

Applications

Some counting and number theory problems, whether to lengthen the code, to make the problem harder, or for some other reason, give a modulus that is not prime!

But its prime factorization shows that it is square-free: the modulus is a product of distinct primes.

We can then do the computation modulo each of these primes separately and combine the answers with the 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 answer is clearly \(0\).

Otherwise, by Euler's theorem, the answer is:

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

It remains to compute:

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

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

Observe that \(999~911~658=2 \times 3 \times 4679 \times 35617\), where every prime factor appears only to the first power. We can therefore compute \(\sum_{k\mid n}\binom{n}{k}\) modulo each of the primes \(2\), \(3\), \(4679\), \(35617\) separately, and then combine the answers with the Chinese remainder theorem.

In other words, 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} \]

Use Lucas's theorem to compute a binomial coefficient modulo a fairly small prime.

Extension: non-coprime moduli

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 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 unless \(\gcd(m_1,m_2)\) divides \(a_2-a_1\).

If it does, the extended Euclidean algorithm gives a solution \((p, q)\).

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

Several equations

Merge the equations two at a time with the method above.

Practice problems