Loading…

hardMath GeometryRarely asked

Chinese Remainder Theorem

Q: How do you solve Chinese Remainder Theorem using the Brute-Force Search (Baseline) approach?

When to use it: Mention first to make 'a solution exists and is unique mod M' concrete — then discard it as O(M). The definition is directly testable: `x` is a solution iff `x mod mᵢ == aᵢ` for every `i`. Brute force tries each candidate `x` in `[0, M)` and returns the first that passes all `k` checks. **Why it is correct.** CRT guarantees exactly one solution in `[0, M)`, so a linear scan over that range is certain to find it. With pairwise-coprime moduli the scan never comes up empty. **Why it doesn't ship.** `M` is the **product** of the moduli, so it grows multiplicatively in `k`. Even three moduli near `10⁹` push `M` past `10²⁷` — there is no scanning that. The brute force is `O(M·k)`, exponential in the input's bit-length. **The structure we ignore.** Scanning treats `x` as a black box. But the congruences are independent in a precise sense: because the moduli are coprime, you can build a number that controls each residue separately and add the pieces. Recognising that 'separate, then recombine' is possible is the leap to the constructive CRT. Time complexity: O(M · k). Space complexity: O(1).

Math & Number Theory · 19 of 36 · 13 min

Given k congruences

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ a_k (mod m_k),

where the moduli m₁, …, m_k are pairwise coprime, find the unique x in [0, M) satisfying all of them, where M = m₁·m₂·…·m_k. The Chinese Remainder Theorem guarantees exactly one such x exists.

In plain English

Each congruence pins down x modulo one modulus. Because the moduli are pairwise coprime, knowing x mod each mᵢ is exactly enough to know x modulo their product M — no more, no less — and there's a single value in [0, M) that matches all the remainders. The construction makes this concrete: build one 'basis' number per congruence that carries the correct remainder for its own modulus and contributes nothing (0) to the others, then add them up. Equivalently, merge congruences two at a time.

Examples

Example 1

Input: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
Output: 23
Note: 23 mod 3 = 2, 23 mod 5 = 3, 23 mod 7 = 2. M = 105, and 23 is the unique solution in [0, 105). (This is the classical Sun Tzu problem.)

Example 2

Input: x ≡ 1 (mod 2), x ≡ 2 (mod 3)
Output: 5
Note: 5 mod 2 = 1, 5 mod 3 = 2. M = 6; the unique solution in [0, 6) is 5.

Example 3

Input: x ≡ 0 (mod 4), x ≡ 1 (mod 6)
Output: no solution
Note: Moduli aren't coprime: gcd(4, 6) = 2. A solution needs (0 − 1) = −1 divisible by 2, which fails — so the system is inconsistent. This is the gcd consistency check the generalised CRT performs.

Constraints

1 ≤ k ≤ 10⁵ congruences
1 ≤ mᵢ, and the mᵢ are pairwise coprime (gcd(mᵢ, mⱼ) = 1 for i ≠ j)
0 ≤ aᵢ < mᵢ
M = ∏ mᵢ can be enormous — use big integers (Python) or mulmod with long / 128-bit intermediates (Java)
Return the unique solution normalised to [0, M)

Clarifying questions4First question: Are the moduli pairwise coprime?Explore questions

Q1.Are the moduli pairwise coprime?
I'll assume so for the classic CRT — that's what guarantees a unique solution mod M and that each Mᵢ is invertible. If they share factors, I'd switch to the generalised merge with a gcd consistency check.
Q2.How big can the product M get?
Potentially huge. In Python I use big integers; in Java I either keep M within 64 bits or use mulmod / 128-bit intermediates to avoid overflow in aᵢ·Mᵢ·yᵢ.
Q3.Do you want every solution or just one?
There's a unique solution in [0, M); all others differ by a multiple of M. I return the canonical one in [0, M).
Q4.What if the system is inconsistent?
With pairwise-coprime moduli it's never inconsistent. For the non-coprime generalisation, two congruences are compatible only if (a₁ − a₂) is divisible by gcd(m₁, m₂); otherwise no solution exists.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You have a system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ a_k (mod m_k) where the moduli are pairwise coprime. CRT says there's a unique solution x modulo M = m₁·m₂·…·m_k, and gives a construction. Let Mᵢ = M / mᵢ. Because mᵢ is coprime to every other modulus, Mᵢ is invertible mod mᵢ; let yᵢ = Mᵢ⁻¹ mod mᵢ (extended Euclid). Then x = (Σ aᵢ · Mᵢ · yᵢ) mod M. The term aᵢ·Mᵢ·yᵢ equals aᵢ mod mᵢ and 0 mod every other modulus, so the sum satisfies all congruences at once.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can state the coprimality precondition, construct the solution from orthogonal basis terms (each aᵢ·Mᵢ·yᵢ correct mod mᵢ and zero elsewhere), and produce the inverses with extended Euclid — plus handle overflow when M is large.

