Three Remainders, One Number: The Chinese Remainder Theorem

Introduction

Around the 3rd to 5th century, a Chinese text known as Sunzi Suanjing posed a riddle: there is a number whose remainder is 2 when divided by 3, 3 when divided by 5, and 2 when divided by 7. What is the number?

You could guess and check forever. But the Chinese Remainder Theorem (CRT) promises something remarkable: as long as the divisors share no common factor — 3, 5 and 7 are pairwise coprime — there is exactly one answer between 0 and 3 × 5 × 7 = 105. The remainders are like coordinates, and together they name a single point.

This is not a conjecture or an open problem. It is a theorem, proven for centuries, with a clean, fast algorithm to rebuild the number. The surprise is how useful that turns out to be: the same trick quietly speeds up the RSA cryptography protecting your messages.

Assemble the Number

Choose any remainders you like — a value mod 3, a value mod 5, and a value mod 7. The theorem guarantees there is precisely one whole number from 0 to 104 that matches all three at once. Press Assemble and watch it get built.

<p class="hint">Pick a remainder for each base. The Chinese Remainder Theorem guarantees there is <b>exactly one</b> number from 0 to 104 that leaves all three remainders at once. Press <b>Assemble</b> to rebuild it.</p>
<div class="picks">
  <label>mod 3 <select id="r3"><option>0</option><option selected>2</option><option>1</option></select></label>
  <label>mod 5 <select id="r5"><option>0</option><option>1</option><option>2</option><option selected>3</option><option>4</option></select></label>
  <label>mod 7 <select id="r7"><option>0</option><option>1</option><option selected>2</option><option>3</option><option>4</option><option>5</option><option>6</option></select></label>
</div>
<div class="btns">
  <button id="go" type="button">Assemble</button>
  <button id="verify" type="button" class="ghost">Verify by scanning</button>
