Translation notice

Parts of this article were translated with assistance from DeepSeek . The translation may contain inaccuracies, and some terms or cultural references may be difficult to understand because of differences in language and cultural context. For precise wording, please read the original version. If you have questions about the cultural context or meaning, please contact me through the sidebar; I will be happy to help clarify them.

The Number Guessing Game

When three walk together, seventy is rare; Twenty-one branches of plum blossoms on five trees; Seven sons reunite at half-moon; Subtract one hundred and five, the answer appears.

——— (Ming Dynasty) Cheng Dawei, Suanfa Tongzong (General Collection of Arithmetic Methods)

The first time I became interested in the “Chinese Remainder Theorem” was simply because its name stood out so uniquely among all theorems. Its solution method, “Qin Jiushao’s Dayan Qiuyi Shu (The Art of Seeking One)”, is also an exceptionally elegant and sacred name that can spark boundless imagination in a high school student. This sacred piece of mathematics comes from the Sunzi Suanjing (The Mathematical Classic of Master Sun) from the Northern and Southern Dynasties—not the military strategist Sunzi who led troops during the Spring and Autumn period, but a mathematician surnamed Sun from that later era. The famous “chickens and rabbits in the same cage” problem also originates from this book.

Today, after school or work, we enjoy puzzle-solving and escape room games. In ancient times, people would buy a copy of Master Sun’s mathematical classic. After a day of farming or fighting (if they survived), they would go home, flip through it, and calculate how many rabbits there were or how many soldiers were in an army. Just as modern people use quirky mnemonics to remember key points, the poem at the beginning is a mnemonic summarized by puzzle experts of the Ming Dynasty after playing Master Sun’s game. Now, let’s also play.

Suppose you time-travel back to the Northern and Southern Dynasties and are captured by an officer who suspects you of being a spy. The officer says: if you can figure out how many soldiers are in the camp, it proves you are Han Chinese and you can go free; otherwise, you must be a spy sent by the barbarians. But you can only observe three things:

• When the guards line up in rows of three, two are left over;
• In rows of five, three are left over;
• In rows of seven, two are left over.

What would you guess?

Most people’s first reaction would be: try them one by one. Try 13, no; 17, no; 19, no… keep trying until you hit a number that satisfies all three conditions.

Of course you can do this, but it is somewhat impossible. After three tries you would probably lose your head. Not to mention that if many solutions satisfy these three conditions—there are infinitely many numbers that leave a remainder of 2 when divided by 3, and infinitely many that leave a remainder of 3 when divided by 5… This problem is designed to stump you. Yet, after some mental calculation, you’ll find that although the conditions seem fragmentary and suggest more than one answer, they eventually converge on a single integer. Not a bunch, not a vague interval—just one clear number.

Let’s actually try it. Starting from 1, the numbers that satisfy “remainder 2 when divided by 3” are 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32… Among these, the ones that also satisfy “remainder 3 when divided by 5” are: 8, 23, 38… Among those, the ones that satisfy “remainder 2 when divided by 7”: 23. So it is 23.

This answer carries a sense of joyful uncertainty—you’ve finally found it, but how do you know there aren’t any more?

Don’t Try One by One

We are too used to thinking of integers as things “one after another.”

1, 2, 3, 4, 5… like a staircase, step by step upward. So when we encounter conditions like “remainder 2 when divided by 3, remainder 3 when divided by 5, remainder 2 when divided by 7,” our intuition says: start checking from the beginning.

But the problem with this approach is obvious: the staircase is too long.

You’re looking for a number that satisfies multiple conditions simultaneously, not just one. When the conditions pile up, brute-force checking becomes a very crude and laborious task. Especially when the numbers get large, this labour quickly becomes undignified. You could try a hundred numbers and still not even touch a corner of the correct answer. Trying numbers one by one has the flavour of a “global search” from the start. It assumes you are hunting for a target along an infinitely long line.

This is a lot like calculating days of the week.

Today is Friday. In 1 day it will be Saturday, in 2 days Sunday. What day will it be in 100 days? Just count forward—one day at a time, 100 days. Count them one by one, and if you miscount, start over.

The remainder stands by, watching you sadly.

The remainder cannot directly tell you what day it will be in 100 days, but it can tell you where this integer sits within a certain cyclic system.

How Remainders Help Us

I really like the concept of modular arithmetic—dividing one number by another and taking the remainder. It has a very everyday feel to it.

Going back to the day-of-the-week problem:

