Current location - Training Enrollment Network - Mathematics courses - China's Mathematical Remainder Theorem
China's Mathematical Remainder Theorem
China's residue theorem, also known as China's residue theorem, is a theorem about the linear congruence equations in number theory, which explains the criteria and methods for solving the linear congruence equations. Also known as Sun Tzu's Theorem, it was called "Han Xin points soldiers", "Sun Tzu's Theorem", "Seeking a Skill" (Shen Songkuo), "Ghost Valley Calculation", "Partition Calculation", "Pipe Cutting" (Song Yanghui) and "Qin Wang secretly points soldiers".

The original text is as follows:

If you don't know how to count things, three or three will leave two, five or five will leave three, and seven or seven will leave two. Ask geometry? That is, an integer divided by three is greater than two, divided by five is greater than three, and divided by seven is greater than two. Find this integer.

Solution: Three people walked seventy times, five trees and twenty-one clubs, and seven children reunited for half a month. 105 didn't know until later.

It means: the remainder obtained by dividing by 3 is multiplied by 70, the remainder obtained by dividing by 5 is multiplied by 2 1, and the remainder obtained by dividing by 7 is multiplied by 15. After adding them all, subtract the integer multiple of 105 or 105 to get the answer.

70 x2+2 1x 3+ 15 x2 = 233 = 105 x2+23,

The result is 23.

Solution example:

Example 1: A number divided by 5 is 1 and divided by 3 is 2. What is the minimum quantity?

Adopt a general method: gradual satisfaction method.

Sort 1 divided by 5 from small to large: 1, 6, 1 1,16,21,26, ...

Then from small to large, we found that the smallest is 1 1.

So 1 1 is an ideal number.

Meet one condition first, and then meet another condition, so it is called "gradual satisfaction method".

Example 2: A number divided by 5 is 1 and divided by 3 is 1. What is the minimum quantity? (except 1

Special method: least common multiple method

Divided by 5, the remaining 1: indicates that the number minus 1 is a multiple of 5.

Divided by 3, the remaining 1: indicates that the number minus 1 is also a multiple of 3.

So this number minus 1 is the common multiple of 3 and 5. Minimum requirement, so this number minus 1 is the least common multiple of 3 and 5. That is, this number is 1 5 after subtracting1,so this number is 15+1=16.

Example 3: A number divided by 5 is 4 and divided by 3 is 2. What is the minimum quantity?

In this case, the least common multiple method can also be used.

A number divided by 5 is greater than 4, which means that this number plus 1 is a multiple of 5.

This number divided by 3 is greater than 2, which means that this number plus 1 is also a multiple of 3.

So this number plus 1 is the common multiple of 3 and 5. The requirement is the lowest, so this number plus 1 is the least common multiple of 3 and 5. That is, this number plus 1 is 15, so this number is 15- 1 = 14.

For multiple numbers, such as three numbers, sometimes two of them can use special methods, so first find the number that meets two conditions by special methods, and then find the number that meets the last condition by general methods.

Example 4: There is a number 1, divided by 7, leaving 2. Divided by 8 leaves 4, divided by 9 leaves 3, what is the minimum number?

The number divided by 7 and 2 can be written as 7n+2.

Numbers like 7n+2 are divided by 8 and 4. Since 2 is divided by 8 and 2, 7n needs to be divided by 8 and 2.

7n divided by 8 is greater than 2, and 7 divided by 8 is greater than 7. If n is divided by 8 and greater than 6 (the remainder of the multiplier is equal to the product of the remainder), then the minimum value of n is 6.

So the minimum number satisfying "divide by 7 and 2, divide by 8 and 4" is 7×6+2=44.

All numbers that meet the requirements of "7 divided by 2, 8 divided by 4" can be written as 44+56× mm.

Require 44+56×m divided by 9 plus 3. Since 44 is divided by 9 and 8, 56×m is required to be divided by 9 and 4. (Addendum equals remainder)

56×m is divided by 9 and 4. Since 56 is divided by 9 and 2, M is required to be divided by 9 and 2 (the multiplier is equal to the product of the remainder), so M is the smallest.

Therefore, the minimum number satisfying "divide by 7 and 2, divide by 8 and 4, divide by 9 and 3" is 44+56×2= 156.

Example 5: Three-three numbers leave two, five-five numbers leave three, and seven-seven numbers leave two. Ask geometry?

That is, an integer divided by 3 and 2, divided by 5 and 3, divided by 7 and 2, to find this integer.

Numbers divided by 3 and 2 and 7 and 2 can be written as 2 1n+2.

2 1n+2 divided by 5 remainder 3 requires 2 1n divided by 5 remainder 1.

2 1n divided by 5 remainder 1, 2 1 divided by 5 remainder 1, it needs n divided by 5 remainder 1 (the remainder of the multiplier is equal to the multiplication of the remainder), so the minimum value of n is 1.

Therefore, the minimum number satisfying "divide by 3 and 2, divide by 5 and 3, divide by 7 and 2" is 2 1× 1+2=23.

Standard solution: First, find out the smaller numbers 15, 2 1 70 which are divisible by 7, 5 and 3 from the common multiples of 3 and 5, 3 and 7 respectively (note: this step is also called "modular inversion" operation, which can be obtained relatively quickly by using the extended Euclidean method and computer programming. Of course, that is

15 ÷ 7 = 2 ... Remaining 1,

2 1 ÷ 5 = 4 ... Remaining 1,

70 ÷ 3 = 23 ... Remaining 1.

Then multiply the product of the remainder obtained by dividing the required number by 7, 5 and 3 by three smaller numbers,

15× 2+21× 3+70× 2 = 233. (replace 233 with I, the program can be found. )

Finally, the sum 233 is divided by the least common multiple of divisors 3, 5 and 7.

233 ÷ 105 = 2 ... Yu 23,

This remainder 23 is the qualified minimum number.

Example 6: What is the smallest number when a number is divided by 5, 6 and 3?

The topic can be seen as: divide by 5, divide by 6, divide by 4, divide by 7, divide by 4. See that "4 divided by 6, 4 divided by 7"? If there is congruence, just find the least common multiple of 6 and 7, and add 4, it is a number that meets the following conditions, 6X7+4=46.

Next, let's try whether 46 can meet the first condition, "A number divided by 5 makes the remainder 2". If not, add 46 to the least common multiple of 6 and 7, 42, until the requirement of "a number divided by 5 and the remainder is 2" can be met. The reason for this step is that 42 is the least common multiple of 6 and 7. No matter how it is added, it will meet the condition of "divided by 6 to 4 and divided by 7 to 4".

46+42=88

46+42+42= 130

46+42+42+42= 172

The minimum number is 172.