</div>
<div class="answer" id="answer">x ≡ 2 (mod 3),  3 (mod 5),  2 (mod 7)</div>
<div class="work" id="work"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.picks { display: flex; gap: 1rem; flex-wrap: wrap; margin: .2rem 0 .8rem; }
label { font: 600 14px system-ui, sans-serif; color: #1d3557; display: flex; align-items: center; gap: .4rem; }
select { font: 600 14px system-ui, sans-serif; padding: .3rem .4rem; border: 1px solid #cdd9e3; border-radius: 6px; background: #fff; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.answer { font: 700 22px ui-monospace, monospace; color: #0a7d33; min-height: 1.4em; margin: .3rem 0; }
.work { font: 500 13px ui-monospace, monospace; color: #41506a; line-height: 1.7; white-space: pre-wrap;
        background: #f2f6f9; border: 1px solid #dde6ee; border-radius: 8px; padding: .6rem .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chinese Remainder Theorem for the pairwise-coprime bases 3, 5, 7 (product M = 105).
// For each base m_i we precompute a "basis number" e_i with:
//   e_i ≡ 1 (mod m_i)  and  e_i ≡ 0 (mod every other base).
// Then the unique solution is x = (r3*e3 + r5*e5 + r7*e7) mod 105.
const MS = [3, 5, 7], M = 105;

// Extended Euclid -> modular inverse of a mod m.
function inv(a, m){
  let [old_r, r] = [((a % m) + m) % m, m];
  let [old_s, s] = [1, 0];
  while (r !== 0){ const q = Math.floor(old_r / r);
    [old_r, r] = [r, old_r - q * r]; [old_s, s] = [s, old_s - q * s]; }
  return ((old_s % m) + m) % m;
}
// Basis number for base index i: Mi = M/mi, then ei = Mi * inv(Mi mod mi, mi).
function basis(i){ const mi = MS[i], Mi = M / mi; return (Mi * inv(Mi % mi, mi)) % M; }
const E = MS.map((_, i) => basis(i));

function readPicks(){
  return [ +document.getElementById('r3').value,
           +document.getElementById('r5').value,
           +document.getElementById('r7').value ];
}
function assemble(){
  const r = readPicks();
  let x = 0; const parts = [];
  for (let i = 0; i < 3; i++){ x = (x + r[i] * E[i]) % M;
    parts.push(r[i] + '·' + E[i]); }
  document.getElementById('answer').textContent = 'x = ' + x;
  document.getElementById('work').textContent =
    fmt(`Basis numbers (each ≡1 at its base, ≡0 at the others):
  e(mod3)=%v%,  e(mod5)=%v2%,  e(mod7)=%v3%
x = (%parts%) mod 105
x = %x%   →   %x% mod 3 = %v4%,  %x% mod 5 = %v5%,  %x% mod 7 = %v6%`, { v: E[0], v2: E[1], v3: E[2], parts: parts.join(' + '), x: x, v4: x % 3, v5: x % 5, v6: x % 7 });
  console.log(`CRT solution:`, x, '| remainders', x % 3, x % 5, x % 7);
  return x;
}
// Honest cross-check: scan 0..104 and confirm exactly one match (the theorem’s claim).
function verify(){
  const r = readPicks(); const hits = [];
  for (let n = 0; n < M; n++)
    if (n % 3 === r[0] && n % 5 === r[1] && n % 7 === r[2]) hits.push(n);
  document.getElementById('work').textContent =
    fmt(`Scanning all numbers 0..104 for a match...
Numbers matching all three remainders: [%hits%]
Count = %length%  (the theorem promises exactly 1).`, { hits: hits.join(', '), length: hits.length });
  console.log(`brute-force matches:`, hits);
}
document.getElementById('go').addEventListener('click', assemble);
document.getElementById('verify').addEventListener('click', verify);
assemble();

<p class="hint">Pick a remainder for each base. The Chinese Remainder Theorem guarantees there is <b>exactly one</b> number from 0 to 104 that leaves all three remainders at once. Press <b>Assemble</b> to rebuild it.</p>
<div class="picks">
  <label>mod 3 <select id="r3"><option>0</option><option selected>2</option><option>1</option></select></label>
  <label>mod 5 <select id="r5"><option>0</option><option>1</option><option>2</option><option selected>3</option><option>4</option></select></label>
  <label>mod 7 <select id="r7"><option>0</option><option>1</option><option selected>2</option><option>3</option><option>4</option><option>5</option><option>6</option></select></label>
</div>
<div class="btns">
  <button id="go" type="button">Assemble</button>
  <button id="verify" type="button" class="ghost">Verify by scanning</button>
</div>
<div class="answer" id="answer">x ≡ 2 (mod 3),  3 (mod 5),  2 (mod 7)</div>
<div class="work" id="work"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.picks { display: flex; gap: 1rem; flex-wrap: wrap; margin: .2rem 0 .8rem; }
label { font: 600 14px system-ui, sans-serif; color: #1d3557; display: flex; align-items: center; gap: .4rem; }
select { font: 600 14px system-ui, sans-serif; padding: .3rem .4rem; border: 1px solid #cdd9e3; border-radius: 6px; background: #fff; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.answer { font: 700 22px ui-monospace, monospace; color: #0a7d33; min-height: 1.4em; margin: .3rem 0; }
.work { font: 500 13px ui-monospace, monospace; color: #41506a; line-height: 1.7; white-space: pre-wrap;
        background: #f2f6f9; border: 1px solid #dde6ee; border-radius: 8px; padding: .6rem .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chinese Remainder Theorem for the pairwise-coprime bases 3, 5, 7 (product M = 105).
// For each base m_i we precompute a "basis number" e_i with:
//   e_i ≡ 1 (mod m_i)  and  e_i ≡ 0 (mod every other base).
// Then the unique solution is x = (r3*e3 + r5*e5 + r7*e7) mod 105.
const MS = [3, 5, 7], M = 105;

// Extended Euclid -> modular inverse of a mod m.
function inv(a, m){
  let [old_r, r] = [((a % m) + m) % m, m];
  let [old_s, s] = [1, 0];
  while (r !== 0){ const q = Math.floor(old_r / r);
    [old_r, r] = [r, old_r - q * r]; [old_s, s] = [s, old_s - q * s]; }
  return ((old_s % m) + m) % m;
}
// Basis number for base index i: Mi = M/mi, then ei = Mi * inv(Mi mod mi, mi).
function basis(i){ const mi = MS[i], Mi = M / mi; return (Mi * inv(Mi % mi, mi)) % M; }
const E = MS.map((_, i) => basis(i));

function readPicks(){
  return [ +document.getElementById('r3').value,
           +document.getElementById('r5').value,
           +document.getElementById('r7').value ];
}
function assemble(){
  const r = readPicks();
  let x = 0; const parts = [];
  for (let i = 0; i < 3; i++){ x = (x + r[i] * E[i]) % M;
    parts.push(r[i] + '·' + E[i]); }
  document.getElementById('answer').textContent = 'x = ' + x;
  document.getElementById('work').textContent =
    fmt(`Basis numbers (each ≡1 at its base, ≡0 at the others):
  e(mod3)=%v%,  e(mod5)=%v2%,  e(mod7)=%v3%
x = (%parts%) mod 105
x = %x%   →   %x% mod 3 = %v4%,  %x% mod 5 = %v5%,  %x% mod 7 = %v6%`, { v: E[0], v2: E[1], v3: E[2], parts: parts.join(' + '), x: x, v4: x % 3, v5: x % 5, v6: x % 7 });
  console.log(`CRT solution:`, x, '| remainders', x % 3, x % 5, x % 7);
  return x;
}
// Honest cross-check: scan 0..104 and confirm exactly one match (the theorem’s claim).
function verify(){
  const r = readPicks(); const hits = [];
  for (let n = 0; n < M; n++)
    if (n % 3 === r[0] && n % 5 === r[1] && n % 7 === r[2]) hits.push(n);
  document.getElementById('work').textContent =
    fmt(`Scanning all numbers 0..104 for a match...
Numbers matching all three remainders: [%hits%]
Count = %length%  (the theorem promises exactly 1).`, { hits: hits.join(', '), length: hits.length });
  console.log(`brute-force matches:`, hits);
}
document.getElementById('go').addEventListener('click', assemble);
document.getElementById('verify').addEventListener('click', verify);
assemble();

Result

Console

Notice the magic. The three small clues never conflict and never leave you with two candidates: every one of the 3 × 5 × 7 = 105 combinations of remainders maps to its own unique number. That is the whole content of the theorem — and the demo rebuilds the number directly, with no searching, by combining three precomputed "basis" numbers.

The Real Complexity

How hard is the CRT, really? Reassuringly, not hard at all — and that is precisely why it is so valuable.

It is proven. The special case appears in Sunzi Suanjing (around the 4th century); the general statement and modern proof were given by Carl Friedrich Gauss in his Disquisitiones Arithmeticae (1801). When the moduli are pairwise coprime, a unique solution always exists below their product.
It is constructive and fast. You do not search. You compute one modular inverse per modulus using the extended Euclidean algorithm, then combine. The running time is polynomial in the number of digits — among the easiest, P-class problems.
It is a one-to-one map. Reducing a number to its remainders, and rebuilding it, are perfect inverses. Nothing is lost, nothing is ambiguous.

So the CRT sits firmly on the easy side of the line drawn by P vs NP. The interesting twist is the company it keeps: it is the friendly, polynomial-time tool that makes the hard problem of factoring — the bedrock of RSA — practical to work around at speed.

Where It Matters

"Split one hard computation into several small independent ones, then recombine" is the CRT's gift, and it shows up everywhere numbers get large:

RSA speedups: instead of one expensive exponentiation modulo a huge number, RSA decryption works modulo each prime factor separately and stitches the results with the CRT — typically about 4× faster. See RSA.
Error-correcting codes: residue number systems detect and repair corrupted data, because a wrong remainder stands out against the others.
Secret sharing: a secret can be split into shares (its remainders) so that only enough of them together reconstruct it.
Fast arithmetic: huge integers are carried as bundles of small remainders, letting additions and multiplications run independently — even in parallel — before a final CRT recombination.

Learn the CRT and you have met the residue number system, the quiet engine that makes giant-number computation fast enough for real cryptography and signal processing.

Conclusion

The Chinese Remainder Theorem hides a quiet elegance: three small remainders, individually almost useless, together name one number with no ambiguity at all. What began as a riddle in Sunzi Suanjing is now a fully proven theorem with a fast algorithm — a textbook citizen of the easy, polynomial world.

And yet it earns its keep at the cutting edge. Every time your browser performs an RSA handshake, the CRT is there, splitting one hard exponentiation into smaller ones and stitching the answer back together. An ancient puzzle, still doing real work behind the scenes — proof that a clean idea about factoring and remainders never goes out of style.

Comments

Loading comments...

https://www.kipuhub.com/en/article/chinese-remainder-theorem/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Chinese Remainder Theorem

How three remainders pin down one number