Combine congruences without losing compatibility

Try

Find an integer that leaves remainder one modulo four and remainder two modulo seven. Trying x=1+4t reduces the second condition to 4t≡1 modulo seven. The inverse of four is two, so t≡2 and x≡9 modulo twenty-eight. The two clocks determine one combined clock when their periods are coprime.

Predict

Predict what changes if the periods share a factor. Conditions x≡0 modulo four and x≡1 modulo six are impossible because the first requires even x and the second odd x. Shared information must agree. When compatible, the combined period is the least common multiple, not automatically the product. This compatibility test prevents treating CRT as an unconditional recipe for arbitrary moduli.

Experiment

Construct selector coefficients for moduli four and seven.

Selector	Modulo 4	Modulo 7
21	1	0
8	0	1

The combination 1·21+2·8=37 reduces to nine modulo twenty-eight. Change the desired residues and reuse the selectors. Each selector behaves like a coordinate basis vector for the pair of residue systems.

Understand

For pairwise coprime positive moduli m₁,…, m_k, let M be their product and Mᵢ=M/mᵢ. Since gcd(Mᵢ, mᵢ)=1, choose uᵢ with uᵢMᵢ≡1 modulo mᵢ. Then x=ΣaᵢuᵢMᵢ realizes the desired residues. At modulus mᵢ its own term remains aᵢ and all other terms vanish. If two solutions exist, their difference is divisible by every mᵢ; coprimality implies divisibility by M. This proves existence and uniqueness modulo M. The correspondence respects addition and multiplication, so it is also a ring decomposition, not merely a counting trick.

Apply

For two arbitrary positive moduli m, n, put d=gcd(m, n). Necessity of d|(a−b) follows from subtracting x−a and x−b. Conversely set x=a+mt and solve mt≡b−a modulo n. The linear-congruence criterion supplies t exactly when d divides the difference. All solution differences are divisible by both m and n, hence by lcm(m, n), and adding that lcm preserves both conditions. This proves the generalized two-modulus theorem. Multiple noncoprime conditions can be combined successively, checking compatibility at each stage rather than assuming pairwise-independent clocks.

The construction also gives an independence interpretation: choosing one residue in each coprime component selects exactly one class modulo the product. There are mn possible pairs and mn classes, but matching counts alone does not prove the map is bijective. Existence comes from the explicit Bézout formula, and uniqueness comes from divisibility by both coprime moduli. For noncoprime m, n, subtracting the two target congruences shows the residues must agree modulo gcd(m, n). When they do, dividing the resulting linear equation by that gcd gives a solution, unique modulo lcm(m, n). This is compatibility, not independent free choice.

Continue

CRT will later turn prime-power congruence solutions into solutions modulo a composite integer and explain why some cryptographic exponent identities hold even on nonunits. Its constructive coefficients can be large, so implementations should reduce intermediate results and protect exactness. Verify both residues independently after construction. A returned representative is only one member of an infinite integer class; any application-specific interval or sign restriction still needs a separate final selection.

Return to the number theory unit to choose a targeted retry. Continue with use permutation of units to control powers.