Today is Friday. In 7 days it’s Friday again; in 14 days it’s still Friday. In 15 days, there is a remainder of 1, so push forward one day—Saturday. In 20 days, three sevens are twenty-one, one day short, so push backward one day—Thursday. In 100 days, 14 full cycles leave a remainder of 2—Sunday. So, the weekday system is essentially cyclic. You don’t need to know how many days have passed; knowing the remainder when divided by 7 is enough.

Another example: the clock.

It is 3 o’clock. In 12 hours it will be 3 o’clock again. The clock is not an infinitely extended straight line, but a circle. Time walks along it and eventually cycles back. To know the time, you glance at the clock. I believe no normal human being first sees the 12, then starts counting forward by how many hours have passed to determine the current time. Instead, you instantly lock onto where the hand is pointing on the clock face—even if the face has no numbers written on it.

The calendar is similar. 30 days, 31 days, 28 days, even leap years. You think time is moving forward, but it actually keeps bringing certain patterns back again and again.

Mathematics abstracts this into the concept of “mod.” A “mod” is a cycle. For instance, “remainder when divided by 7” is called “mod 7” ($mod$ $7$)—this is speaking in the world of weekdays. “Remainder when divided by 12” is speaking in the world of clocks. A day has 24 hours, so 1 a.m. the next day is, for us night owls, the 25th hour of today. In fact, “25 o’clock ≡ 1 o’clock (mod 24).”

Thus, a number is no longer just itself. In different moduli, it reveals different facets.

This is very much like a person.

At home, at school, in front of friends, in front of a loved one—the faces they show are not exactly the same. A single snapshot may not give you an accurate read on someone. But if you see many facets, you get closer to the truth.

What an integer looks like mod 3, mod 5, mod 7—these “remainders” fix its identity.

Introducing Number Theory Here

Gauss said:

Mathematics is the queen of the sciences, and number theory is the queen of mathematics.

Number theory is, essentially, the study of integers.

The world of integers, though seemingly low-key, even plain, has an internal order that is unfathomably deep. A great deal of modern mathematics, modern computer science, and modern cryptography ultimately comes back to integers, to remainders, to the afterimages of division.

It is marvellous.

Modular arithmetic is one of the most important tools in number theory. Just as calculus has the derivative, linear algebra has matrices, and geometry has coordinates, number theory’s most common tool is the modulus. Different numbers are regarded as the same number in the world of modular arithmetic, just as 25 o’clock ≡ 1 o’clock (mod 24) and day eight ≡ Monday (mod 7). This equivalence relation is called congruence.

  graph TD

M["Mathematics"]

M --> N["Number Theory"]
M --> FF["Calculus"]

N --> A["Integers"]

A --> B["Divisibility"]
B --> B1["Greatest Common Divisor (GCD)"]
B --> B2["Least Common Multiple (LCM)"]

A --> C["Prime Numbers"]
C --> C1["Prime Factorization"]

B --> D["Congruence (Modular Arithmetic)"]


D --> E["Euclidean Algorithm"]
E --> E1["Extended Euclidean Algorithm"]

D --> F["Euler's Theorem"]
D --> G["Fermat's Little Theorem"]

D --> H["Chinese Remainder Theorem"]

E1 --> H

H --> I["Modern Cryptography"]

I --> I1["RSA"]
I --> I2["ECC (Elliptic Curve Cryptography)"]
I --> I3["Digital Signature"]
I3 --> I4["Blockchain"]

Back to the Puzzle, and Finally Formulas Appear

All the above has been nothing but groundwork, just to let you know what these letters and three horizontal bars represent. It would feel a little unfaithful to modern mathematics if I reached this point without writing any formulas.

So now, let the formulas appear, but let them appear gradually.

Suppose we are looking for an integer (x) that satisfies:

$$x \equiv a_1 \pmod{m_1}$$$$x \equiv a_2 \pmod{m_2}$$$$\cdots$$$$x \equiv a_n \pmod{m_n}$$

That is, when $x$ is divided by $m_1$, the remainder is $a_1$; divided by $m_2$, remainder $a_2$; … divided by $m_n$, remainder $a_n$.

The Chinese Remainder Theorem tells us: if these moduli $m_1, m_2, \dots, m_n$ are pairwise coprime, then this system of congruences must have a solution, and modulo

$$ M = m_1 m_2 \cdots m_n $$

the solution is unique.

What Does “Pairwise Coprime” Mean?

