What is CRT?

The Chinese Remainder Theorem (CRT) says: if you break a big clock into smaller clocks with coprime sizes, no information is lost. The remainders on the small clocks completely determine the position on the big clock. One number becomes a tuple of smaller numbers -- and you can get the original back.

The Simplest Example: N = 15

15 = 3 x 5. Since 3 and 5 share no common factors (they are coprime), every number mod 15 is uniquely determined by its remainders mod 3 and mod 5.

Every pair (r3, r5) with 0 <= r3 < 3 and 0 <= r5 < 5 appears exactly once in the range 0..14. That's 3 x 5 = 15 pairs for 15 numbers. A perfect bijection. No collisions, no gaps.

Why Coprime Matters

Try N = 12 = 4 x 6. Since GCD(4, 6) = 2, they are NOT coprime. Now 0 mod 4 = 0 and 0 mod 6 = 0. But also 12 mod 4 = 0 and 12 mod 6 = 0. Collision! Two different numbers give the same pair of remainders. CRT breaks.

But 12 = 3 x 4 works: GCD(3, 4) = 1 (coprime). Every pair (r3, r4) with 0 <= r3 < 3 and 0 <= r4 < 4 maps to exactly one number mod 12. This is why we factor N into PRIME POWERS, not just any factors.

Reconstruction: From Parts to Whole

CRT is not just decomposition -- it goes both ways. Given remainders, you can RECONSTRUCT the original number. For N = 15 = 3 x 5:

To find n such that n mod 3 = 1 and n mod 5 = 2: find the number that is 1 on the 3-clock and 0 on the 5-clock (that is 10), and the number that is 0 on the 3-clock and 1 on the 5-clock (that is 6). Then n = 1 x 10 + 2 x 6 = 22. Take mod 15: 22 mod 15 = 7. Check: 7 mod 3 = 1, 7 mod 5 = 2.

Scaling Up: More Channels

CRT works for any number of coprime factors. More factors = more channels = finer decomposition:

Each channel computes independently. Addition, multiplication, exponentiation -- all happen per-channel, in parallel. The channels cannot interfere with each other. This is the key insight that makes everything on this site work.

Try It: CRT Machine

Enter any number. See how CRT decomposes it at every level -- from the smallest ring to the full Z/214,414,200.

Enter a number:

CRT is the backbone. Every number is a tuple of independent channel values. Next: see the full 7-channel ring, its classes, and why this specific factorization matters.