Where candidates slip

Assuming a solution always exists even when moduli aren't coprime, forgetting to reduce into [0, M), or letting aᵢ·Mᵢ·yᵢ overflow because mulmod / big ints weren't used.

How to stand out

Explain the orthogonality — why Mᵢ·yᵢ ≡ 1 (mod mᵢ) and ≡ 0 (mod mⱼ) — and present the iterative pairwise merge as the numerically stable way to combine many congruences, with the gcd consistency check for the non-coprime generalisation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute-Force Search (Baseline)	`O(M · k)`	`O(1)`	Mention first to make 'a solution exists and is unique mod M' concrete — then discard it as O(M).	Read
2	Constructive CRT — Orthogonal Basis / Iterative Merge (Optimal)Optimal	`O(k log M)`	`O(1) beyond inputs`	The answer they want. Lead with 'build one term per congruence that's correct on its own modulus and zero on the others', or present the cleaner pairwise merge.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Orthogonal basis construction

How to read it:Each term aᵢ·Mᵢ·yᵢ equals aᵢ mod mᵢ and 0 mod every other modulus; summing them satisfies all congruences.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute-Force Search (Baseline)

TimeO(M · k)SpaceO(1)

Mention first to make 'a solution exists and is unique mod M' concrete — then discard it as O(M).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

By definition, x satisfies every congruence. What's the most direct way to find such an x without any number theory?

2Hint 2Explore hint

Try every candidate x from 0 up to M − 1 and check x mod mᵢ == aᵢ for all i. The first that passes is the unique answer.

3Hint 3Explore hint

That's O(M · k). M is the product of all moduli, so it explodes — for moduli like 1e9 each, M is astronomically large. What structure lets us construct x directly?

A · Core idea

The definition is directly testable: x is a solution iff x mod mᵢ == aᵢ for every i. Brute force tries each candidate x in [0, M) and returns the first that passes all k checks.

Why it is correct. CRT guarantees exactly one solution in [0, M), so a linear scan over that range is certain to find it. With pairwise-coprime moduli the scan never comes up empty.

Why it doesn't ship. M is the product of the moduli, so it grows multiplicatively in k. Even three moduli near 10⁹ push M past 10²⁷ — there is no scanning that. The brute force is O(M·k), exponential in the input's bit-length.

The structure we ignore. Scanning treats x as a black box. But the congruences are independent in a precise sense: because the moduli are coprime, you can build a number that controls each residue separately and add the pieces. Recognising that 'separate, then recombine' is possible is the leap to the constructive CRT.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

x=2

2 mod 3 = 2 ✓, 2 mod 5 = 2 ✗

Statefail

Final result23

C · Code with teaching comments