We need these moduli to be as independent as possible, because we want to pinpoint a specific number. If you use 6 and 9 as moduli, they share a common factor of 3, causing the remainders to overlap—wouldn’t that be absurd?

So any two numbers we divide by must not share a common factor. For instance, 3 and 5 are coprime (neither is composed of the other’s factors), 3 and 7 are coprime, 5 and 7 are also coprime. They have no common factors; we will not waste a single opportunity to localize.

Thus, the Chinese Remainder Theorem does not hold unconditionally for all moduli; it has a clear boundary. This is one of the most fascinating aspects of mathematics: it never boasts casually. It always writes the conditions out plainly.

Why Is the Solution “Unique”?

Note that “unique” here does not mean only one integer satisfies the conditions forever, but rather that it is unique modulo (M).

That is to say, there may be infinitely many integers that satisfy the same set of remainder conditions, but they all differ from each other by multiples of (M). In the world of modulo (M), they are actually the same answer—i.e., they are congruent.

This is another reason why I love modular arithmetic. It compresses “infinitely many similar objects” into a single crisp class. Like ripples on the surface of the sea—though each ring is moving, you know they belong to the same rhythm.

What Is the Constructive Idea?

Mathematics does not merely hand you a conclusion; it gives you a path to build a bridge.

Let

$$ M_i = \frac{M}{m_i} $$

That is, divide the total product (M) by the (i)-th modulus to get that piece.

Because $M_i$ and $m_i$ are coprime, we can find an integer $y_i$ such that

$$ M_i y_i \equiv 1 \pmod{m_i} $$

Meaning: we hope that ($M_i$) becomes 1 in the world of modulo ($m_i$) simply by multiplying it by an appropriate number ($y_i$).

Then the solution can be written as:

$$ x \equiv \sum_{i=1}^n a_i M_i y_i \pmod{M} $$

The logic is actually quite simple. When you put ($M_i$) into the world of modulo ($m_j$), every term except the one where ($j=i$) will be divisible by ($m_j$) and turn into 0. Only the corresponding term survives, and it just equals ($a_i$).

This is a beautifully “directed” construction: each term speaks only to its own modulus and remains silent towards the others.

What Is the Extended Euclidean Algorithm?

You will notice that the construction above requires finding ($y_i$), which is a modular multiplicative inverse (i.e., finding a number such that when multiplied by the original number, the result is 1—just as $2 \times \frac12 = 1$, $\frac12$ is the multiplicative inverse of 2). How do we find it?

This is where the Extended Euclidean Algorithm enters the stage.

In short, the Euclidean Algorithm was originally used to find the greatest common divisor. The extended version further tells us: if two numbers are coprime, we can express 1 as an integer combination of them. That is, we can find integers $u, v$ such that

$$ au + bv = 1 $$

Once 1 can be expressed in this way, the inverse naturally appears.

The Euclidean Algorithm has a pleasant quality: it honestly performs divisions, and as it does, the structure emerges by itself.

Modern Essence: Actually Calculate 23

Now let’s work out the earlier problem:

$$ x \equiv 2 \pmod{3} $$

$$ x \equiv 3 \pmod{5} $$

$$ x \equiv 2 \pmod{7} $$

The moduli are 3, 5, 7, which are pairwise coprime, so we can use the Chinese Remainder Theorem.

First, calculate the total product:

$$ M = 3 \times 5 \times 7 = 105 $$

Then calculate each piece:

$$ M_1 = \frac{105}{3} = 35,\quad M_2 = \frac{105}{5} = 21,\quad M_3 = \frac{105}{7} = 15 $$

Next, we need to make each $M_i$ become 1 in its corresponding modulus.

For $m_1=3$: We need to find $y_1$ such that:

$$ 35y_1 \equiv 1 \pmod{3} $$

First see that the remainder of 35 divided by 3 is 2, so we are actually solving:

$$ 2y_1 \equiv 1 \pmod{3} $$

Try it: when $y_1=2$, $2 \times 2 = 4 \equiv 1 \pmod{3}$. So $y_1=2$.

For $m_2=5$: We need to find $y_2$ such that:

$$ 21y_2 \equiv 1 \pmod{5} $$

21 divided by 5 leaves remainder 1, so:

$$ y_2 \equiv 1 \pmod{5} $$

The simplest is to take $y_2=1$.

For $m_3=7$: We need to find $y_3$ such that:

$$ 15y_3 \equiv 1 \pmod{7} $$

15 divided by 7 leaves remainder 1, so:

