Chinese Remainder Theorem Cipher

What is it?

The Chinese Remainder Theorem (CRT) is a cornerstone of number theory. It says: if you know the remainder of a number modulo two different (and coprime) moduli, you can uniquely determine that number modulo their product. The theorem dates back to Sunzi's work in 3rd-century China.

In this cipher, you're given a system of two congruences: x ≡ a (mod m) and x ≡ b (mod n), where m and n are coprime. You find the unique solution x modulo m×n. Then x mod 26 (A=0) gives the secret letter.

Concrete Example

Solve: x ≡ 3 (mod 5) and x ≡ 2 (mod 7).

Step 1: Compute M = m × n = 5 × 7 = 35.

Step 2: Compute the modular inverses.

For modulus 5: M/m = 35/5 = 7. Need 7 × inv ≡ 1 (mod 5).
7 mod 5 = 2. inv of 2 mod 5 = 3 (since 2×3=6≡1).
So inv₁ = 3.

For modulus 7: M/n = 35/7 = 5. Need 5 × inv ≡ 1 (mod 7).
5 mod 7 = 5. inv of 5 mod 7 = 3 (since 5×3=15≡1).
So inv₂ = 3.

Step 3: Combine using the CRT formula:

x = a × (M/m) × inv₁ + b × (M/n) × inv₂ (mod M)
x = 3 × 7 × 3 + 2 × 5 × 3 (mod 35)
x = 63 + 30 (mod 35)
x = 93 (mod 35)
93 mod 35 = 93 - 2×35 = 93 - 70 = 23

Step 4: 23 mod 26 = 23 → X (since A=0, B=1, ..., X=23).

The answer is "x".

Verification: 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓.

Why It Works

The Chinese Remainder Theorem works because the moduli are coprime — they share no common factors. This means the mapping between numbers modulo m×n and pairs of remainders (mod m, mod n) is a bijection: every number in [0, m×n-1] corresponds to exactly one pair of remainders, and vice versa. The formula finds the unique solution by scaling each remainder by the product of the other moduli and its modular inverse, then summing them up.

Solving Tips

• Make sure m and n are coprime (gcd = 1) — the puzzle guarantees this
• Compute M = m × n
• Find the modular inverse of M/m modulo m (for first congruence)
• Find the modular inverse of M/n modulo n (for second congruence)
• Apply: x = a × (M/m) × inv₁ + b × (M/n) × inv₂ (mod M)
• Take x mod 26, map A=0 to find the answer letter

Real-World Applications

• RSA cryptography: The Chinese Remainder Theorem is used to speed up RSA decryption by splitting the computation modulo p and q
• Computer arithmetic: CRT allows representing large integers as tuples of smaller moduli for efficient computation (Residue Number Systems)
• Secret sharing: Asmuth-Bloom secret sharing uses CRT to split a secret into shares that can only be reconstructed with enough parts
• Astronomy: Ancient Chinese astronomers used CRT to predict planetary alignments from remainders of orbital periods
• Calendar systems: The Chinese calendar and the Jewish calendar use CRT-like calculations to synchronize lunar months with solar years