Reference implementation previewpublic long crtBruteForce(long[] a, long[] m) { long M = 1; for (long mi : m) M *= mi; // assumes M fits in long for the demo for (long x = 0; x < M; x++) { boolean ok = true;Explore the full code

solution.javaJava

Brute-Force Search (Baseline) — reference

2 teaching notes

1
public long crtBruteForce(long[] a, long[] m) {
2
    long M = 1;
3
    for (long mi : m) M *= mi; // assumes M fits in long for the demo
4
    for (long x = 0; x < M; x++) {
5
        boolean ok = true;
6
        for (int i = 0; i < m.length; i++) {
7
            // Direct definition test; one failure rejects this candidate.
8
            if (x % m[i] != a[i]) { ok = false; break; }
9
        }
10
        if (ok) return x;
11
    }
12
    return -1; // unreachable for valid coprime input
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(M · k) timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force is only a definition check — useful to verify a constructed answer on tiny inputs, never to compute it. The whole point of CRT is that you never need to search: the solution can be assembled directly from the residues.

ComplexityO(M · k) time, O(1) space — Scanning x from 0 to M − 1 and testing k congruences each is O(M·k). Since M is the product of the moduli, it grows multiplicatively and is hopeless beyond tiny inputs; space is O(1).

E · Edge cases and pitfalls3Running it when M is large — multiplicative blowup makes it infeasible.Explore edge cases

Pitfalls

Running it when M is large — multiplicative blowup makes it infeasible.
Assuming M fits in a 64-bit integer for the loop bound — it rarely does.
Treating it as a real algorithm rather than a correctness check on tiny inputs.

03.2

Approach 2 of 2 · Optimal

Constructive CRT — Orthogonal Basis / Iterative Merge (Optimal)

TimeO(k log M)SpaceO(1) beyond inputs

The answer they want. Lead with 'build one term per congruence that's correct on its own modulus and zero on the others', or present the cleaner pairwise merge.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you could build, for each i, a number that equals aᵢ when reduced mod mᵢ but equals 0 mod every other modulus. What happens when you add all k of them?

2Hint 2Explore hint

Let M = ∏ mⱼ and Mᵢ = M / mᵢ. Mᵢ is divisible by every mⱼ (j ≠ i), so it's 0 mod those. To make it ≡ 1 mod mᵢ, multiply by yᵢ = Mᵢ⁻¹ mod mᵢ (extended Euclid). Then aᵢ·Mᵢ·yᵢ is your basis term.

3Hint 3Explore hint

Sum the terms and reduce mod M. Equivalently, merge two congruences at a time: combine (a₁, m₁) and (a₂, m₂) into one congruence mod m₁·m₂, then fold in the next — this keeps the numbers smaller.

A · Core idea

Construct the solution directly instead of searching. Two equivalent framings; both rest on the same orthogonality idea.

The orthogonal-basis construction. Set M = m₁·m₂·…·m_k and, for each i, Mᵢ = M / mᵢ. The number Mᵢ is a product of every modulus except mᵢ, so Mᵢ ≡ 0 (mod mⱼ) for all j ≠ i. By itself Mᵢ is not ≡ 1 (mod mᵢ), but since mᵢ is coprime to every factor of Mᵢ, Mᵢ is invertible mod mᵢ. Let yᵢ = Mᵢ⁻¹ (mod mᵢ), computed with the extended Euclidean algorithm. Now the basis term eᵢ = Mᵢ·yᵢ satisfies eᵢ ≡ 1 (mod mᵢ) and eᵢ ≡ 0 (mod mⱼ) for j ≠ i — it is an 'indicator' for modulus i. Therefore x = Σ aᵢ·eᵢ (mod M) reduces, modulo any particular mⱼ, to just aⱼ·1 + (other terms)·0 = aⱼ — every congruence is satisfied at once.

Why coprimality is essential. Two things hinge on it. First, Mᵢ is invertible mod mᵢ only because mᵢ shares no factor with the other moduli; without that, yᵢ doesn't exist. Second, coprimality is what makes the solution unique mod M: if x and x' both solve the system then mᵢ | (x − x') for all i, and pairwise-coprime moduli give M | (x − x'). Drop coprimality and you either lose existence or lose uniqueness.

The iterative pairwise merge (numerically cleaner). Instead of forming the giant M up front, merge two congruences into one and repeat. Given x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂), write x = a₁ + m₁·t. Substituting into the second congruence: a₁ + m₁·t ≡ a₂ (mod m₂), so t ≡ (a₂ − a₁)·(m₁⁻¹) (mod m₂). Then the merged congruence is x ≡ a₁ + m₁·t (mod m₁·m₂). Fold congruences in one at a time; the running modulus is the product so far, which keeps intermediates as small as possible and makes the gcd consistency check easy to insert for the non-coprime case (a solution exists only if (a₂ − a₁) is divisible by gcd(m₁, m₂)).

Why normalise. The summed/merged value can land outside [0, M) (especially with negative inverses), so finish with ((x % M) + M) % M to return the canonical representative.

Why overflow demands care. M, Mᵢ, and aᵢ·Mᵢ·yᵢ blow past 64 bits quickly. In Java, multiply with a mulmod (e.g. via Math.multiplyHigh / 128-bit logic or BigInteger) and reduce after each step; divide M / mᵢ exactly before multiplying back to limit growth. Python integers are unbounded, so the arithmetic is exact with no overflow, and the modulus is for keeping the final answer canonical.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Array state

start

x=0, mod=1

fold ↓

x=0

[0]

mod=1

[1]

Current pointerResolved stateNot processed

Final result23

C · Code with teaching comments

solution.javaJava

Constructive CRT — Orthogonal Basis / Iterative Merge (Optimal) — optimal

6 teaching notes

1
import java.math.BigInteger;
2
import java.util.*;
3
 
4
public BigInteger crt(long[] a, long[] m) {
5
    // Iterative pairwise merge; BigInteger avoids overflow in the product.
6
    BigInteger x = BigInteger.ZERO;
7
    BigInteger mod = BigInteger.ONE;       // running modulus = product so far
8
    for (int i = 0; i < a.length; i++) {
9
        BigInteger ai = BigInteger.valueOf(a[i]);
10
        BigInteger mi = BigInteger.valueOf(m[i]);
11
        // solve x + mod*t == ai (mod mi):  t = (ai - x) * inv(mod, mi) mod mi
12
        // How far the current solution is from aᵢ, reduced mod mᵢ.
13
        BigInteger diff = ai.subtract(x).mod(mi);
14
        BigInteger inv = mod.modInverse(mi); // requires gcd(mod, mi) == 1
15
        BigInteger t = diff.multiply(inv).mod(mi);
16
        // Adjust x by a multiple of the running modulus so it now satisfies the new
17
        // congruence too.
18
        x = x.add(mod.multiply(t));
19
        mod = mod.multiply(mi);              // new modulus = product
20
        x = x.mod(mod);
21
    }
22
    return x.mod(mod); // canonical representative in [0, M)
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(k log M) timeO(1) beyond inputs spaceOpen the invariant and proofExplore the proof

CRT is the 'partition of unity' for modular arithmetic: build indicator numbers that are 1 on their own modulus and 0 on the rest, then any target residues are reachable by a weighted sum. The pairwise merge is the same theorem expressed as a fold — preferable in code because it keeps intermediates small and slots in the gcd check needed when moduli aren't coprime.

ComplexityO(k log M) time, O(1) beyond inputs space — Either form does O(k) modular inverses (extended Euclid, O(log m) each) plus O(k) multiplications, so O(k log M). Space is O(1) beyond storing the inputs. The iterative merge keeps intermediate values bounded by the running product.

E · Edge cases and pitfalls9single congruence x ≡ a (mod m) — Merge runs once; returns a mod m.Explore edge cases

Edge cases handled

single congruence x ≡ a (mod m)Merge runs once; returns a mod m.
all aᵢ = 0x = 0 satisfies every congruence; returns 0.
moduli not coprime, consistentGeneralised merge succeeds only if (a₂−a₁) divisible by gcd; modulus becomes lcm, not product.
moduli not coprime, inconsistentgcd check fails → report no solution.

Pitfalls

Assuming a solution exists when moduli aren't coprime — add the gcd consistency check.
Forgetting to normalise into [0, M) — negative inverses leak a negative answer.
Letting M or aᵢ·Mᵢ·yᵢ overflow in Java — use BigInteger or mulmod, reduce per step.
Computing M then Mᵢ = M / mᵢ with integer overflow before the division — prefer the iterative merge.
Inverting Mᵢ mod mⱼ (wrong modulus) — the inverse must be taken mod mᵢ.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.math.BigInteger; import java.util.*; public BigInteger crt(long[] a, long[] m) { // Iterative pairwise merge; BigInteger avoids overflow in the product.Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Ignoring the coprimality precondition

Classic CRT needs pairwise-coprime moduli. With shared factors, Mᵢ may not be invertible mod mᵢ, and the system can be inconsistent. The generalised merge needs (a₂ − a₁) divisible by gcd(m₁, m₂).

Explore the code comparison

Don't write this

inv = pow(mod, -1, mi)   # throws if gcd(mod, mi) != 1, or silently wrong assumptions

Write this instead

g = math.gcd(mod, mi)
if (ai - x) % g != 0:
    return None              # inconsistent system
# ... generalised merge using lcm and inverse of (mod // g) ...

Not normalising the result

Basis terms or merge updates can produce a value outside [0, M) (negative inverses, large sums). Returning it raw gives a non-canonical or negative answer.

Explore the code comparison

Don't write this

return x;                 // may be negative or >= M

Write this instead

return x.mod(mod);        // canonical representative in [0, M)

Overflow in the product and basis terms

M = ∏ mᵢ and aᵢ·Mᵢ·yᵢ blow past 64 bits fast. Plain long multiplication overflows to garbage; use BigInteger (Java) or big ints (Python), or a mulmod.

Explore the code comparison

Don't write this

long M = 1;
for (long mi : m) M *= mi;          // overflows long for several moduli
long term = a[i] * (M / m[i]) * y[i]; // overflows again

Write this instead

BigInteger M = BigInteger.ONE;
for (long mi : m) M = M.multiply(BigInteger.valueOf(mi));
// terms via BigInteger.multiply, reduced mod M

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Build the solution as a sum of basis terms, each correct for one modulus and zero on the rest

Code pattern to memorize

M = product of all m_i
for each i:  M_i = M / m_i
             y_i = modInverse(M_i mod m_i, m_i)   # extended Euclid
x = (sum of a_i * M_i * y_i) mod M
# pairwise iterative merge of (a1,m1),(a2,m2):
#   x = a1 + m1 * ((a2 - a1) * inv(m1 mod m2, m2) mod m2)

Rules to remember

1The moduli must be pairwise coprime for the classic CRT. If they aren't, the system may have no solution, or you need the generalised merge with a consistency check (a₁ − a₂) divisible by gcd(m₁, m₂).
2Each basis term aᵢ·Mᵢ·yᵢ is designed to be ≡ aᵢ (mod mᵢ) and ≡ 0 (mod mⱼ) for j ≠ i — that orthogonality is why the sum works.
3Mᵢ = M / mᵢ is invertible mod mᵢ because it's a product of moduli all coprime to mᵢ; get the inverse from extended Euclid.
4The product M and intermediate terms aᵢ·Mᵢ·yᵢ overflow fast — multiply with (__int128-style) long care using mulmod, or use Python big ints. Divide-before-multiply where possible.
5Normalise the answer into [0, M) with ((x % M) + M) % M; the construction can produce a value outside that range before reduction.

Use this pattern when

Solve a **system of congruences** with pairwise-coprime moduli
Reconstruct a big result from its residues modulo several small primes (CRT after computing mod p₁, p₂, …)
Speed up big-integer arithmetic by working in independent modular channels, then recombining
Counting / scheduling problems that reduce to 'x leaves remainder aᵢ when divided by mᵢ'

Choose another pattern when

A single congruence → just reduce; CRT is for systems
Moduli share factors and you only want the classic theorem → either no solution or you need the generalised CRT with a gcd check
You need a modular inverse, not a system → extended Euclid alone
The combined modulus M is required but overflows and you don't reduce per-channel → rethink representation

Interview takeaway

CRT turns a system of remainders into one congruence modulo the product. The construction is 'sum of orthogonal basis terms': each term hits its own modulus and vanishes on the others, so adding them satisfies everything simultaneously. The two pillars are pairwise-coprimality (guarantees uniqueness mod M and that each Mᵢ is invertible) and the modular inverse from extended Euclid. Iterating the two-congruence merge is the cleaner way to combine many at once and to keep numbers small.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternChinese Remainder Theorem — solve a system of congruences with coprime moduli. Recognise it whenever a quantity is known only by its remainders modulo several coprime numbers, or when you split a hard modular computation into independent prime-power channels and recombine. The orthogonal-basis sum and the iterative pairwise merge are two views of the same constructive proof.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Catalan Numbers

Continue · Next problem

Collatz Sequence Length

hardMath GeometryRarely asked

Chinese Remainder Theorem

Math & Number Theory · 19 of 36 · 13 min

Given k congruences

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ a_k (mod m_k),

In plain English

Examples

Example 1

Input: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
Output: 23
Note: 23 mod 3 = 2, 23 mod 5 = 3, 23 mod 7 = 2. M = 105, and 23 is the unique solution in [0, 105). (This is the classical Sun Tzu problem.)

Example 2

Input: x ≡ 1 (mod 2), x ≡ 2 (mod 3)
Output: 5
Note: 5 mod 2 = 1, 5 mod 3 = 2. M = 6; the unique solution in [0, 6) is 5.

Example 3

Input: x ≡ 0 (mod 4), x ≡ 1 (mod 6)
Output: no solution
Note: Moduli aren't coprime: gcd(4, 6) = 2. A solution needs (0 − 1) = −1 divisible by 2, which fails — so the system is inconsistent. This is the gcd consistency check the generalised CRT performs.

Constraints

1 ≤ k ≤ 10⁵ congruences
1 ≤ mᵢ, and the mᵢ are pairwise coprime (gcd(mᵢ, mⱼ) = 1 for i ≠ j)
0 ≤ aᵢ < mᵢ
M = ∏ mᵢ can be enormous — use big integers (Python) or mulmod with long / 128-bit intermediates (Java)
Return the unique solution normalised to [0, M)

Clarifying questions4First question: Are the moduli pairwise coprime?Explore questions

Q1.Are the moduli pairwise coprime?
I'll assume so for the classic CRT — that's what guarantees a unique solution mod M and that each Mᵢ is invertible. If they share factors, I'd switch to the generalised merge with a gcd consistency check.
Q2.How big can the product M get?
Potentially huge. In Python I use big integers; in Java I either keep M within 64 bits or use mulmod / 128-bit intermediates to avoid overflow in aᵢ·Mᵢ·yᵢ.
Q3.Do you want every solution or just one?
There's a unique solution in [0, M); all others differ by a multiple of M. I return the canonical one in [0, M).
Q4.What if the system is inconsistent?
With pairwise-coprime moduli it's never inconsistent. For the non-coprime generalisation, two congruences are compatible only if (a₁ − a₂) is divisible by gcd(m₁, m₂); otherwise no solution exists.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Assuming a solution always exists even when moduli aren't coprime, forgetting to reduce into [0, M), or letting aᵢ·Mᵢ·yᵢ overflow because mulmod / big ints weren't used.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute-Force Search (Baseline)	`O(M · k)`	`O(1)`	Mention first to make 'a solution exists and is unique mod M' concrete — then discard it as O(M).	Read
2	Constructive CRT — Orthogonal Basis / Iterative Merge (Optimal)Optimal	`O(k log M)`	`O(1) beyond inputs`	The answer they want. Lead with 'build one term per congruence that's correct on its own modulus and zero on the others', or present the cleaner pairwise merge.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Orthogonal basis construction

How to read it:Each term aᵢ·Mᵢ·yᵢ equals aᵢ mod mᵢ and 0 mod every other modulus; summing them satisfies all congruences.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute-Force Search (Baseline)

TimeO(M · k)SpaceO(1)

Mention first to make 'a solution exists and is unique mod M' concrete — then discard it as O(M).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

By definition, x satisfies every congruence. What's the most direct way to find such an x without any number theory?

2Hint 2Explore hint

Try every candidate x from 0 up to M − 1 and check x mod mᵢ == aᵢ for all i. The first that passes is the unique answer.

3Hint 3Explore hint

That's O(M · k). M is the product of all moduli, so it explodes — for moduli like 1e9 each, M is astronomically large. What structure lets us construct x directly?

A · Core idea

The definition is directly testable: x is a solution iff x mod mᵢ == aᵢ for every i. Brute force tries each candidate x in [0, M) and returns the first that passes all k checks.

Why it is correct. CRT guarantees exactly one solution in [0, M), so a linear scan over that range is certain to find it. With pairwise-coprime moduli the scan never comes up empty.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

x=2

2 mod 3 = 2 ✓, 2 mod 5 = 2 ✗

Statefail

Final result23

C · Code with teaching comments

solution.javaJava

Brute-Force Search (Baseline) — reference

2 teaching notes

1
public long crtBruteForce(long[] a, long[] m) {
2
    long M = 1;
3
    for (long mi : m) M *= mi; // assumes M fits in long for the demo
4
    for (long x = 0; x < M; x++) {
5
        boolean ok = true;
6
        for (int i = 0; i < m.length; i++) {
7
            // Direct definition test; one failure rejects this candidate.
8
            if (x % m[i] != a[i]) { ok = false; break; }
9
        }
10
        if (ok) return x;
11
    }
12
    return -1; // unreachable for valid coprime input
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(M · k) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Running it when M is large — multiplicative blowup makes it infeasible.Explore edge cases

Pitfalls

Running it when M is large — multiplicative blowup makes it infeasible.
Assuming M fits in a 64-bit integer for the loop bound — it rarely does.
Treating it as a real algorithm rather than a correctness check on tiny inputs.

03.2

Approach 2 of 2 · Optimal

Constructive CRT — Orthogonal Basis / Iterative Merge (Optimal)

TimeO(k log M)SpaceO(1) beyond inputs

The answer they want. Lead with 'build one term per congruence that's correct on its own modulus and zero on the others', or present the cleaner pairwise merge.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you could build, for each i, a number that equals aᵢ when reduced mod mᵢ but equals 0 mod every other modulus. What happens when you add all k of them?

2Hint 2Explore hint

3Hint 3Explore hint

A · Core idea

Construct the solution directly instead of searching. Two equivalent framings; both rest on the same orthogonality idea.

Why normalise. The summed/merged value can land outside [0, M) (especially with negative inverses), so finish with ((x % M) + M) % M to return the canonical representative.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Array state

start

x=0, mod=1

fold ↓

x=0

[0]

mod=1

[1]

Current pointerResolved stateNot processed

Final result23

C · Code with teaching comments

solution.javaJava

Constructive CRT — Orthogonal Basis / Iterative Merge (Optimal) — optimal

6 teaching notes

1
import java.math.BigInteger;
2
import java.util.*;
3
 
4
public BigInteger crt(long[] a, long[] m) {
5
    // Iterative pairwise merge; BigInteger avoids overflow in the product.
6
    BigInteger x = BigInteger.ZERO;
7
    BigInteger mod = BigInteger.ONE;       // running modulus = product so far
8
    for (int i = 0; i < a.length; i++) {
9
        BigInteger ai = BigInteger.valueOf(a[i]);
10
        BigInteger mi = BigInteger.valueOf(m[i]);
11
        // solve x + mod*t == ai (mod mi):  t = (ai - x) * inv(mod, mi) mod mi
12
        // How far the current solution is from aᵢ, reduced mod mᵢ.
13
        BigInteger diff = ai.subtract(x).mod(mi);
14
        BigInteger inv = mod.modInverse(mi); // requires gcd(mod, mi) == 1
15
        BigInteger t = diff.multiply(inv).mod(mi);
16
        // Adjust x by a multiple of the running modulus so it now satisfies the new
17
        // congruence too.
18
        x = x.add(mod.multiply(t));
19
        mod = mod.multiply(mi);              // new modulus = product
20
        x = x.mod(mod);
21
    }
22
    return x.mod(mod); // canonical representative in [0, M)
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(k log M) timeO(1) beyond inputs spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls9single congruence x ≡ a (mod m) — Merge runs once; returns a mod m.Explore edge cases

Edge cases handled

single congruence x ≡ a (mod m)Merge runs once; returns a mod m.
all aᵢ = 0x = 0 satisfies every congruence; returns 0.
moduli not coprime, consistentGeneralised merge succeeds only if (a₂−a₁) divisible by gcd; modulus becomes lcm, not product.
moduli not coprime, inconsistentgcd check fails → report no solution.

Pitfalls

Assuming a solution exists when moduli aren't coprime — add the gcd consistency check.
Forgetting to normalise into [0, M) — negative inverses leak a negative answer.
Letting M or aᵢ·Mᵢ·yᵢ overflow in Java — use BigInteger or mulmod, reduce per step.
Computing M then Mᵢ = M / mᵢ with integer overflow before the division — prefer the iterative merge.
Inverting Mᵢ mod mⱼ (wrong modulus) — the inverse must be taken mod mᵢ.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Ignoring the coprimality precondition

Explore the code comparison

Don't write this

inv = pow(mod, -1, mi)   # throws if gcd(mod, mi) != 1, or silently wrong assumptions

Write this instead

g = math.gcd(mod, mi)
if (ai - x) % g != 0:
    return None              # inconsistent system
# ... generalised merge using lcm and inverse of (mod // g) ...

Not normalising the result

Basis terms or merge updates can produce a value outside [0, M) (negative inverses, large sums). Returning it raw gives a non-canonical or negative answer.

Explore the code comparison

Don't write this

return x;                 // may be negative or >= M

Write this instead

return x.mod(mod);        // canonical representative in [0, M)

Overflow in the product and basis terms

M = ∏ mᵢ and aᵢ·Mᵢ·yᵢ blow past 64 bits fast. Plain long multiplication overflows to garbage; use BigInteger (Java) or big ints (Python), or a mulmod.

Explore the code comparison

Don't write this

long M = 1;
for (long mi : m) M *= mi;          // overflows long for several moduli
long term = a[i] * (M / m[i]) * y[i]; // overflows again

Write this instead

BigInteger M = BigInteger.ONE;
for (long mi : m) M = M.multiply(BigInteger.valueOf(mi));
// terms via BigInteger.multiply, reduced mod M

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Build the solution as a sum of basis terms, each correct for one modulus and zero on the rest

Code pattern to memorize

M = product of all m_i
for each i:  M_i = M / m_i
             y_i = modInverse(M_i mod m_i, m_i)   # extended Euclid
x = (sum of a_i * M_i * y_i) mod M
# pairwise iterative merge of (a1,m1),(a2,m2):
#   x = a1 + m1 * ((a2 - a1) * inv(m1 mod m2, m2) mod m2)

Rules to remember

1The moduli must be pairwise coprime for the classic CRT. If they aren't, the system may have no solution, or you need the generalised merge with a consistency check (a₁ − a₂) divisible by gcd(m₁, m₂).
2Each basis term aᵢ·Mᵢ·yᵢ is designed to be ≡ aᵢ (mod mᵢ) and ≡ 0 (mod mⱼ) for j ≠ i — that orthogonality is why the sum works.
3Mᵢ = M / mᵢ is invertible mod mᵢ because it's a product of moduli all coprime to mᵢ; get the inverse from extended Euclid.
4The product M and intermediate terms aᵢ·Mᵢ·yᵢ overflow fast — multiply with (__int128-style) long care using mulmod, or use Python big ints. Divide-before-multiply where possible.
5Normalise the answer into [0, M) with ((x % M) + M) % M; the construction can produce a value outside that range before reduction.

Use this pattern when

Solve a **system of congruences** with pairwise-coprime moduli
Reconstruct a big result from its residues modulo several small primes (CRT after computing mod p₁, p₂, …)
Speed up big-integer arithmetic by working in independent modular channels, then recombining
Counting / scheduling problems that reduce to 'x leaves remainder aᵢ when divided by mᵢ'

Choose another pattern when

A single congruence → just reduce; CRT is for systems
Moduli share factors and you only want the classic theorem → either no solution or you need the generalised CRT with a gcd check
You need a modular inverse, not a system → extended Euclid alone
The combined modulus M is required but overflows and you don't reduce per-channel → rethink representation

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Catalan Numbers

Continue · Next problem

Collatz Sequence Length