$$ y_3 \equiv 1 \pmod{7} $$

The simplest is to take $y_3=1$.

Then the formula gives:

$$ x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105} $$

Compute each term:

$$ 2 \cdot 35 \cdot 2 = 140 $$

$$ 3 \cdot 21 = 63 $$

$$ 2 \cdot 15 = 30 $$

Add them up:

$$ 140+63+30=233 $$

Then take modulo 105:

$$ 233 \equiv 23 \pmod{105} $$

So the solution is:

$$ x \equiv 23 \pmod{105} $$

That is, 23, 128, 233, 338… all satisfy this set of remainder conditions, but modulo 105 they are all the same answer.

  flowchart LR

A["x ≡ 2 (mod 3)"]
B["x ≡ 3 (mod 5)"]
C["x ≡ 2 (mod 7)"]

A --> D["35 × inverse × 2"]
B --> E["21 × inverse × 3"]
C --> F["15 × inverse × 2"]

D --> G["Sum"]
E --> G
F --> G

G --> H["x = 23"]

The Ancient Method: Back to the Opening Poem

Now let us look again at the mnemonic poem at the very beginning, which was Cheng Dawei’s summary of Qin Jiushao’s method:

“When three walk together, seventy is rare.”

Multiply the remainder from division by 3 by 70.

Because $70 = 35 = 5 \times 7$ simultaneously satisfies $70 \equiv 1 \pmod{3}$, $70 \equiv 0 \pmod{5}$, and $70 \equiv 0 \pmod{7}$.

This means that after multiplying by 70, it preserves the original remainder in the world of mod 3, while completely “vanishing” in the worlds of mod 5 and mod 7.

“Five trees of plum blossoms, twenty-one a share.”

“Twenty-one” is 21.

Multiply the remainder from division by 5 by 21.

Because $21 = 3 \times 7$, and $21 \equiv 1 \pmod{5}$, while $21 \equiv 0 \pmod{3}$ and $21 \equiv 0 \pmod{7}$. So, it affects only the condition modulo 5 without disturbing the other two.

“Seven sons reunite at half-moon.”

The ancients said “half-moon” to mean fifteen.

Multiply the remainder from division by 7 by 15.

Because $15 = 3 \times 5$, satisfying $15 \equiv 1 \pmod{7}$, while $15 \equiv 0 \pmod{3}$ and $15 \equiv 0 \pmod{5}$.

It likewise only takes care of its own condition. Thus, we obtain three magical numbers:

Coefficient	mod 3	mod 5	mod 7
70	1	0	0
21	0	1	0
15	0	0	1

• 70 is responsible only for mod 3;
• 21 is responsible only for mod 5;
• 15 is responsible only for mod 7.

No matter how they are added together, they will not interfere with one another.

“Subtract one hundred and five, the answer appears.”

The “one hundred and five” here is precisely $105 = 3 \times 5 \times 7$.

After adding up the first three terms, repeatedly subtract 105 (which is exactly what we call taking modulo 105 today) until you get the smallest positive integer—that is the final answer.

At this point, you might feel that this seems somewhat different from the modern method introduced earlier. The formula we just learned also requires calculating a “modular multiplicative inverse”—why doesn’t this mnemonic describe that step?

The reason is that this is an extraordinarily lucky special case.

For the moduli (3, 5, 7), we have:

$$ 70 \equiv 1 \pmod{3}, $$

$$ 21 \equiv 1 \pmod{5}, $$

$$ 15 \equiv 1 \pmod{7}. $$

The three coefficients are already their own modular inverses by nature, so no extra calculation is needed at all.

For general Chinese Remainder Theorem problems, such luck normally does not occur. If the moduli were (4, 9, 11) or (5, 7, 11), simply using $M_i = \frac{M}{m_i}$ would no longer be enough; you must also multiply by the corresponding modular inverse, which is exactly the general formula in modern textbooks:

$$ x \equiv \sum a_i M_i N_i \pmod M, $$

where ($N_i$) is the modular inverse of ($M_i$) under the corresponding modulus.

In other words, this mnemonic is not a completely different algorithm, but rather an elegant instantiation of the modern Chinese Remainder Theorem formula when the moduli happen to be 3, 5, 7—much like the “3-4-5 triangle” in the Pythagorean theorem; both are special cases of theorems discovered by early Chinese mathematicians.

