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):
The "things of unknown number" problem above is an instance of a system of linear congruences in one unknown.
Procedure
- Compute the product \(n\) of all the moduli.
- For the \(i\)-th equation:
- Compute \(m_i=\frac{n}{n_i}\).
- Compute the modular inverse \(m_i^{-1}\) of \(m_i\) modulo \(n_i\).
- Compute \(c_i=m_im_i^{-1}\) (do not reduce it modulo \(n_i\)).
- 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 | |
1 2 3 4 5 6 7 8 9 10 11 | |
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:
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.
- \(n=3\times 5\times 7=105\).
- 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\).
- 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\).
- 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\).
- 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):
Then \(a\) can be written in the following form, called the mixed radix representation of \(a\):
Garner's algorithm computes the coefficients \(x_1, \ldots, x_k\).
Let \(r_{ij}\) be the inverse of \(p_i\) modulo \(p_j\):
Substituting \(a\) into the first equation, we obtain:
Substituting into the second equation gives:
Subtracting \(x_1\) from both sides and then dividing by \(p_1\), we get
Similarly, we obtain:
Implementation
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 | |
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:
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:
First, when \(G=999~911~659\), the answer is clearly \(0\).
Otherwise, by Euler's theorem, the answer is:
It remains to compute:
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:
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
- [Template] Chinese Remainder Theorem (CRT) / Cao Chong Raises Pigs
- [Template] Extended Chinese Remainder Theorem
- [NOI2018] Dragon Slayer
-
Parts of this page are translated from the blog post Китайская теорема об остатках 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.
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Great-designer, StudyingFather, Xeonacid, Enter-tainer, 24OI-bot, iamtwz, ksyx, namasikanam, hly1204, renbaoshuo, little-cindy, Early0v0, Menci, ImpleLee, 383494, Tiphereth-A, shawlleyw, HeRaNO, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.