Chinese Remainder Theorem: Mathematical Algorithm Deep Dive

1. Introduction and Core Concepts

The chinese remainder theorem is one of the most elegant and practically useful results in number theory, bridging ancient mathematics with modern computer science. First documented in the 3rd-century Chinese mathematical text Sunzi Suanjing, the theorem addresses a deceptively simple question: can we reconstruct an integer from its remainders modulo several different numbers? The answer, under the right conditions, is a resounding yes, and the reconstruction is unique within a specific range.

At its core, the chinese remainder theorem states that if we have a system of simultaneous congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ a_k (mod n_k) where the moduli n₁, n₂, ..., n_k are pairwise coprime (meaning no two share a common divisor greater than 1), then there exists a unique solution for x modulo N = n₁ * n₂ * ... * n_k. This uniqueness is powerful because it guarantees not only existence but also a systematic way to find the solution.

Why does the chinese remainder theorem matter for programmers and system designers today? The theorem enables us to decompose large computations into smaller, independent computations that can be performed in parallel and then recombined. This divide-and-conquer property is fundamental to high-performance cryptography, distributed storage, and efficient arithmetic with large integers. Instead of working directly with a 2048-bit integer, for example, we can work with its residues modulo several smaller, coprime numbers, perform operations independently, and reconstruct the final result. This approach reduces computational complexity and enables parallelism that would be impossible otherwise.

The Fundamental Problem Statement

Formally, we are given k pairs (a_i, n_i) where a_i is the remainder and n_i is the modulus. We seek the smallest non-negative integer x that satisfies all k congruences simultaneously. The classic puzzle that illustrates this is: find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. The chinese remainder theorem not only proves such a number exists but provides a constructive algorithm to find it, which in this case is 23.

Understanding the theorem requires familiarity with modular arithmetic, greatest common divisors (GCD), and modular inverses. A modular inverse of a modulo m exists if and only if gcd(a, m) = 1, which is why the pairwise coprime condition is essential for the classic form. When this condition holds, each modulus has an inverse modulo every other modulus, allowing the construction of orthogonal basis elements that isolate each congruence.

2. How It Works

The mechanism behind the chinese remainder theorem is constructive and ingenious. The standard construction defines N as the product of all moduli, and for each i, defines N_i = N / n_i. Because the moduli are pairwise coprime, N_i and n_i are also coprime, which guarantees that N_i has a modular inverse modulo n_i. Let M_i be this inverse, meaning N_i * M_i ≡ 1 (mod n_i). The solution is then assembled as x = Σ (a_i * N_i * M_i) mod N.

To understand why this works, consider the term e_i = N_i * M_i. By construction, e_i ≡ 1 (mod n_i) because M_i is the inverse of N_i modulo n_i. Crucially, for any j ≠ i, e_i ≡ 0 (mod n_j) because N_i contains n_j as a factor (since N_i = N / n_i). Therefore, when we compute the sum x = Σ a_i * e_i, taking x modulo n_i eliminates all terms except the i-th term, leaving x ≡ a_i * 1 ≡ a_i (mod n_i). This orthogonality is the heart of the theorem.

The proof of uniqueness is equally important. Suppose there were two solutions x and y both satisfying the system. Then x - y ≡ 0 (mod n_i) for every i, meaning each n_i divides x - y. Since the n_i are pairwise coprime, their product N must also divide x - y, so x ≡ y (mod N). Thus any two solutions are congruent modulo N, meaning there is exactly one solution in the range [0, N-1]. This uniqueness makes the theorem deterministic and reliable for algorithmic use.

Intuition Through Basis Construction

Another way to visualize the chinese remainder theorem is as a number system transformation, analogous to the Chinese remainder representation. Just as we can represent a vector in terms of basis vectors, we can represent an integer x by its vector of residues (a₁, a₂, ..., a_k). The e_i values act as basis vectors in this residue space. This is similar to the principle behind the Discrete Fourier Transform or Lagrange interpolation, where a function is reconstructed from its values at specific points using basis polynomials that are 1 at one point and 0 at all others.

