Algorithms in Ancient Chinese Mathematics

★ On the rolling division method, searched, in China's ancient "nine chapters of arithmetic" on the record, now excerpted as follows:

Approximate division of the art said: "can be half of half of it, not half of the person, the vice of placing the denominator, the son of the number of the denominator, in order to reduce the number of more than a little, more phase reduction, and seek its equal also. To equal the number of about."

The "equal number" is the highest common denominator. The way to find the "equal number" is the "more subtractive" method, which is actually the method of division.

Rolling over and dividing to find the greatest common divisor is a better way to do it, and it's faster.

Can you quickly find the greatest common divisor of the numbers 52317 and 75569? Normally you would look for the common **** making factor, this is a tricky question, it's not easy to find, the prime factor is large.

Now I'll teach you to find the greatest common divisor by rolling over and dividing.

First, the larger 75569 divided by 52317, get the quotient 1, the remainder 23252, then 52317 divided by 23252, get the quotient 2, the remainder is 5813, and then 23252 as the divisor, 5813 as the divisor, exactly divided by the quotient 4. 5813 is the greatest common divisor of 75569 and 52317. You won't find it if you factorize it.

So, how does this rolling division get to the greatest common divisor? I'm going to talk to the guys about it below.

For example, there is a requirement for the greatest common divisor of two integers, a and b, a > b, then we first divide a by b to get a quotient of 8 and a remainder r1: a ÷ b = q1...r1 We can of course rewrite the above equation as a multiplication equation: a = bq1 + r1 ------l)

If r1 = 0, then b is the greatest common divisor of a and b is the greatest common divisor of 3. If r1 ≠ 0, continue dividing, dividing b by r1, and we can have the same equation as above:

b = r1q2 + r2-------2)

If the remainder r2 = 0, then r1 is the greatest common divisor of the sum sought, 3. Why? Because if equation 2) becomes b = r1q2, then the convention of b1r1 must be the convention of a1b. This is because a number that divides both b and r1 must then, by equation l), be able to divide a, and thus also be the common divisor of a1b.

In turn, if a number, d, can divide both a1b, then by the equation 1), it must also be able to divide r1, and thus there is also a convention that d is b1r1.

In this way, the covenant of a and b is exactly the same as the covenant of b and r1, and then the greatest common divisor of these two pairs must also be the same. So isn't the greatest common divisor of b1r1, at r1 = 0, r1? So the greatest common divisor of a and b is also r1.

Some may say, what about r2 not equal to 0? Then, of course, you continue on, dividing r1 by r2, ...... until the remainder is zero.

In this method, the one who does the divisor first becomes the divisor in the latter step, and that's where the name tumbling division comes from, I guess.