6.2 Rod numerals and the Chinese remainder theorem

Counting Rods and Decimal System

Ancient Chinese Counting Tools

Counting rods were the primary calculation tools in ancient China for roughly 1,500 years, from the Warring States period (around the 5th century BCE) through the medieval era. These small sticks, typically made of bamboo or ivory, were arranged on a flat surface in specific patterns to represent numbers and carry out arithmetic.

The system worked through two alternating patterns based on place value:

• Units, hundreds, ten-thousands (odd-position places) used vertical rods: one vertical rod for 1, two for 2, up to five. For 6 through 9, a horizontal rod on top represented five, with vertical rods beneath for the remainder.
• Tens, thousands (even-position places) flipped the orientation: horizontal rods for 1 through 5, with a vertical rod on top for values 6 through 9.

This alternation between vertical and horizontal orientations made it easy to distinguish adjacent place values at a glance. Red rods represented positive numbers and black rods represented negative numbers, giving Chinese mathematicians a working concept of negative quantities centuries before Europe adopted them.

With these rods, mathematicians could perform addition, subtraction, multiplication, and division directly on a counting board, physically rearranging the rods through each step of a calculation.

Development of Decimal Place Value System

The rod numeral system was inherently decimal, built on powers of ten. Each column on the counting board represented a successively higher power: ones, tens, hundreds, thousands, and so on.

• A blank space on the board indicated the absence of a value in that place, functioning as a zero placeholder long before a written symbol for zero was formalized.
• This structure allowed efficient representation of very large numbers without needing new symbols.
• The place-value logic enabled systematic algorithms for arithmetic, much like the column-based methods students learn today.

The Chinese decimal system developed independently from, and roughly contemporaneously with, the Babylonian positional system (which used base 60). Its base-10 structure would later parallel the Hindu-Arabic numeral system that became the global standard.

Applications and Significance

• Rod numerals made financial record-keeping and tax collection far more accurate across Chinese dynasties.
• Astronomical calculations and calendar reform depended heavily on the precision these tools provided.
• Engineering projects, including large-scale construction and land surveying, benefited from the ability to handle complex arithmetic reliably.
• The system laid the computational foundation for the advanced algebraic and number-theoretic work that followed in later centuries.

Sunzi Suanjing and the Chinese Remainder Theorem

Sunzi Suanjing: A Mathematical Classic

The Sunzi Suanjing ("Master Sun's Mathematical Manual") is an ancient Chinese text composed sometime between the 3rd and 5th centuries CE. Its author, Sun Tzu, is not the famous military strategist of the same name. The text covers a range of practical mathematical topics, from basic arithmetic to problems in measurement and distribution.

Its most famous contribution is a deceptively simple-sounding puzzle: "Find a number that leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 7." The answer is 23. This problem is the earliest known statement of what we now call the Chinese Remainder Theorem.

Chinese Remainder Theorem: Fundamental Concept

The Chinese Remainder Theorem (CRT) provides a method for finding a number that simultaneously satisfies several remainder conditions. In modern notation, you're looking for a value $x$ such that:

$x \equiv a_1 \pmod{m_1},\quad x \equiv a_2 \pmod{m_2},\quad \ldots,\quad x \equiv a_k \pmod{m_k}$

The theorem guarantees a unique solution modulo $m_1 \cdot m_2 \cdots m_k$ as long as the moduli are pairwise coprime (meaning every pair shares no common factor other than 1). For the Sunzi problem, 3, 5, and 7 are pairwise coprime, so a unique solution exists modulo $3 \times 5 \times 7 = 105$.

Here's how the solution method works in broad strokes:

1. Compute the product of all moduli: $M = m_1 \cdot m_2 \cdots m_k$.
2. For each congruence, compute $M_i = M / m_i$ (the product of all the other moduli).
3. Find the modular inverse of each $M_i$ with respect to $m_i$. That is, find $y_i$ such that $M_i \cdot y_i \equiv 1 \pmod{m_i}$.
4. The solution is $x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 + \cdots + a_k M_k y_k \pmod{M}$.

Applications of Modular Arithmetic

Modular arithmetic is the math of remainders. When you say $17 \equiv 2 \pmod{5}$, you mean 17 divided by 5 leaves a remainder of 2. Numbers "wrap around" after reaching the modulus, like hours on a clock.

This framework, which the CRT depends on, turned out to have enormous reach:

• Ancient Chinese astronomers used it to reconcile cycles of different lengths when calculating calendar dates.
• Modern cryptography (including RSA encryption) relies on CRT to speed up computations with very large numbers.
• Computer science uses CRT in error-correcting codes and for distributing large calculations across smaller, parallel operations.
• Digital signal processing applies modular techniques to handle periodic signals efficiently.

Qin Jiushao and the Dayan Qiuyishu

Qin Jiushao: Mathematical Innovator

Qin Jiushao (1202–1261 CE) was a Song Dynasty mathematician whose work represents one of the high points of medieval Chinese mathematics. His major text, the Shushu Jiuzhang ("Mathematical Treatise in Nine Sections," published 1247), tackled problems ranging from military logistics to land measurement to astronomy.

Among his contributions:

• A general method for solving higher-degree polynomial equations numerically (similar to what is now called Horner's method, but developed independently and centuries earlier).
• Techniques for numerical computation that extended well beyond what earlier Chinese texts had covered.
• Most significantly for this unit, a fully systematic algorithm for solving systems of linear congruences, even when the moduli are not pairwise coprime.

Dayan Qiuyishu: Advanced Problem-Solving Algorithm

The Dayan Qiuyishu (roughly, "Great Extension Method for Finding Unity") was Qin Jiushao's generalized algorithm for the Chinese Remainder Theorem. Where the Sunzi Suanjing presented a single worked example, Qin provided a step-by-step procedure that could handle a wide range of problems.

What made it a genuine advance over the original CRT formulation:

• It included a systematic procedure for computing modular inverses, equivalent to what we'd now recognize as the extended Euclidean algorithm.
• It addressed cases where the moduli share common factors, reducing them to a pairwise coprime system before applying the main algorithm.
• It was designed for practical application: Qin used it to solve real problems in calendar computation and military planning.

The algorithm essentially formalized and generalized what had been a collection of problem-specific tricks into a reliable, repeatable method.

Impact and Legacy of Qin's Work

Qin Jiushao's Dayan Qiuyishu was one of the most sophisticated number-theoretic algorithms anywhere in the world during the 13th century. European mathematicians would not develop comparable general methods for solving systems of congruences until Euler and Gauss worked on the problem in the 18th and 19th centuries.

• The algorithm demonstrated that Chinese mathematicians were doing serious, systematic number theory, not just collecting isolated clever solutions.
• It influenced later Chinese mathematical writing and remained a reference point for scholars in the Yuan and Ming dynasties.
• The underlying ideas connect directly to modern number theory, abstract algebra, and the computational methods used in cryptography today.

Qin's work is a clear example of how practical needs (calendars, logistics, astronomy) drove the development of deep mathematical theory in medieval China.