When moduli are not pairwise coprime, the classic construction fails, but a generalized version exists. A system with arbitrary moduli has a solution if and only if for every pair i, j, the remainders are consistent modulo the GCD: a_i ≡ a_j (mod gcd(n_i, n_j)). If this condition holds, the solution is unique modulo the least common multiple (LCM) of the moduli, not the product. This generalization is critical for real-world implementations where moduli may not be conveniently coprime.

3. Implementation

Implementing the chinese remainder theorem in Python requires two foundational building blocks: the extended Euclidean algorithm to compute GCDs and modular inverses, and the main CRT combination logic. Python's built-in integers handle arbitrary precision, making it ideal for demonstrating CRT with large numbers without overflow concerns that plague lower-level languages.

The extended Euclidean algorithm is preferred over brute-force search for modular inverses because it runs in O(log min(a, m)) time. It finds integers x and y such that a*x + m*y = gcd(a, m). When gcd(a, m) = 1, x is the modular inverse of a modulo m. This algorithm is iterative, efficient, and numerically stable.

# Extended Euclidean Algorithm and Modular Inverse
def extended_gcd(a, b):
    """
    Returns (g, x, y) such that a*x + b*y = g = gcd(a, b)
    Iterative version to avoid recursion limits for large numbers.
    """
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while b != 0:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def mod_inverse(a, m):
    """
    Returns the modular inverse of a modulo m.
    Requires gcd(a, m) == 1, otherwise raises ValueError.
    Result is in range [0, m-1].
    """
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError(f"No inverse: gcd({a}, {m}) = {g} != 1")
    # x may be negative, normalize to positive range
    return x % m

# Example: inverse of 3 mod 11 is 4 because 3*4 = 12 ≡ 1 (mod 11)
print(mod_inverse(3, 11))  # Output: 4
print(mod_inverse(10, 17)) # Output: 12 because 10*12=120 ≡ 1 (mod 17)

With modular inverses available, the classic CRT for pairwise coprime moduli becomes straightforward. The implementation follows the constructive proof directly: compute N, then for each congruence compute N_i, its inverse M_i, and accumulate the sum. The final result is reduced modulo N to ensure it lies in the canonical range.

def crt_coprime(remainders, moduli):
    """
    Classic Chinese Remainder Theorem for pairwise coprime moduli.
    Solves x ≡ remainders[i] (mod moduli[i]) for all i.
    
    Args:
        remainders: list of a_i values
        moduli: list of n_i values, must be pairwise coprime
    
    Returns:
        (x, N) where x is the unique solution in [0, N-1] and N = product(moduli)
    """
    if len(remainders) != len(moduli):
        raise ValueError("remainders and moduli must have same length")
    
    # Compute product N = n1 * n2 * ... * nk
    N = 1
    for n in moduli:
        if n <= 0:
            raise ValueError("Moduli must be positive")
        N *= n
    
    result = 0
    for a_i, n_i in zip(remainders, moduli):
        N_i = N // n_i              # Product of all moduli except n_i
        M_i = mod_inverse(N_i, n_i) # Inverse of N_i modulo n_i
        # e_i = N_i * M_i is 1 mod n_i and 0 mod n_j for j != i
        result += a_i * N_i * M_i
    
    # Normalize to [0, N-1]
    return result % N, N

# Classic puzzle: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
x, N = crt_coprime([2, 3, 2], [3, 5, 7])
print(f"x = {x} mod {N}")  # Output: x = 23 mod 105
# Verify: 23 % 3 = 2, 23 % 5 = 3, 23 % 7 = 2
for a, n in zip([2, 3, 2], [3, 5, 7]):
    assert x % n == a

For production systems where moduli may not be coprime, a generalized implementation is essential. This version merges congruences incrementally, checking consistency at each step and using the LCM instead of the product. It can detect unsolvable systems early and handles large inputs gracefully.

