Chapter 1. Early Edo Period

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≡a₁ (mod m₁) and x≡a₂ (mod m₂) and ... and x≡a_s (mod m_s) is given as x≡q (mod m₁m₂...m_s) 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.