Generalized CRT & Garner's Algorithm

Intuition, Vocabulary and Foundations

A congruence describes a repeating schedule. The statement $x\equiv a\pmod m$ means every valid value differs from $a$ by a multiple of $m$. Combining congruences resembles synchronizing clocks: their requested readings may align periodically, or a shared cycle may make them contradictory.

For example, $x\equiv2\pmod6$ and $x\equiv5\pmod9$ are compatible because $\gcd(6,9)=3$ divides $5-2=3$. Their solutions form one residue class modulo $\operatorname{lcm}(6,9)=18$, namely $x\equiv14\pmod{18}$. In contrast, $x\equiv2\pmod6$ and $x\equiv4\pmod9$ are inconsistent because $3\nmid2$.

The generalized Chinese Remainder Theorem permits non-coprime moduli. Two constraints are compatible exactly when their residues agree modulo the gcd; after a successful merge, the combined modulus is the lcm, not generally the product.

Garner’s algorithm addresses pairwise coprime moduli. It reconstructs a value through mixed-radix digits $x=c_0+c_1m_0+c_2m_0m_1+\cdots$, where $0\le c_i\lt m_i$. Each digit satisfies the next congruence without disturbing previous ones. The representation is unique below $\prod_i m_i$ and can be evaluated exactly or modulo a separate target.

Generalized CRT first checks whether residues agree modulo every shared gcd; only compatible constraints may be merged, and the resulting period is their lcm. Garner’s algorithm instead requires pairwise coprime moduli and replaces a potentially huge direct reconstruction with uniquely determined mixed-radix digits.

Concept	Definition or invariant	Concrete example	Non-example or boundary	Question answered
Normalized congruence	$0\le a\lt m$ with $m\gt0$	$-1\bmod5=4$	A zero modulus is invalid	What canonical residue represents the class?
Compatibility	$\gcd(m,n)\mid(b-a)$	$2\bmod6$ and $5\bmod9$ are compatible	$2\bmod6$ and $4\bmod9$ contradict	Can both constraints hold?
Combined period	$\operatorname{lcm}(m,n)$	Moduli $6$ and $9$ merge to period $18$	Product $54$ is not minimal	What is the unique solution modulus?
Coprime CRT	Pairwise gcds equal $1$	Moduli $3,5,7$	Moduli $6,10$ are not coprime	When is the period the full product?
Mixed-radix digit	$0\le c_i\lt m_i$	For $3,5$, write $x=c_0+3c_1$	Digits are not decimal digits	How is reconstruction built incrementally?
Exact reconstruction	Canonical $x$ below the product	Recover $23$ modulo $3,5,7$	It may overflow a machine word	What is the complete representative?
Modular reconstruction	Compute $x\bmod M$ directly	Recover a coefficient modulo $10^9+7$	It does not reveal exact $x$	How can the full product be avoided?
Uniqueness	One class modulo the merged period	$14\bmod18$ represents all solutions	Infinitely many integer representatives remain	In what sense is reconstruction unique?

Step-by-Step Derivations and Algorithms

To merge $x\equiv a\pmod m$ and $x\equiv b\pmod n$, write $x=a+mt$. Substitution gives $mt\equiv b-a\pmod n$. Let $g=\gcd(m,n)$. A solution exists exactly when $g\mid(b-a)$. Divide by $g$ to obtain

$$ \frac{m}{g}t\equiv\frac{b-a}{g}\pmod{\frac{n}{g}}. $$

The reduced coefficient $m/g$ is invertible modulo $n/g$, so solve for $t$, substitute into $a+mt$, and normalize modulo $m(n/g)=\operatorname{lcm}(m,n)$. Repeating this merge maintains that the current residue class equals the intersection of all processed constraints.

For pairwise coprime moduli, Garner assumes digits $c_0,\ldots,c_{i-1}$ are fixed. If $x_{i-1}$ is their partial mixed-radix value, the next digit satisfies

$$ x_{i-1}+c_i\prod_{j=0}^{i-1}m_j\equiv r_i\pmod{m_i}. $$

The accumulated product is invertible modulo $m_i$, so $c_i$ is unique. Once all digits are known, evaluate them with arbitrary-precision integers or reduce each accumulation step modulo a target.

Generalized CRT & Garner's Algorithm algorithm map