def crt_general(remainders, moduli):
    """
    Generalized CRT that works for arbitrary (not necessarily coprime) moduli.
    Merges congruences pairwise using extended GCD.
    Returns (x, M) where M = lcm(moduli) if solvable, else raises ValueError.
    """
    if not remainders:
        return 0, 1
    
    # Start with first congruence: x ≡ a0 (mod n0)
    x = remainders[0] % moduli[0]
    M = moduli[0]
    
    for a_i, n_i in zip(remainders[1:], moduli[1:]):
        a_i = a_i % n_i
        g, p, q = extended_gcd(M, n_i)
        
        # Check consistency: a_i ≡ x (mod g) must hold
        if (a_i - x) % g != 0:
            raise ValueError(
                f"Inconsistent system: x ≡ {x} (mod {M}) "
                f"and x ≡ {a_i} (mod {n_i}) have no solution"
            )
        
        # Merge: find solution modulo lcm(M, n_i) = M * n_i / g
        lcm = M // g * n_i
        # Compute combined solution
        # x_new = x + M * ((a_i - x)/g * p mod n_i/g)
        diff_div_g = (a_i - x) // g
        # p is inverse of M/g modulo n_i/g
        mod = n_i // g
        increment = (diff_div_g * p) % mod
        x = (x + M * increment) % lcm
        M = lcm
    
    return x, M

# Example with non-coprime but solvable system:
# x ≡ 2 (mod 4), x ≡ 6 (mod 6) -> check: 2 ≡ 6 (mod 2) true, solution exists
x, M = crt_general([2, 6], [4, 6])
print(f"General CRT: x = {x} mod {M}")  # Output: x = 6 mod 12
# Example unsolvable: x ≡ 1 (mod 4), x ≡ 2 (mod 6) -> 1 != 2 mod 2
try:
    crt_general([1, 2], [4, 6])
except ValueError as e:
    print(f"Correctly detected unsolvable: {e}")

A fourth implementation demonstrates Garner's algorithm, which is numerically superior for large moduli because it avoids computing the huge product N directly and instead reconstructs the answer in a mixed-radix representation. This is the preferred method in cryptographic libraries.

def garner_crt(remainders, moduli):
    """
    Garner's algorithm for CRT - more efficient and avoids large intermediate N.
    Works for pairwise coprime moduli. Returns x in [0, N-1].
    Uses mixed-radix representation for better numerical stability.
    """
    k = len(remainders)
    # Precompute inverses: inv[i][j] = moduli[i]^{-1} mod moduli[j] for i < j
    # For Garner, we need inverse of moduli[i] modulo moduli[j]
    coeffs = [0] * k
    for i in range(k):
        coeffs[i] = remainders[i]
        for j in range(i):
            # Compute moduli[j] inverse modulo moduli[i]
            inv = mod_inverse(moduli[j] % moduli[i], moduli[i])
            coeffs[i] = (inv * (coeffs[i] - coeffs[j])) % moduli[i]
    
    # Reconstruct x from mixed-radix coefficients
    x = coeffs[k-1]
    for i in range(k-2, -1, -1):
        x = x * moduli[i] + coeffs[i]
    
    # Alternative simpler iterative Garner for clarity:
    # x = a0, M = n0
    # for i from 1 to k-1:
    #   inv = M^{-1} mod n_i
    #   t = ((a_i - x) * inv) % n_i
    #   x = x + M * t
    #   M *= n_i
    # This is equivalent and easier to verify
    
    # Verify with iterative method for correctness
    x_iter = remainders[0] % moduli[0]
    M = moduli[0]
    for i in range(1, k):
        inv = mod_inverse(M % moduli[i], moduli[i])
        t = ((remainders[i] - x_iter) * inv) % moduli[i]
        x_iter = x_iter + M * t
        M *= moduli[i]
    
    return x_iter % M, M

x, N = garner_crt([2, 3, 2], [3, 5, 7])
print(f"Garner result: x = {x} mod {N}")  # 23 mod 105
# Handles larger moduli efficiently without overflow of N intermediate
x2, N2 = garner_crt([123, 456, 789], [1009, 1013, 1019])
print(f"Large moduli: x = {x2} mod {N2}")

