// NUMBER THEORY · ADVANCED

Chinese Remainder Theorem

Turn many remainder clues into one exact answer. The CRT is the master key behind cryptography and modular problem solving.

Solve a System Play Lock Puzzle
Advanced·25 min·Mathematics · Number Theory
Reviewed by CodeTikki Academic Team

Prerequisites: Modular arithmetic · GCD / Euclidean algorithm · Modular inverses

// VISUALIZER

Brute-force the congruences

Start with the first congruence and add m until the second congruence is satisfied. CRT guarantees a solution when m and n are coprime.

mod
mod

Press PLAY to search for the smallest x that satisfies both congruences.

2
5
8

// MINI GAME

CRT Lock Puzzle

Two congruences, four keys. Pick the correct x before the timer runs out. Correct answers reset the lock with a new challenge.

Loading lock...

// FLOWCHART

Algorithm flow

// FLOWCHART · Chinese Remainder Theorem
Two congruences x ≡ a (mod m), x ≡ b (mod n)
YesNoStartRead a, m, b, nGCD(m, n) = 1?M = m × nM1 = M / mM2 = M / ny1 = M1⁻¹ mod my2 = M2⁻¹ mod nx = a·M1·y1 + b·M2·y2mod MOutput x mod MEnd

Press PLAY to trace the algorithm through the flowchart.

0 / 8

// PSEUDOCODE

Trace the code

// PSEUDOCODE · Chinese Remainder Theorem
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5)
a = 2, m = 3, b = 3, n = 5
1function crt(a, m, b, n):
2 M = m * n
3 M1 = M / m
4 M2 = M / n
5 y1 = modInverse(M1, m)
6 y2 = modInverse(M2, n)
7 x = (a*M1*y1 + b*M2*y2) mod M
8 return x

Press PLAY to step through the algorithm line by line.

0 / 8

// TUTORIAL QUIZZES

Test your mastery

From reading congruences to building the CRT formula and applying it to cryptography.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Lock Smith: Solve a CRT SystemL4The Modular Messenger: CRT with Three CongruencesL6The RSA Accelerator: CRT DecryptionL8The Inverse Hunter: Modular Inverses for CRTL5The Garner Builder: Incremental CRTL9

// REFERENCES

Sources & further reading

  1. [1]
    Sunzi Suanjing — Chinese Remainder TheoremSunzi (3rd–5th century) — earliest known statement
  2. [2]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — Modular arithmetic and number theory
  3. [3]
    A Course in Number Theory and CryptographyNeal Koblitz — CRT and public-key cryptography
  4. [4]
    The Art of Computer Programming, Vol. 2Donald Knuth — Seminumerical Algorithms, modular computation

// READY?

All four number-theory tutorials are live

You now have GCD & Euclidean, Sieve of Eratosthenes, Prime Factorization, and Chinese Remainder Theorem — each with games, quizzes, and full SEO.

Browse All Tutorials Solve Problems