#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/chinese-remainder-theorem

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/chinese-remainder-theorem

Repovive

Chinese Remainder Theorem - Algorithm Tutorial | Repovive | Repovive

Repovive.

Back to Algorithms

Chinese Remainder Theorem Algorithm Tutorial

hardNumber Theory9 min read

Introduction

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory. It states that if you know the remainders of an integer when divided by several pairwise coprime numbers, you can uniquely determine the remainder when divided by their product.

Historical context: The theorem appears in the 3rd century Chinese text Sunzi Suanjing, where it was used to solve problems about counting soldiers.

Problem statement: Given a system of congruences: $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ $\vdots$ $x \equiv a_n \pmod{m_n}$

where $\gcd(m_i, m_j) = 1$ for all $i \ne j$ , there exists a unique solution modulo $M = m_1 \cdot m_2 \cdot \ldots \cdot m_n$ .

The Classical Construction

The classical CRT proof gives an explicit formula for the solution.

Setup:

Let $M = m_1 \cdot m_2 \cdot \ldots \cdot m_n$
Let $M_i = M / m_i$ (product of all moduli except $m_i$ )
Let $y_i = M_i^{-1} \pmod{m_i}$ (modular inverse of $M_i$ mod $m_i$ )

The solution: $x = \sum_{i=1}^{n} a_i \cdot M_i \cdot y_i \pmod{M}$

Why it works:

$M_i \cdot y_i \equiv 1 \pmod{m_i}$
$M_i \cdot y_i \equiv 0 \pmod{m_j}$ for $j \ne i$ (since $m_j | M_i$ )

So the $i$ -th term contributes $a_i$ modulo $m_i$ and 0 modulo all other $m_j$ .

Iterative Approach

A simpler approach combines equations one at a time.

Algorithm:

text

function solve_crt(equations):
    x = equations[0].remainder
    mod = equations[0].modulus

    for each (a, m) in equations[1:]:
        // Find k such that: x + k * mod ≡ a (mod m)
        // k ≡ (a - x) * mod^(-1) (mod m)
        inv = modular_inverse(mod, m)
        k = ((a - x) * inv) mod m
        if k < 0: k += m

        x = x + k * mod
        mod = mod * m
        x = x mod mod

    return x

Why it works: After processing the first $i$ equations, $x$ satisfies all of them modulo $\text{lcm}(m_1, \ldots, m_i)$ . Since all moduli are coprime, this LCM is just their product.

Modular Inverse via Extended GCD

To find the modular inverse, we use the Extended Euclidean Algorithm.

Extended GCD: Given $a$ and $b$ , find $x, y$ such that $ax + by = \gcd(a, b)$ .

text

function extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)

    (g, x, y) = extended_gcd(b, a mod b)
    return (g, y, x - (a / b) * y)

Modular inverse: If $\gcd(a, m) = 1$ , then: $ax + my = 1$ $ax \equiv 1 \pmod{m}$

So $x$ (reduced mod $m$ ) is the modular inverse of $a$ mod $m$ .

text

function modular_inverse(a, m):
    (g, x, _) = extended_gcd(a, m)
    if g != 1: error("No inverse")
    return ((x mod m) + m) mod m

Implement this Algorithm

Go to Problem

Introduction

The Classical Construction

Iterative Approach

Modular Inverse via Extended GCD

Implement this Algorithm

Applications