4. Step-by-Step Example

To make the chinese remainder theorem concrete, let us walk through the classic example in exhaustive detail: find x such that x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7). First, we verify the moduli 3, 5, and 7 are pairwise coprime: gcd(3,5)=1, gcd(3,7)=1, gcd(5,7)=1. The product N = 3 * 5 * 7 = 105, so we expect a unique solution modulo 105.

Step 1 is to compute each N_i = N / n_i. We get N₁ = 105 / 3 = 35, N₂ = 105 / 5 = 21, and N₃ = 105 / 7 = 15. Notice how each N_i is divisible by all moduli except its own: 35 is divisible by 5 and 7 but not 3, 21 is divisible by 3 and 7 but not 5, and 15 is divisible by 3 and 5 but not 7. This divisibility property is what creates the zeroing effect in the sum.

Step 2 is to find each modular inverse M_i = N_i^-1 (mod n_i). For M₁, we need the inverse of 35 modulo 3. Since 35 mod 3 = 2, we need x such that 2*x ≡ 1 (mod 3), which gives x = 2 because 2*2=4 ≡1 (mod 3). For M₂, we need inverse of 21 modulo 5: 21 mod 5 =1, and 1*1 ≡1 (mod 5), so M₂=1. For M₃, inverse of 15 modulo 7: 15 mod 7=1, so M₃=1 as well. In more complex examples, we would use the extended Euclidean algorithm here.

Assembling the Final Solution

Step 3 is to compute each term a_i * N_i * M_i. Term 1: 2 * 35 * 2 = 140. Term 2: 3 * 21 * 1 = 63. Term 3: 2 * 15 * 1 = 30. Summing these gives 140 + 63 + 30 = 233. Finally, we reduce modulo N: 233 mod 105 = 233 - 2*105 = 233 -210 =23. Thus x=23 is our solution.

Verification is immediate: 23 divided by 3 leaves remainder 2, 23 divided by 5 leaves remainder 3 (since 5*4=20, remainder 3), and 23 divided by 7 leaves remainder 2 (since 7*3=21, remainder 2). All three congruences are satisfied, and any other solution must be of the form 23 + 105*k for integer k, such as 128, 233, or -82.

Consider what happens if we attempted brute force instead. We could simply test integers 0,1,2,... checking each against all three congruences until we find a match. For N=105 this is trivial, but for cryptographic moduli where N might be 2²⁰⁴⁸, brute force is computationally impossible. The CRT construction finds the answer in O(k log N) time regardless of how large N is, demonstrating its algorithmic superiority.

5. Complexity Analysis

The efficiency of the chinese remainder theorem depends on the cost of three operations: computing GCDs and modular inverses, performing modular multiplications, and handling large integers. For k congruences with moduli up to M and product N, the classic construction requires k modular inverses, each costing O(log M) using the extended Euclidean algorithm, plus O(k) multiplications of numbers up to size N. Since N can be exponentially larger than M, the bit-complexity matters.

In terms of bit operations, if each modulus has at most b bits, then N has at most k*b bits. Multiplying numbers of size k*b bits costs O((k*b) log(k*b)) with modern algorithms like Karatsuba or FFT-based multiplication, though Python uses Karatsuba and Toom-Cook for large integers. The extended Euclidean algorithm on b-bit numbers costs O(b²) with naive arithmetic or O(b log² b) with faster methods. For most practical purposes with k < 100 and b < 2048, the runtime is negligible.

Garner's algorithm improves the constant factors by avoiding the explicit computation of N and the large intermediate products N_i * M_i. Instead, it works incrementally with numbers that grow gradually, keeping intermediate values smaller on average. This is particularly important in embedded systems or when using fixed-width integer types where overflow is a concern. The asymptotic complexity remains similar, but the practical performance is better and numerical stability is higher.

