the Chinese remainder theorem

Here is an old puzzle: a number leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7 — what is it? The Chinese remainder theorem says that such a number always exists and is unique once you fix the range, as long as the divisors share no common factors. Intuitively, knowing a number's remainder against several coprime divisors pins it down exactly within one full cycle, the way knowing the day-of-week, day-of-month, and month together identifies a unique date in a year.

Precisely: if m1, m2, ..., mk are pairwise coprime (any two share gcd 1) and M = m1*m2*...*mk, then the system x = a1 mod m1, x = a2 mod m2, ..., x = ak mod mk has exactly one solution x in the range 0..M-1. To construct it for two congruences x = a1 mod m1 and x = a2 mod m2, write Mi for the product of the other moduli: x = a1*M1*(M1^(-1) mod m1) + a2*M2*(M2^(-1) mod m2), all reduced mod M, where each inverse comes from the extended Euclidean algorithm. The construction works because each term is designed to equal ai modulo its own mi and 0 modulo the others, so the sum has the right remainder against every modulus at once. Trace the puzzle with m=3,5,7, M=105: solving gives x = 23, and indeed 23 = 2 mod 3, 23 = 3 mod 5, 23 = 2 mod 7.

CRT matters both as a counting tool and as a computational speedup. It tells you that working modulo a big composite M is equivalent to working independently modulo each coprime factor, which lets algorithms split a hard big-number computation into several small parallel ones and then glue the answers back together. This trick speeds up RSA decryption (compute modulo the two prime factors p and q separately, then recombine), big-integer arithmetic, and many competitive-programming tasks. The one requirement you cannot drop is pairwise coprimality: if two moduli share a factor, the system may have no solution or many, and the clean one-to-one correspondence breaks down.