flowchart TD
    A["Normalize residues and moduli"] --> B{"Moduli pairwise coprime?"}
    B -->|No or unknown| C["Merge constraints incrementally"]
    C --> D["Compute shared gcd"]
    D --> E{"Difference divisible by gcd?"}
    E -->|No| F["Report contradiction"]
    E -->|Yes| G["Solve reduced congruence"]
    G --> H["Return residue modulo lcm"]
    B -->|Yes| I["Compute mixed-radix digits"]
    I --> J{"Desired output?"}
    J -->|Exact| K["Evaluate full reconstruction"]
    J -->|Modulo target| L["Evaluate digits modulo target"]

Incremental CRT preserves that the current class is exactly the intersection of all processed constraints; compatibility and the reduced inverse prove each merge. Merging $k$ constraints takes $O(k)$ gcd and inverse operations, while straightforward Garner takes $O(k^2)$ modular operations and $O(k)$ storage.

Implementation, Complexity and Engineering

The reference implementation separates generalized CRT from Garner reconstruction. merge_crt accepts non-coprime moduli and returns None on contradiction. Garner checks pairwise coprimality before producing digits, preventing a nonexistent inverse from being mistaken for an unrelated failure.

Python integers grow automatically. In fixed-width languages, compute lcm as (m / gcd) * n, check multiplication, and use overflow-safe modular multiplication. Modular Garner keeps accumulated products reduced by the target modulus, but digit construction still uses arithmetic modulo the original source moduli.

from math import gcd


def extended_gcd(a, b):
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_x, x = x, old_x - quotient * x
        old_y, y = y, old_y - quotient * y
    return old_r, old_x, old_y


def inverse_mod(value, modulus):
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    divisor, coefficient, _ = extended_gcd(value % modulus, modulus)
    if divisor != 1:
        raise ValueError("inverse does not exist")
    return coefficient % modulus


def normalize_congruence(residue, modulus):
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    return residue % modulus, modulus


def merge_crt(left, right):
    a, m = normalize_congruence(*left)
    b, n = normalize_congruence(*right)
    common = gcd(m, n)
    difference = b - a
    if difference % common != 0:
        return None

    reduced_m = m // common
    reduced_n = n // common
    step = 0 if reduced_n == 1 else (
        difference // common * inverse_mod(reduced_m, reduced_n)
    ) % reduced_n

    combined_modulus = m * reduced_n
    combined_residue = (a + m * step) % combined_modulus
    return combined_residue, combined_modulus


def generalized_crt(congruences):
    result = (0, 1)
    for congruence in congruences:
        result = merge_crt(result, congruence)
        if result is None:
            return None
    return result


def require_pairwise_coprime(moduli):
    for i, left in enumerate(moduli):
        if left <= 1:
            raise ValueError("Garner moduli must exceed 1")
        for right in moduli[:i]:
            if gcd(left, right) != 1:
                raise ValueError("Garner moduli must be pairwise coprime")


def garner_digits(residues, moduli):
    if len(residues) != len(moduli):
        raise ValueError("residue and modulus counts differ")
    require_pairwise_coprime(moduli)
    digits = []
    for i, (residue, modulus) in enumerate(zip(residues, moduli)):
        partial = 0
        multiplier = 1
        for j in range(i):
            partial = (partial + digits[j] * multiplier) % modulus
            multiplier = (multiplier * moduli[j]) % modulus
        digit = (
            (residue - partial) * inverse_mod(multiplier, modulus)
        ) % modulus
        digits.append(digit)
    return digits


def garner_exact(residues, moduli):
    digits = garner_digits(residues, moduli)
    value = 0
    multiplier = 1
    for digit, modulus in zip(digits, moduli):
        value += digit * multiplier
        multiplier *= modulus
    return value, multiplier


def garner_mod(residues, moduli, target_modulus):
    if target_modulus <= 0:
        raise ValueError("target modulus must be positive")
    digits = garner_digits(residues, moduli)
    value = 0
    multiplier = 1
    for digit, modulus in zip(digits, moduli):
        value = (value + digit * multiplier) % target_modulus
        multiplier = (multiplier * modulus) % target_modulus
    return value