Space complexity is dominated by the storage of the moduli, remainders, and the product N. The classic method needs O(k) integers of size up to N, while Garner's method can be implemented with O(1) extra space beyond the input arrays if done iteratively. For the generalized CRT, we also need to store intermediate LCM values, which are bounded by N.

When analyzing the chinese remainder theorem for interviews or system design, emphasize that the bottleneck is almost always the extended Euclidean algorithm and large integer multiplication, both of which are highly optimized in modern libraries. For k=2 or k=3 with 32-bit moduli, CRT is effectively O(1). The exponential gap between CRT's O(k log M) and brute force's O(N) is what makes CRT indispensable for large-scale problems.

6. Variations and Optimizations

The classic chinese remainder theorem assumes pairwise coprime moduli, but several important variations extend its applicability. The generalized CRT handles arbitrary moduli by checking consistency modulo GCDs and merging congruences pairwise. This is essential when moduli are not under our control, such as when reconstructing a timestamp from multiple periodic sensors with overlapping periods.

Garner's algorithm is the most significant optimization for the coprime case. Instead of computing the large sum Σ a_i N_i M_i, Garner converts the residue representation into a mixed-radix representation. The mixed-radix coefficients c_i are computed iteratively: c₀ = a₀, and for i > 0, c_i = (a_i - Σ_j<i c_j * P_j) * inv(P_j) mod n_i, where P_j is the product of previous moduli. This avoids ever forming the full product N until the final reconstruction, reducing intermediate overflow and improving cache locality.

Another powerful variation is the use of CRT for polynomial and secret sharing contexts. In Shamir's Secret Sharing, a secret is encoded as the constant term of a polynomial, and shares are points on the polynomial. While this uses Lagrange interpolation rather than CRT directly, the underlying principle of reconstructing a value from residues is identical, and CRT can be used to implement threshold schemes with integer moduli instead of finite fields.

Performance Optimizations in Practice

For repeated CRT computations with the same moduli, precomputation is the dominant optimization. The values N_i and M_i depend only on the moduli, not the remainders, so they can be computed once and reused for many different remainder vectors. In RSA-CRT decryption, for example, the primes p and q are fixed for a given key, so the CRT coefficients are precomputed at key generation time and reused for every decryption operation, yielding a 3-4x speedup.

Parallelization is another natural optimization. Since each term a_i * N_i * M_i can be computed independently, the classic CRT construction is embarrassingly parallel across k cores. For large k (hundreds of moduli), this can provide near-linear speedup. Garner's algorithm is inherently sequential due to its iterative nature, so the choice between classic and Garner involves a tradeoff between numerical stability and parallelizability.

For very large integers where even Python's big integers become slow, the Residue Number System (RNS) uses CRT as its foundation to perform addition, subtraction, and multiplication entirely in the residue domain without ever reconstructing the full integer until needed. This is used in digital signal processing and high-performance arithmetic units where carry propagation in large adders is a bottleneck.

7. Real-World Applications

The chinese remainder theorem is far from a theoretical curiosity; it underpins critical infrastructure in cryptography, distributed systems, and computer architecture. Its ability to decompose large problems into smaller independent subproblems makes it a fundamental tool for performance and reliability.

In cryptography, the most famous application is RSA decryption using CRT. Standard RSA decryption computes m = c^d mod N where N = p*q is a 2048-bit modulus and d is the private exponent. This requires modular exponentiation with 2048-bit numbers, which is expensive. With CRT, we instead compute m_p = c^{d mod (p-1)} mod p and m_q = c^{d mod (q-1)} mod q using the much smaller primes p and q (1024 bits each), then combine via CRT to get m. Since exponentiation cost is cubic in bit length, this is roughly 4 times faster and is used in every modern TLS implementation and smart card.

In distributed systems and databases, CRT enables elegant solutions for data sharding and consistent hashing. Imagine a database that shards user records across multiple servers based on user ID modulo different numbers. CRT can help determine a global ordering or reconstruct a composite key from its shards. Similarly, in calendar and scheduling systems, CRT solves problems like finding the next time that multiple periodic events coincide, such as bus schedules or satellite orbits with different periods.

