Théorème Chinois

Suite à une petite discussion avec Wendell, une petite présentation du théorème chinois. Au 3ème siècle, Sun Tsu a développé une technique élégante pour compter le nombre de soldat de la Grande Armée chinoise. Il les fait s'aligner sur 13, 17, 19, 23 colonnes et compte seulement le nombre de soldat qui ne forme pas une rangée complète: petit schéma d'explication sur 3 rangs:

résultat: Sun Tsu ne compte que jusqu'à 2... Notons N le nombre de soldat de la grande armée et A le produit a1.a2.a3 ... Le problème s'écrit alors:

N = n1 [a1]
N = n2 [a2]
N = n3 [a3]
...

si on choisit a1, a2, a3 ... tels qu'ils soient premiers 2 à 2 alors N s'écrit sous la forme:

N=n1.n1.(A/a1) + n2.n2.(A/a2) + n3.n3.(A/a3)...

Comment calculer e1, e2, e3....? Ben en fait c'est super simple: il suffit de calculer e1 avec une identité de Bezout:

e1 tel que e1.a1 + n1.(A/a1) = 1
et donc n1.n1.(A/a1) = n1 [a1]

à partir de là on vérifie facilement que la solution est la bonne modulo A. Voila Wendell : c'est ça le théorème Chinois...

Tags: théorème, chinois, modulo, Bezout, identité