Linear Congruences & Chinese Remainder Theorem

Intuition, Vocabulary and Foundations

A congruence describes a repeating constraint rather than one isolated integer. For example, $x\equiv2\pmod5$ means that $x$ may be $2,7,12,17$, or any integer differing from $2$ by a multiple of $5$. An everyday analogy is a repeating schedule: if a task occurs every five days and its next occurrence is two days after a reference date, every occurrence has the same residue modulo $5$.

A linear congruence has the form

$$ ax\equiv b\pmod m, \qquad m\ge1. $$

This is equivalent to $m\mid(ax-b)$ and therefore to the linear Diophantine equation $ax-my=b$. Let $d=\gcd(a,m)$. Bézout's identity shows that a solution exists exactly when $d\mid b$.

If $d\mid b$, division by $d$ gives

$$ \frac adx\equiv\frac bd\pmod{\frac md}. $$

The reduced coefficient is coprime to the reduced modulus, so it has an inverse. A reduced solution is

$$ x_0\equiv\frac bd\left(\frac ad\right)^{-1}\pmod{\frac md}. $$

Modulo the original modulus, there are exactly $d$ solutions:

$$ x=x_0+k\frac md, \qquad 0\le k\lt d. $$

For example, $12x\equiv18\pmod{30}$ has $d=6$. Reduction gives $2x\equiv3\pmod5$, hence $x\equiv4\pmod5$. Its six solutions modulo $30$ are $4,9,14,19,24,29$.

The Chinese Remainder Theorem combines residue constraints. For

$$ x\equiv r_1\pmod{m_1}, \qquad x\equiv r_2\pmod{m_2}, $$

let $g=\gcd(m_1,m_2)$. The constraints are compatible exactly when $g\mid(r_2-r_1)$. When compatible, their common solutions form one residue class modulo $\operatorname{lcm}(m_1,m_2)$. If the moduli are coprime, compatibility is automatic and the answer is unique modulo $m_1m_2$.

Step-by-Step Derivations and Algorithms

To solve $ax\equiv b\pmod m$, normalize $a$ and $b$ modulo $m$, then compute $d=\gcd(a,m)$. If $d\nmid b$, no solution exists because every integer combination of $a$ and $m$ is divisible by $d$.

When $d\mid b$, define

$$ a'=\frac ad, \qquad b'=\frac bd, \qquad m'=\frac md. $$