A thousand years ago, the ancients did not know the term “modular multiplicative inverse,” nor did they write down modern congruence formulas. Yet they had already discovered these three magical numbers—70, 21, 15—and condensed them into a twenty-eight character mnemonic. Even today, when we re-examine it using modern algebra, we can still see the core idea of the Chinese Remainder Theorem.

How the Internet Applies It

When You Open an HTTPS Website

For example, visiting this very site:

https://hpu.edu.kg

Your browser and my server perform a handshake.

During this, the server needs to prove:

“I am hpu.edu.kg.”

Its method is:

use its own RSA private key to digitally sign a piece of data.

Here is the problem.

The RSA private key operation is very slow.

Because it requires computing something like

$$ m^d \bmod n $$

where

• $n=pq$
• $p, q$ are both prime numbers of several hundred digits.

Directly computing such an exponentiation requires handling integers with thousands of bits.

How Does the Chinese Remainder Theorem Speed It Up?

The RSA private key possesses information that no one else has:

the server knows

$$ n = pq $$

Therefore, it does not need to compute

$$ m^d \bmod n $$

directly. Instead, it can split the problem into two smaller ones.

First compute

$$ m^d \bmod p $$

Then compute

$$ m^d \bmod q $$

These two moduli are only half the original length.

The computation is much faster.

Finally, use the Chinese Remainder Theorem:

recombine the two answers back into

$$ m^d \bmod n $$

The whole process is:

  flowchart LR

A["RSA private key operation
m^d mod n"]

A --> B["Split"]

B --> C["Compute mod p"]
B --> D["Compute mod q"]

C --> E["CRT recombination"]
D --> E

E --> F["Final signature / decryption result"]

F --> G["HTTPS / SSH / VPN"]

This is the most famous application of CRT in RSA.

Why Is It So Much Faster?

Assume:

RSA is 2048-bit.

Then

• p is approximately 1024 bits
• q is approximately 1024 bits

Modern multiplication complexity is not linear.

When the integer length is halved,

the computational load typically drops to about one quarter of the original.

Two quarters added together

are roughly

half of the original.

Taking fast exponentiation algorithms into account,

in practice:

CRT-RSA is usually about 3 to 4 times faster than direct RSA private key operations.

Therefore, almost all RSA implementations use CRT.

Without CRT,

server performance would degrade significantly.

So What Does It Affect?

Almost all places that use an RSA private key.

For example:

• HTTPS website certificates
• SSH logins
• VPN authentication
• Software digital signatures
• PDF digital signatures
• Email encryption (S/MIME)

Whenever a server needs to perform an RSA private key operation,

CRT is almost always involved.

---

What About Blockchain?

When people mention blockchain, the first things that come to mind are certainly cryptocurrencies—Bitcoin, Ethereum, and so on—but these hardly involve CRT. This is because they primarily use ECDSA (Elliptic Curve Digital Signature Algorithm), not RSA, so CRT is not a core component.

However, blockchain technology depends on digital signatures, and digital signatures have many implementations.

  flowchart LR

A["Chinese Remainder Theorem"]

A --> B["RSA"]

B --> C["Digital signature"]

C --> D["HTTPS"]

C --> E["Software signatures"]

C --> F["Identity authentication"]

C -. "Modern blockchains more often adopt\nElliptic Curve Digital Signatures" .-> G["Blockchain"]

Conclusion

You nervously answered the officer’s question, proved your identity, and successfully returned to the modern day.

When you need to prove your identity, the server performs a digital signature using its private key, and the Chinese Remainder Theorem can split one enormous modular exponentiation into two smaller calculations, then merge the results back together. In almost all RSA implementations, this optimization called CRT-RSA has become standard practice, speeding up private key operations by about 3 to 4 times. Precisely because of this, a mathematical theorem born two thousand years ago still silently operates at the very foundations of modern internet infrastructure—HTTPS, SSH, VPN, software signing, and more. That we can access Google, YouTube, and ChatGPT through a VPN is also something we owe to those ancient formulas written on scrap paper.

Looking again at that problem in the Sunzi Suanjing, it is not merely a case of “the ancients could calculate.” Humanity realized very early on that certain problems do not need to be confronted head-on. You can take a detour, look at it from another angle. You can break an invisible whole into a set of visible parts; and from those parts, you can piece the whole back together.

I don’t know exactly how many days have passed since the day humans first began to record dates. That number is too large. But if I divide that number by 7 and take the remainder, I know what day of the week today is; divide it by 12 and take the remainder, I know which month it corresponds to; divide it by 365 and take the remainder, I know which day of the year it is.