Error-correcting codes and secret sharing also rely heavily on CRT. The redundant residue number system uses extra moduli to detect and correct errors: if one residue is corrupted, the remaining residues still contain enough information to reconstruct the original number or detect the fault. This is analogous to RAID storage but for numerical data, and is used in fault-tolerant computing for aerospace applications where radiation can flip bits.

Beyond these, the chinese remainder theorem appears in unexpected places: in music theory for describing rhythmic patterns that align after different numbers of beats, in compiler optimizations for loop unrolling with different strides, and in network protocols for fragment reassembly where packet sequence numbers wrap around modulo different values.

8. Comparison with Alternatives

While the chinese remainder theorem is the optimal solution for systems of congruences with coprime moduli, several alternative approaches exist, each with different tradeoffs in complexity, generality, and implementation difficulty. Understanding when to use CRT versus these alternatives is crucial for system design.

Brute force search is the simplest alternative: iterate x from 0 to N-1 and test each candidate against all congruences. It requires no number theory and works for any moduli, coprime or not, but its O(N) time complexity makes it infeasible for all but the smallest problems. For N=105 it is fine; for N=2²⁰⁴⁸ it would require more iterations than atoms in the universe.

Lagrange interpolation is mathematically related to CRT but operates over polynomials rather than integers. Given k points (x_i, y_i), it finds the unique polynomial of degree < k that passes through them. If we view residues as values at specific moduli, the analogy is strong. However, Lagrange interpolation requires O(k²) operations and works over fields, not modular rings, making it suitable for Shamir's Secret Sharing but overkill for simple CRT problems.

Hensel's lemma and lifting techniques are used when moduli are prime powers (e.g., p^e). Instead of treating p^e as a single modulus, we can solve modulo p and then lift the solution to higher powers iteratively. This is more efficient than direct CRT when moduli share prime factors, and is used in p-adic algorithms and polynomial factorization.

For most software engineering tasks involving the chinese remainder theorem, the decision tree is simple: if moduli are guaranteed coprime and you need maximum speed with precomputation, use classic CRT; if moduli are large and numerical stability matters, use Garner; if moduli are arbitrary and you need to handle unsolvable cases gracefully, use generalized CRT; never use brute force except for testing or tiny N.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the chinese remainder theorem. The most frequent mistake is assuming moduli are coprime without verification. If two moduli share a factor, the classic CRT formula will silently produce an incorrect answer or fail with a missing modular inverse error. Always validate pairwise GCDs or use the generalized CRT that checks consistency explicitly. A simple loop checking gcd(n_i, n_j) == 1 for all i < j can prevent hours of debugging.

Another common pitfall is mishandling negative remainders and not normalizing the final result. In Python, the % operator always returns a non-negative result, but in languages like C++ or Java, -1 % 5 yields -1, not 4. If remainders come from user input or prior computations that may be negative, normalize them with a_i % n_i before processing. Similarly, the final CRT result should be reduced modulo N to the canonical range [0, N-1]; forgetting this can cause downstream failures when the result is used as an array index or cryptographic key.

Overflow and performance issues arise when computing N = product(moduli) directly for large k or large moduli. The product can exceed available memory or cause intermediate values to become astronomically large, slowing down multiplication. Garner's algorithm or incremental merging avoids this by never forming the full product until necessary. In languages with fixed-width integers (like 64-bit), overflow is silent and catastrophic; always use arbitrary-precision libraries or check for overflow before multiplication.

Best Practices for Robust Implementations