Since $\gcd(a',m')=1$, extended Euclid supplies $(a')^{-1}$ modulo $m'$, and

$$ x_0\equiv b'(a')^{-1}\pmod{m'}. $$

The compact result $(x_0,m',d)$ represents the $d$ solutions modulo $m$: begin at $x_0$, advance by $m'$, and stop after $d$ residues. This avoids allocating a large list when $d$ is large.

To merge two congruences, write $x=r_1+m_1k$ and substitute into the second one:

$$ m_1k\equiv r_2-r_1\pmod{m_2}. $$

Extended Euclid produces $s,t$ satisfying $sm_1+tm_2=g$, where $g=\gcd(m_1,m_2)$. If $g\nmid(r_2-r_1)$, the system is inconsistent. Otherwise,

$$ k\equiv\frac{r_2-r_1}{g}s\pmod{\frac{m_2}{g}}. $$

The merged residue is $r=r_1+m_1k$, normalized modulo

$$ M=\operatorname{lcm}(m_1,m_2)=m_1\frac{m_2}{g}. $$

Incremental CRT begins with the identity constraint $x\equiv0\pmod1$ and merges one constraint at a time. After every successful merge, $(r,M)$ represents exactly the integers satisfying all constraints processed so far.

flowchart TD
    A["Normalize coefficients and residues"] --> B{"Single congruence?"}
    B -->|Yes| C["Compute coefficient-modulus gcd"]
    C --> D{"Does gcd divide target?"}
    D -->|No| E["Report no solution"]
    D -->|Yes| F["Reduce and invert coefficient"]
    B -->|No| G["Start with residue 0 modulo 1"]
    G --> H["Merge next constraint"]
    H --> I{"Residues agree modulo gcd?"}
    I -->|No| E
    I -->|Yes| J["Update residue modulo lcm"]
    J --> K{"More constraints?"}
    K -->|Yes| H
    K -->|No| L["Return canonical residue and period"]

Implementation, Complexity and Engineering

A robust interface rejects nonpositive moduli, normalizes every residue, distinguishes inconsistency from a valid zero residue, and returns the combined modulus with the residue. For a linear congruence, returning a base, step, and count is more scalable than eagerly listing all solutions.

The expression $m_1(m_2/g)$ computes the lcm more safely than $(m_1m_2)/g$, but it can still exceed a fixed-width type. Production code should use checked multiplication, a wider integer type, or arbitrary-precision integers. The same concern applies to $m_1k$ while constructing a merged residue.

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    old_r, r = abs(a), abs(b)
    old_s, s = 1, 0
    old_t, t = 0, 1

    while r:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    x = -old_s if a < 0 else old_s
    y = -old_t if b < 0 else old_t
    return old_r, x, y


def modular_inverse(value: int, modulus: int) -> int:
    if modulus <= 1:
        raise ValueError("inverse requires modulus greater than one")
    value %= modulus
    gcd, coefficient, _ = extended_gcd(value, modulus)
    if gcd != 1:
        raise ValueError("inverse does not exist")
    return coefficient % modulus


def solve_linear_congruence(
    coefficient: int,
    target: int,
    modulus: int,
) -> tuple[int, int, int] | None:
    """Return (base, step, count), or None if inconsistent."""
    if modulus <= 0:
        raise ValueError("modulus must be positive")

    coefficient %= modulus
    target %= modulus
    gcd, _, _ = extended_gcd(coefficient, modulus)
    if target % gcd != 0:
        return None

    reduced_modulus = modulus // gcd
    if reduced_modulus == 1:
        base = 0
    else:
        reduced_coefficient = coefficient // gcd
        reduced_target = target // gcd
        inverse = modular_inverse(reduced_coefficient, reduced_modulus)
        base = (reduced_target * inverse) % reduced_modulus

    return base, reduced_modulus, gcd


def expand_linear_solutions(
    solution: tuple[int, int, int],
    modulus: int,
) -> list[int]:
    base, step, count = solution
    return [(base + index * step) % modulus for index in range(count)]


def merge_congruences(
    residue_a: int,
    modulus_a: int,
    residue_b: int,
    modulus_b: int,
) -> tuple[int, int] | None:
    if modulus_a <= 0 or modulus_b <= 0:
        raise ValueError("moduli must be positive")

    residue_a %= modulus_a
    residue_b %= modulus_b
    gcd, bezout_a, _ = extended_gcd(modulus_a, modulus_b)
    difference = residue_b - residue_a

    if difference % gcd != 0:
        return None

    reduced_b = modulus_b // gcd
    correction = ((difference // gcd) * bezout_a) % reduced_b
    combined_modulus = modulus_a * reduced_b
    combined_residue = (residue_a + modulus_a * correction) % combined_modulus
    return combined_residue, combined_modulus


def chinese_remainder(
    congruences: list[tuple[int, int]],
) -> tuple[int, int] | None:
    residue, modulus = 0, 1

    for next_residue, next_modulus in congruences:
        merged = merge_congruences(
            residue,
            modulus,
            next_residue,
            next_modulus,
        )
        if merged is None:
            return None
        residue, modulus = merged

    return residue, modulus


linear = solve_linear_congruence(12, 18, 30)
assert linear == (4, 5, 6)
assert expand_linear_solutions(linear, 30) == [4, 9, 14, 19, 24, 29]

assert solve_linear_congruence(6, 5, 9) is None
assert solve_linear_congruence(-3, -6, 9) == (2, 3, 3)
assert solve_linear_congruence(0, 0, 7) == (0, 1, 7)
assert solve_linear_congruence(0, 3, 7) is None

assert merge_congruences(2, 3, 3, 5) == (8, 15)
assert merge_congruences(4, 6, 10, 14) == (10, 42)
assert merge_congruences(4, 6, 9, 14) is None

assert chinese_remainder([(2, 3), (3, 5), (2, 7)]) == (23, 105)
assert chinese_remainder([(-1, 4), (5, 6)]) == (11, 12)
assert chinese_remainder([]) == (0, 1)
assert chinese_remainder([(0, 1), (7, 10)]) == (7, 10)
assert chinese_remainder([(1, 2), (0, 4)]) is None

for operation in (
    lambda: solve_linear_congruence(1, 1, 0),
    lambda: merge_congruences(0, -3, 1, 5),
    lambda: chinese_remainder([(2, 0)]),
):
    try:
        operation()
        raise AssertionError("expected ValueError")
    except ValueError:
        pass

print("all congruence and CRT tests passed")

Applications, Case Studies and Exercises

Congruence systems model repeating schedules, synchronized counters, rotating identifiers, calendar calculations, sharded storage layouts, and reconstruction from smaller arithmetic channels. The compatibility test is also an engineering diagnostic: it distinguishes “no synchronized time exists” from “the search has not run long enough.”

A reliable oracle substitutes the returned residue into every original congruence. Useful properties include invariance under adding multiples of an input modulus, equivalence under reordered constraints, agreement with brute force on small systems, and a combined modulus equal to the lcm of compatible input moduli.