Wednesday, December 20, 2006

The Chinese Theorem

Following a little discussion with Wendell, a little presentation of the Chinese theorem. At the 3rd century, Sun Tsu developed an elegant way to count the number of soldier of the Great Army of China. It makes them be aligned on 13, 17, 19, 23 columns and count only the number of soldier who does not form a complete row: a small diagram to explane on 3 rows:
razzrazzrazzrazzrazzrazzrazz

razzrazzrazzrazzrazzrazzrazz

razzrazzrazzrazzrazzrazz

result: Sun Tsu counts only up to 2… Let us note N the number of soldier of the large army and A the product it a1.a2.a3… the problem is then:
NR = n1 [a1]
NR = N2 [a2]
NR = n3 [a3]
...
if a1, a2, a3… are chosen to be prime 2 to 2 then N can be written as:
cool N=n1.n1.(A/a1) + n2.n2.(A/a2) + n3.n3.(A/a3)...
How to calculate e1, e2, e3….? In fact it is very simple: just use the correct identity of Bezout:
idea e1 such as e1.a1 + n1. (A/a1) = 1
and so arrow n1.n1.(A/a1) = 1 [a1]
from there you can easily check that the solution is the good one modulo A.
Voila Wendell: this is the Chinese theorem… razz

No comments: