# Chapter 1. Early Edo Period

## ColumnCongruence Notation and Remainder Theorem (Level 2)

The linear Diophantine equation takes the form of ax+by=c with a, b, and c as a given integer, and studies whether integer solution x, y may exist or not. For example, an infinite number of solutions exist for 2x+3y=1 such as x=2, y=-1, but there is none for 2x+6y=1. Moreover, the solution for 2x+3y=1 takes the form of x=2+3t, y=-1-2t, with t as any integer. K. F. Gauss expressed the fact that (x-2) is a multiple of 3 by writing x≡2(mod 3), and decided to call the notation, for example, "x is congruent to 2 modulo 3". The necessary and sufficient condition for ax+by=c to have a solution is that c be a multiple of the greatest common divisor of a and b (usually written d=(a,b)), and then ax≡c (mod b) and by≡c (mod a) hold true. When d=1 (a and b are relatively prime), ax≡c (mod b) has the solution of the form x≡p(mod b), and when d>1, it has the solution of the form x≡q(mod c/d).

As the congruence equation in the form of ax≡b (mod c) can be rewritten x≡s (mod t) if it has a solution, the question at the next step is what becomes of a solution for the simultaneous congruence equation in the form of x≡a (mod m) and x≡b (mod n). The necessary and sufficient condition for the equation to have a solution is that a≡b (mod d) holds true, assuming that d is the greatest common divisor of m and n. Particularly, when d=1 (in other words, m and n are relatively prime), the solution takes the form of x≡p (mod mn). A solution for s simultaneous congruence equations: x≡a1 (mod m1) and x≡a2 (mod m2) and ... and x≡as (mod ms) is given as x≡q (mod m1m2...ms) by repeating the process above. This is called the Chinese Remainder Theorem.

In the following, we would like to explain the congruence notation and the congruence equation with examples: a≡b (mod c) means that (a-b) is a multiply of c, and a-b=cn holds true with a given n. Let's look at examples of mod 3:

...-9≡-6≡-3≡0≡3≡6≡9...(mod 3)
...-8≡-5≡-2≡1≡4≡7≡10...(mod 3)
...-7≡-4≡-1≡2≡5≡8≡11...(mod 3)

As indicated by the above examples, the integers are divided into 3 groups of numbers that are congruent to each other. [Generally, mod m divides the entire integers into m groups] When thinking of the addition and multiplication of integers at the group level: (the red one is a representation in each group):
0+0=0, 0+1=1, 0+2=2, 1+1=2, 1+2=0, 2+2=1, 0×0=0, 0×1=0, 0×2=0, 1×1=1, 1×2=2, 2×2=1
We can understand that the above holds true for any number within the same group. For this reason, the equation in the form of ax≡b (mod c) has regular solutions.

Let's think about the equation of 2x≡1 (mod 3). As 2×2=1, all the numbers in group 2 are its solutions and x≡1 (mod 3) is the answer. However, the equation of 3x≡1 (mod 3) does not have any solutions. (As 3 belongs to the same group as 0, multiplying any number by it does not produce 1.) The equation ax≡b (mod c) can be solved when b is a multiple of the greatest common divisor of a and c, and can be solved regardless of whatever number b is if a and c are relatively prime (or the greatest common divisor is 1).

Next, let's think about the equation of 15x≡21 (mod 33). The greatest common divisor of 15 and 33 is 3, and since 21 is a multiple of 3, there must be a solution. This equation is equivalent to 15x-21=33n, and the two sides can be divided by 3. 5x-7=11n is derived from the division, which is equivalent to 5x≡7 (mod 11) To solve this equation, we should look for a number that is a multiple of 5 by adding 11 to 7 and continuing to add 11 to the previous sum. Since 40 (=7+11×3) is a multiple of 5, the solution x≡8 (mod 11) is derived from 5x≡40 (mod 11). Rewriting this solution with mod 33, we have three solutions: x≡8 (mod 33), x≡19 (mod 33), and x≡30 (mod 33).

Now, let's look at an example of a simultaneous congruence equation. We will solve x≡a (mod 3) & x≡b (mod 5) & x≡c (mod 7), which is derived by generalizing the problem in Jinkoki. Since 3, 5, and 7 are relatively prime, the existence of a solution in the form of x≡p (mod 3×5×7) is known from the Chinese Remainder Theorem. Confirm that x(=s+t+u) satisfies the conditions, where s satisfies s≡a (mod 3) & s≡0 (mod 5) & s≡0 (mod 7), t satisfies t≡b (mod 5) & t≡0 (mod 3) & t≡0 (mod 7), and u satisfies u≡c (mod 7) & u≡0 (mod 3) & u≡0 (mod 5). Now, let's actually find s, t, and u.

As s is a multiple of 35 and divisible by 3 with remainder a, and 70 is the minimum number that is a multiple of 35 and divisible by 3 with remainder 1, we get s=70a. As t is a multiple of 21 and divisible by 5 with remainder b, and 21 is the minimum number that is a multiple of 21 and divisible by 5 with remainder 1, we get t=21b; as u is a multiple of 15 and divisible by 7 with remainder c, and 15 is the minimum number that is a multiple of 15 and divisible by 7 with remainder 1, we get u=15c. Therefore, the solution is x≡70a+21b+15c (mod 105). As the problem in Katsuyo sanpo corresponds to the case of a=2, b=1, c=5, the solution is x≡70×2+21×1+15×5 (mod 105) or x≡236 (mod 105), and we get x≡26 (mod 105) by tidying it up.

Top of page