THE GARDEN

Chinese Remainder Theorem

Updated 13 Sep 2026

• •

  What it is

  • •

    Given a system of congruences with pairwise coprime moduli, there's a unique solution modulo the product of those moduli.

• •

  When to apply

  • •

    You're given $x \bmod m_1, x \bmod m_2, \dots$ for coprime $m_i$ and need to recombine them into $x \bmod \prod m_i$​ — also a building block for attacks like Håstad's broadcast attack.

• •

  Symbols and assumptions

  • •

    $x\equiv r_i\pmod{m_i}$ means $m_i$ divides $x-r_i$. Here the positive moduli $m_i$ are pairwise coprime; $M=\prod_i m_i$.

• •

  Math — step by step

  • •
    1. For each modulus, set $M_i=M/m_i$. This is divisible by every other modulus, so its contribution will be zero in all the other congruences.
  • •
    2. Compute $y_i=M_i^{-1}\bmod m_i$. Now $M_i y_i$ is 1 modulo its own modulus and 0 modulo all the others. It acts like a switch selecting one remainder.
  • •
    3. Add the desired remainders times those switches: $x=\sum_i r_i M_i y_i\bmod M$. Reducing modulo any $m_j$ leaves only $r_j$.
  • •
    4. Any two solutions differ by a multiple of every $m_i$, hence by a multiple of $M$. For non-coprime moduli, first require compatible remainders modulo each gcd; uniqueness is modulo the lcm instead.
• •

  Worked example

  • •

    Solve $x\equiv2\pmod3$, $x\equiv3\pmod5$, $x\equiv2\pmod7$. The product is $M=105$ and the partial products are 35, 21, 15.

  • •

    Inverses: $35^{-1}\bmod3=2$, $21^{-1}\bmod5=1$, and $15^{-1}\bmod7=1$.

  • •

    Combine: $x\equiv2(35)(2)+3(21)(1)+2(15)(1)=233\equiv23\pmod{105}$.

  • •

    Check directly: $23\bmod3=2$, $23\bmod5=3$, $23\bmod7=2$. The full solution set is $23+105k$ for integer $k$.

• •

  Python

  • •

    from sympy.ntheory.modular import crt
    x, mod = crt(moduli, residues)
    # sagemath also has crt(residues, moduli)
    

• •

  SageMath

  • •

    crt([2, 3, 5], [5, 11, 17])   # crt(residues, moduli). result is 872
    

• •

  Related

  • •

    Extended Euclidean Algorithm

• •

  Cards

  • •

    What condition must the moduli satisfy for CRT to give a unique solution?

    • •

      They must be pairwise coprime.

  • •

    What's the modulus of the combined solution under CRT?

    • •

      The product of all the individual moduli.

• •

  Archived notes

  • •

    given a set of arbitrary integers $a^i$, and pairwise coprime integers $n^i$, such that the following linear congruences hold:

    • •

      Note: "pairwise coprime integers" means that if we have a set of integers $\{n1,n2,\dots,ni\}$, all pairs of integers selected from the set are coprime: $\gcd(n^i,n^j)=1$.

    • •
      $$\begin{align*} x &\equiv a^1 \mod n^1 \\ x &\equiv a^2 \mod n^2 \\ \dots \\ x &\equiv a^n \mod n^n \end{align*}$$
    • •

      There is a unique solution $x \equiv a \mod N$ where $N= n^1 \cdot n^2 \cdot \dots \cdot n^n$

  • •

    In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.

◌ Explore connections in Graph view