assert merge_crt((2, 6), (5, 9)) == (14, 18)
assert merge_crt((2, 6), (4, 9)) is None
assert generalized_crt([(2, 6), (5, 9), (14, 18)]) == (14, 18)
assert generalized_crt([(-1, 5), (2, 3)]) == (14, 15)
assert generalized_crt([]) == (0, 1)

residues = [2, 3, 2]
moduli = [3, 5, 7]
digits = garner_digits(residues, moduli)
exact, product = garner_exact(residues, moduli)
assert digits == [2, 2, 1]
assert exact == 23 and product == 105
assert all(exact % m == r for r, m in zip(residues, moduli))

for target in (2, 11, 97, 1_000_000_007):
    assert garner_mod(residues, moduli, target) == exact % target

try:
    garner_digits([1, 2], [6, 10])
    raise AssertionError("non-coprime Garner input was accepted")
except ValueError:
    pass

try:
    merge_crt((1, 0), (2, 3))
    raise AssertionError("zero modulus was accepted")
except ValueError:
    pass

print("all tests passed")

Method or choice	Preconditions	Complexity	Numeric risk	Failure mode	Mitigation
Incremental generalized CRT	Positive moduli	$O(k)$ gcd and inverse operations	Merged lcm grows rapidly	Skipping compatibility	Check the difference modulo the gcd
Coprime product CRT	Pairwise coprime moduli	$O(k)$ inverses plus reconstruction	Large product and weighted terms	Using shared-factor moduli	Verify pairwise gcds or merge generally
Straightforward Garner	Pairwise coprime moduli	$O(k^2)$ time, $O(k)$ space	Exact evaluation products grow	Inverse does not exist	Validate the domain before digit construction
Garner modulo target	Pairwise coprime sources, positive target	$O(k^2)$	Source arithmetic still needs safety	Confusing modular and exact output	Name the target and document information loss
Arbitrary precision	Valid algorithmic inputs	Operand-length-dependent	Allocation and multiplication cost	Assuming constant-time arithmetic	Include bit complexity
Fixed-width integers	All intermediates fit	Fast native operations	Silent lcm or product overflow	Correct residue with corrupted modulus	Divide first and use checked operations
Normalized residues	Positive modulus	$O(1)$ per constraint	Minimal	Comparing negative representatives	Normalize at the input boundary
Brute-force oracle	Small combined period	Up to the lcm	Impractical at scale	Deploying the oracle	Reserve it for differential tests

Applications, Case Studies and Exercises

Generalized CRT suits schedules, counters, and constraints whose moduli may share factors. Garner is especially useful when a large integer or polynomial coefficient was computed modulo several machine-friendly primes and only a final modular value is required.

Practice

Apply Generalized CRT & Garner's Algorithm

Case study 1 — synchronize non-coprime schedules. Merge $x\equiv2\pmod6$ and $x\equiv5\pmod9$. Compute $g=3$, verify compatibility, solve the reduced congruence, and obtain $x\equiv14\pmod{18}$. Replace the second residue with $4$ and explain the contradiction. Success means every accepted result satisfies both inputs and every rejected pair disagrees modulo the gcd.

Case study 2 — reconstruct a large convolution coefficient. Suppose an NTT pipeline returns one coefficient modulo three pairwise coprime transform primes. Compute its Garner digits, evaluate the exact representative when a coefficient bound guarantees uniqueness, and separately evaluate it modulo an application modulus. Verify every source residue and record the source-modulus product.

Hands-on comparison. Generate one thousand seeded systems with two to six small moduli. Compare generalized CRT with brute force through the lcm. For pairwise coprime systems, compare generalized CRT, exact Garner, and modular Garner. Include negative residues, redundant constraints, modulus $1$ in generalized CRT, and deliberate contradictions. Success means all valid methods agree and invalid Garner domains are rejected.

Tiered exercises. Recall: state the gcd compatibility condition. Derive: prove the merged modulus is the lcm. Implement: return the first solution inside a closed interval. Debug: expose overflow from computing $mn/g$ instead of $(m/g)n$. Extend: precompute Garner inverses for repeated reconstructions with a fixed modulus set.

Use incremental generalized CRT when moduli may share factors or contradictions require diagnosis; use Garner when source moduli are pairwise coprime and mixed-radix or target-modular reconstruction avoids unwieldy products. Always distinguish a canonical residue class, an exact representative justified by an external size bound, and a value reconstructed only modulo another modulus.

Cookie Consent