China has made brilliant achievements in ancient mathematics. Today, Mr. and Mrs. Wu will introduce China's remainder theorem, which is very famous in the history of Chinese mathematics.

1 Han Xin's soldier problem

This question begins with a story called "Han Xin ordered soldiers".

At the end of Qin Dynasty, Chu and Han contended. Han Xin, one of the three outstanding heroes of early han dynasty, once led 1500 soldiers to fight, and four or five hundred people died. In order to count the number of remaining soldiers, Han Xin ordered three soldiers in a row, with two more; 5 people in a row, more than 4 people; Seven people in a row, more than six. On this basis, Han Xin quickly stated the number of people: 1049. The Han army was very convinced of General Han Xin, and later it was convinced that Han Xin was a "god from heaven, and his plan was clever", so the morale was greatly boosted and the drums were deafening. In the next battle, the Han army pressed hard, and the Chu army made a mess and fled in defeat. Han Xin is famous all over the world, and is praised by later generations as a "soldier fairy" and a "handsome god".

So how did Han Xin quickly calculate the number of soldiers? Han Xin's soldier problem can be described in modern mathematical language as follows: if the number of soldiers is 0, divide by 3, divide by 2, divide by 5, divide by 4, divide by 7 and divide by 6.

We can also use congruence to express this problem:

We found that if it can be divisible by 3, 5 and 7 at the same time, that is

So it must be an integer multiple of the least common multiple of 3, 5 and 7. Because 3, 5 and 7 are prime numbers, then

therefore

that is

So, where are the positive integers?

In this way, Han Xin calculated the number of remaining soldiers.

2 Sun Tzu's problem of calculating classics and not knowing things.

This kind of problem is actually to solve the congruence equations in elementary number theory. In the history of mathematics, Han Xin's problem of ordering soldiers is also known as the governor's problem, which was first recorded in Sun Tzu's Art of War more than 1000 years ago:

"

I don't know how many things happened today. What is the geometry of things?

Transforming into modern mathematical language is to solve the congruence satisfied by integers.

This problem is similar to the problem of Han Xin's ordering soldiers mentioned above, but it is not as good as the last one, because no matter adding or subtracting a number, it cannot be divisible by 3, 5 and 7 at the same time. So, how to solve this problem?

In the first and second volumes of Shu Shu Jiu Zhang (1247), Qin, a mathematician in the Song Dynasty, gave a complete and systematic answer to the question that "things are unknown". Cheng Dawei, a mathematician in the Ming Dynasty, compiled this solution into a catchy Art of War by Sun Tzu:

"

The three of them are in seventy, five trees and twenty-one clubs (twenty-one), and the seven sons are reunited for half a month, except for one hundred and five ambassadors.

The meaning of this poem is: the remainder obtained by dividing 3 by 70, the remainder obtained by dividing 5 by 2 1, the remainder obtained by dividing 7 by 15, and the remainder obtained by dividing them all by 105 is the answer.

According to this algorithm, we can get:

Therefore, the smallest positive integer solution of the unknown problem is that 23 really meets the requirements of division by 3 and 2, division by 5 and 3, and division by 7 and 2. The general solution to this problem is as follows

Where is a natural number.

3 China remainder theorem

For this problem, if it is general, how to deal with it? For example, there are congruences:

We decompose this problem into three congruence equations.

Then the initial problem has the smallest positive integer solution.

So as long as we can find someone who meets the requirements. For example, from the congruence formula,

therefore

So the existence makes

therefore

Its existence can be proved because of the following theorem:

"

If so, there must be something that makes

For the proof of this theorem, we can consider the smallest positive integer in the set, as long as we prove that this smallest positive integer is 1.

Consider the smallest positive integer,, which can only be 1 because it is coprime.

This matter can be proved by reduction to absurdity: inseparable, inseparable.

therefore

Therefore, the remainder can also be expressed by multiplying an integer by another integer, and because it is less than, this contradicts the assumption that it is the smallest positive integer at first, so it must be.

Therefore, the existence is proved.

In fact, this kind of problem not only exists, but also is easy to find, where 70 is the smallest positive integer that can be divisible by 5 and 7 at the same time and divided by 3 remainder 1, so it can be obtained in the same way, so this kind of problem has a general solution:

It turns out that the three numbers 70,21and 15 in the ancient poems above come from this!

Generally speaking, given different prime numbers, the congruence equation

There must be a solution. To solve this problem, we only need to construct a basic solution system:

So there is

Because they are all prime numbers, their existence is obvious.

The process and method to solve the above problems are called "China's Remainder Theorem" and "Sun Tzu's Theorem".

China's remainder theorem was first spread to Europe in 1852 by Alexander Wylie, a British missionary in China. 1874, the British mathematician Matheson pointed out that this method conforms to the general theorem of congruence solution obtained by Gauss in 180 1, so it is called "China's remainder theorem" in the west and becomes a very important theorem in elementary number theory.