• Validate inputs early: Check that moduli are positive, remainders are integers, and arrays have equal length before any computation. Raise clear ValueError exceptions with diagnostic messages.
• Use iterative extended GCD: Recursive implementations can hit recursion limits for 2048-bit numbers. The iterative version is equally clear and more robust.
• Precompute for repeated use: If the same moduli are used for many remainder vectors (as in RSA), cache N_i and M_i or Garner coefficients. This transforms O(k log M) per query into O(k) per query.
• Test with known vectors: Use the classic [2,3,2] mod [3,5,7] =23 test, plus edge cases like single congruence, large primes, and intentionally unsolvable systems to verify error handling.
• Prefer generalized CRT for libraries: If writing a reusable function, implement the generalized version that handles non-coprime moduli and reports unsolvability, rather than assuming coprimality.
• Document the modulus product: Always return both x and N (or M = lcm) so callers know the modulus of the solution and can handle the full solution set x + k*N correctly.

Finally, be aware of timing side channels in cryptographic use. A naive CRT implementation that takes different time depending on the remainders can leak information about the private key. Constant-time implementations that always perform the same sequence of operations regardless of input values are required for security-critical code. Use established libraries like Python's pow with built-in CRT or specialized cryptographic libraries rather than rolling your own for production RSA.

10. Interview Questions

Interviewers frequently use the chinese remainder theorem to assess understanding of number theory, algorithm design, and practical problem solving. The questions range from direct implementation to creative applications, and they test both theoretical knowledge and coding ability.

Question 1: Implement CRT for pairwise coprime moduli. This is the most common coding question. The interviewer expects you to write extended_gcd, mod_inverse, and crt_coprime functions from scratch, handling edge cases and explaining the time complexity. A strong answer will discuss why the inverse exists (coprimality), walk through the construction of N_i and M_i, and verify the solution with an example. Bonus points for mentioning Garner's algorithm as an optimization and for testing with the [2,3,2] mod [3,5,7] example. Be prepared to code without libraries and to escape < > correctly if writing HTML.

Question 2: How would you detect if a system of congruences has no solution? This tests knowledge of the generalized CRT. The answer is to check pairwise consistency: for every i, j, we need a_i ≡ a_j (mod gcd(n_i, n_j)). If any pair fails this, the system is unsolvable. For example, x ≡ 1 (mod 4) and x ≡ 2 (mod 6) is unsolvable because gcd(4,6)=2 and 1 ≠ 2 mod 2. An excellent follow-up is to implement crt_general that merges congruences incrementally and raises an error when inconsistency is detected, explaining how the LCM replaces the product as the solution modulus.

Question 3: Explain how RSA uses CRT to speed up decryption and quantify the speedup. This evaluates ability to connect theory to real-world systems. The answer should explain that RSA decryption computes m = c^d mod N where N=p*q, and with CRT we compute m_p = c^{d mod (p-1)} mod p and m_q = c^{d mod (q-1)} mod q separately, then combine. Since modular exponentiation is O(b³) for b-bit numbers, doing two (b/2)-bit exponentiations costs 2*(b/2)³ = b³/4, which is 4x faster than one b-bit exponentiation. Mention that this is why OpenSSL and hardware security modules always use RSA-CRT, and that the speedup is crucial for TLS handshakes handling thousands of connections per second.

Question 4: Given k periodic tasks with periods n_i and offsets a_i, find the next time they all align. This is a disguised CRT problem. For example, a satellite orbits every 3 hours with offset 2, another every 5 hours with offset 3, when do they align? The solution is to model it as x ≡ a_i (mod n_i) and solve via CRT. A strong candidate will recognize the pattern, verify coprimality, apply CRT, and discuss what happens if periods are not coprime (use generalized CRT or report no alignment). They should also discuss the practical interpretation: the solution x is the next alignment time, and subsequent alignments occur every N = lcm(n_i) time units.

Question 5: Compare CRT with brute force and discuss when you would use each. This tests complexity analysis and engineering judgment. The answer should state that brute force is O(N) where N is the product of moduli, while CRT is O(k log M), making CRT exponentially faster for large moduli. Brute force is only suitable for tiny N (e.g., N < 10⁶) or for verification/testing. CRT is superior in all other cases but requires coprime moduli or the generalized version. A nuanced answer will mention that brute force is trivial to implement and has no edge cases, making it useful for quickly validating CRT results in unit tests, but should never be used in production for large inputs.