Chapter 1. Early Edo Period

As this theorem appears in a book in ancient China called Sunzi suanjing, it is called the "Chinese remainder theorem" in the West, and it deals with the remainder from the division of one number by another number. Sunzi suanjing includes the following problem: "A number is divisible by 3 with remainder 2, by 5 with remainder 3, and by 7 with remainder 2. What is the number?" The book solves this problem as follows: "Numbers that are divisible by 3 with remainder 2 include 140, those that are divisible by 5 with remainder 3 include 63, and those that are divisible by 7 with remainder 2 include 30. Adding these three numbers together produces 233. Subtracting 105 from this 233 and continuing to subtract 105 from the previous remainder produces the numbers 128, 23, .... Among the results, 23 is the minimum number that satisfies the conditions." The number 105 is derived by product of the divisors 3, 5, and 7; hence in Wasan this calculation method was called Hyakugo genzan (hundred five subtraction) after this number.
So, why can this problem be solved by this method?

Suppose:
That a is a number that is exactly divisible both by 5 and by 7, and divisible by 3 with remainder 2,
That b is a number that is exactly divisible both by 3 and by 7, and divisible by 5 with remainder 3,
That c is a number that is exactly divisible both by 3 and by 5, and divisible by 7 with remainder 2.

Confirm that 140, 63, and 30 in the above solution correspond to a, b, and c, respectively. In the case of a, 140 can be broken down into prime factors: 5×7×2². Since 140 includes 5x7, it is exactly divisible both by 5 and by 7.
Here, when creating M, which satisfies the equation M=a+b+c, we know that M is divisible by 3 with remainder 2, by 5 with remainder 3, and by 7 with remainder 2. Therefore, 233=140+63+30 is a number that certainly satisfies the conditions; and it is the Chinese Remainder Theorem that states that such numbers repeat themselves infinitely in a cycle of 105. we would like to explain this theorem using a simpler case.

Question:. What is a number that is divisible by 2 with remainder 1 and by 3 with remainder 2?

If we divide the numbers from 1 to 12 by 2 and by 3 and list the remainders in a table, we can obtain the following table:

n	1	2	3	4	5	6	7	8	9	10	11	12
Remainder when divided by 2	1	0	1	0	1	0	1	0	1	0	1	0
Remainder when divided by 3	1	2	0	1	2	0	1	2	0	1	2	0

As 2 and 3 are relatively prime, 6 (=2x3) types of patterns appear, and the pattern for n=1 to 6 is repeated for n=7 to 12. The table shows us that the numbers to be found are 5 and 11, and we can deduce that the numbers with the same property are 17, 23, 29, ... derived by adding 6 to 11 and continuing to add 6 to the previous sum. Furthermore, the Chinese Remainder Theorem states that the pattern for remainders from divisions of numbers by p numbers that are relatively prime repeats itself in a cycle of the product of those p numbers.
Now, let's solve this problem with the method shown in Sunzi suanjing. Find the multiples of 3 that are divisible by 2 with remainder 1: we can find they are 3, 9, 15, ...; next find the multiples of 2 that are divisible by 3 with remainder 2: we can find they are 2, 8, 14, ...; and we can find 5, 11, 17, ... as the solutions by adding the former numbers to the latter ones.

Let us now return to Hyakugo genzan. The pattern of each set of remainders that are derived by dividing the numbers from 1 to 105 by 3, 5, and 7 differs from each other.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...	21	70	105
Remainder when divided by 3	1	2	0	1	2	0	1	2	0	1	2	0	1	2	0	...	0	1	0
Remainder when divided by 5	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	...	1	0	0
Remainder when divided by 7	1	2	3	4	5	6	0	1	2	3	4	5	6	0	1	...	0	0	0

The entire pattern repeats itself for the numbers from 106 to 210, and after that it indefinitely repeats itself for each set of 105 numbers. If we write out all the patterns, we can obtain the numbers to be found; as this is obviously a time-consuming job, we can find the answer more easily with the method for creating M described above.

Jinkoki by Yoshida Mitsuyoshi includes the following problem with a slightly changed number from that presented in Sunzi suanjing: "A number is divisible by 3 with remainder 2, by 5 with remainder 1, and by 7 with remainder 2. What is the number?" Let's solve this problem.
As 70 (=2x5x7) is exactly divisible by 5 and by 7, and divisible by 3 with remainder 1, 140 or 2 times 70 is also exactly divisible by 5 and by 7, and divisible by 3 with remainder 2.
And, 21(=3x7) is exactly divisible by 3 and by 7, and divisible by 5 with remainder 1.
As 15 (=3x5) is exactly divisible by 3 and by 5, and divisible by 7 with remainder 1, 30 or 2 times 15 is also exactly divisible by 3 and by 5, and divisible by 7 with remainder 2.
Then, the number 191 (=140+21+30) derived by adding these three numbers is divisible by 3 with remainder 2, by 5 with remainder 1, and by 7 with remainder 2. Subtracting 105 (=3x5x7) from this number does not affect the remainder because it is exactly divisible by 3, by 5, and by 7. Therefore, 86 (=191-105) is the minimum of numbers to be obtained.
(In fact, as 35 (=5X7) is exactly divisible by 5 and by 7, and divisible by 3 with remainder 2, we can immediately find the solution: 86 (=35+21+30). The method explained above is a generalized method: to find a number that is exactly divisible by p and by q, and divisible by r with remainder s, we first look for the minimum number that is exactly divisible by p and by q, and divisible by r with remainder 1, and finally can find the number that is exactly divisible by p and by q, and divisible by r with remainder s by multiplying the minimum number by s.)

In Wasan, the solution in the Chinese Remainder Theorem is called Senkanjutsu (Seki Takakazu's method on the remainder problems). That is the term used in Katsuyo sanpo, and it is said to have been borrowed from the mathematical textbook Yang Hui suanfa written in China in the thirteenth century, which Seki studied.

We would like to introduce a problem and the solution to it that are described in Katsuyo sanpo. For the problem of "What is the minimum number that is divisible by 5 with remainder 1 and by 7 with remainder 2?", add 21 or a number that is a multiple of 7 and divisible by 5 with remainder 1 to 30, or a number that is a multiple of 5 and divisible by 7 with remainder 2 to produce 51, which is divisible by 5 with remainder 1 and by 7 with remainder 2. As 35 (=5x7) is exactly divisible both by 5 and by 7, the answer is 16 (=51-35). This is how the logic flowed in the book.
In addition to this, Seki described other problems such as "What is the minimum number that is divisible by 36 with remainder 2 and by 48 with remainder 14?" and "What is the minimum number that is divisible by 3 with remainder 2, by 5 with remainder 1, and by 7 with remainder 5?" The former problem needs some device because the two divisors are not relatively prime, and Seki also mentioned the method.

In current mathematics, argument for the Chinese Remainder Theorem is discussed with the notation called the congruence equation, invented by K. F. Gauss (1777-1855).

Gauss began Disqvisitiones arithmeticae (1801), which he published at the age of 24, with an explanation of the congruence equation. The congruence equation is a symbol that came from the problem of the indeterminate equation discussed by Diophantos, a mathematician in Alexandria in the third century, and now is being systematically discussed in the field of elementary number theory. Note that the Japanese edition of this book by Gauss was published in 1995 under the title of Gausu seisuron (Number Theory by Gauss). The congruence notation, in a form such as 137≡2(mod 3), might not have been taught in school, but addition, subtraction, and multiplication can be handled as usual and more automatically solved if they are described with a congruence notation.

For these, see "Congruence Notation and Remainder Theorem".