Chinese Remainder Theorem

Chinese Remainder Theorem

Mathematical Definition

Let m and n be positive integers and a and b be integer representatives. We want an integer x satisfying both conditions:

A solution exists exactly when g divides b−a. If it exists, there is one solution x₀ in the range 0 ≤ x₀ < L. Every integer solution is x₀ + kL, where k is any integer. This generalized two-modulus statement is proved in Bruce Ikenaga’s Millersville lecture.

When gcd(m,n)=1, compatibility is automatic because 1 divides every integer. Then L=mn, giving the ordinary coprime theorem. “Unique” describes a residue class, not a single integer without qualification: 8, 23 and −7 all satisfy x≡2 modulo 3 and x≡3 modulo 5.

Key Concepts

Why the shared factor decides compatibility

If x satisfies the first condition, x−a is a multiple of m and therefore of g. Similarly x−b is a multiple of g. Subtracting shows that b−a must also be a multiple of g. For instance, a remainder 1 modulo 4 requires an odd integer. A remainder 2 modulo 6 requires an even integer. No integer can meet both conditions.

Constructing the solution

First normalize a and b to nonnegative remainders. Write x=a+mt so the first condition is already satisfied. The second condition asks for mt≡b−a modulo n. If compatibility holds, divide the coefficient, difference and modulus by g:

The reduced moduli m′ and n′ are coprime, so m′ has a multiplicative inverse modulo n′ when n′ is greater than 1. An inverse u satisfies m′u≡1 modulo n′. For larger moduli, the extended Euclidean algorithm can find u efficiently. Stanford’s number-theory notes give a complementary construction using modular inverses.

If n′=1, no extra restriction remains on t. Choose t=0 without computing an inverse. This happens when n divides m and the remainders are compatible, including equal moduli. Modulus 1 is valid: every integer has remainder zero modulo 1.

Worked example: two coprime patterns

For x≡2 modulo 3 and x≡3 modulo 5, set x=2+3t. Then 3t≡1 modulo 5. Since 3×2=6 leaves remainder 1, the inverse of 3 is 2. Choose t=2 and obtain x=2+3×2=8. Direct division checks 8=2×3+2 and 8=1×5+3. The period is 15, so the next solutions are 23 and 38; the preceding one is −7.

Worked example: shared factors can still agree

For x≡1 modulo 4 and x≡3 modulo 6, the gcd is 2 and the remainder difference is 2. Dividing 4t≡2 modulo 6 by 2 gives 2t≡1 modulo 3. The inverse of 2 is 2, so t=2 and x=1+4×2=9. Both 9 and 21 satisfy the conditions. The period is 12, not 24: using the product would hide the smaller repeating pattern.

Change the second remainder from 3 to 2. The difference becomes 1, which is not divisible by 2. The green intersection disappears; this is a valid input with no mathematical solution, rather than an input-format error.

Equal and dividing moduli

Two conditions modulo 5 with remainder 2 are the same condition: x≡2 modulo 5. Remainders 2 and 3 modulo that same modulus conflict. Likewise, x≡4 modulo 6 already implies x≡1 modulo 3. The combined answer is 4 modulo 6; it needs no inverse modulo 1. Reversing the order of the conditions changes the construction steps but preserves the answer.

Why the period is the least common multiple

If x and y both solve the system, their difference is divisible by m and by n, hence by lcm(m,n). Conversely, adding any multiple of that lcm preserves both remainders. Thus exactly one representative appears in a full period when the conditions are compatible, and none appears when they conflict. The grid displays that complete period, so the count is observable.

Signed representatives and experiment boundaries

Negative representatives are normalized using the Euclidean remainder in 0..m−1. For example, −1 modulo 5 becomes 4. Combining that condition with remainder 3 modulo 7 gives x=24 modulo 35: 24 leaves remainders 4 and 3. A negative probe uses the same normalization; −7 leaves remainders 2 modulo 3 and 3 modulo 5.

The experiment accepts moduli 1..12 and representatives −100..100. Its largest possible period is 132, allowing every integer in one period to be inspected. Empty, fractional, nonnumeric or out-of-range inputs show an explicit error and remove the earlier calculation. The probe ranges from −150 to 300; clicking a grid cell or “Inspect solution” updates its remainder checks. Reset restores the default coprime example.

Historical Context

Modern number theory expresses the Chinese Remainder Theorem through congruences and residue classes. NIST places it among applications of number theory, while the Stanford notes connect the same correspondence to computation with composite moduli. Those presentations emphasize two enduring ideas: separate a calculation into smaller modular pieces, then reconstruct the combined class.

Real-world Applications

• Repeating schedules: conditions such as “two steps after every third tick” and “three steps after every fifth tick” meet at 8, then recur every 15 ticks. Shared factors can make a proposed schedule impossible.
• Residue arithmetic: for coprime moduli, an integer class modulo their product corresponds to one remainder for each modulus. Addition and multiplication can be performed in those smaller systems and reconstructed afterward.
• Cryptographic computation: CRT can accelerate operations such as RSA signing and decryption by using computations modulo the prime factors before recombination. The Stanford notes explain this application.

Related Concepts

• RSA Encryption — modular exponentiation and key generation; CRT addresses how smaller modular results can be combined.
• Shamir Secret Sharing — modular inverses support interpolation within one prime field, a different reconstruction problem.
• Prime Number Patterns — prime distribution and an Ulam spiral, rather than simultaneous congruences.