L'histoire du théorème des restes chinois commence… en Chine, sous forme d'énigmes. La suivante est due au mathématicien et astronome Sun Zi, qui vécut entre le IIIe et le Ve siècle de notre ère (et qui ne doit pas être confondu avec le général Sun Zi) :
« Quand le général Han Xing range ses soldats par trois, il reste deux soldats, quand il les range par cinq, il en reste trois et quand il les range par sept, il en reste deux. Combien l'armée de Han Xing comporte-t-elle de soldats ? »
Derrière l'habillage ludique, il s'agit d'un problème d'arithmétique lié à la divisibilité. Sans encore le résoudre, on peut remarquer que, s'il a une solution, on en obtient une autre en ajoutant cent cinq soldats car 105 est multiple de 3, 5 et 7 ce qui, en itérant cette remarque, en produit une infinité. On en déduit que, si une solution existe, il en existe une entre 1 et 105. L'énigme est ainsi potentiellement résolue, puisqu'il suffit alors d'essayer un nombre fini de valeurs !
Cependant, cette démarche est fastidieuse et peu éclairante. Il est préférable de répondre séparément aux trois conditions posées. Pour qu'il reste deux soldats quand on les groupe par trois, l'effectif total doit être l'un des nombres 2, 5, 8, 11, 14, 17, 20, 23, 26, 29… Pour qu'il en reste trois quand on les groupe par cinq, l'effectif doit être l'un des nombres 3, 8, 13, 18, 23, 28… Enfin, pour qu'il en reste deux quand on les range par sept, l'effectif total doit être l'un des nombres 2, 9, 16, 23, 30… Le nombre 23 appartient aux trois suites, donc il s'agit d'une solution au problème, et c'est la plus petite.
Les autres sont 128, puis 233, et ainsi de suite en ajoutant 105 à chaque fois. Cette démarche est déjà plus claire, mais on peut s'enfoncer davantage dans les rouages de la question. Pour cela, il est utile d'introduire une nouvelle vision des nombres, celle de l'arithmétique modulaire.
L'arithmétique de l'horloge
Les conditions posées dans l'énigme de l'armée de Han Xing s'expriment mieux dans une arithmétique qui fut introduite par Carl Gauss au début du XIXe siècle : l'arithmétique modulaire (ou arithmétique de l'horloge). Arrêtons-nous sur la définition de cette arithmétique particulière. On dit que deux nombres sont égaux modulo n (où n est un nombre entier supérieur ou égal à 2) s'ils ont le même reste dans la division par n (c'est-à-dire si leur différence est un multiple de n). Dans ce cadre, l'effectif de l'armée de Han Xing est égal à 2 modulo 3, à 3 modulo 5 et à 2 modulo 7. L'énigme se généralise en remplaçant les modules 3, 5 et 7 par des nombres premiers entre eux deux à deux, ce qui donne le théorème des restes chinois : si p, q… sont des nombres premiers entre eux deux à deux et a, b… des entiers, alors il existe un nombre unique modulo le produit p q … qui est égal à a modulo p, à b modulo q, etc.
Une version de ce théorème fournit une formule pour ce nombre unique dont l'existence est affirmée. Pour l'instant, remarquons que si la propriété ne porte que sur deux couples de nombres, p et q premiers entre eux d'un côté, a et b de l'autre, le problème revient à chercher des coïncidences dans les deux suites arithmétiques a, a + p, a + 2p, a + 3p… et b, b + q, b + 2q, b + 3q…, c'est-à-dire à chercher deux nombres x et y tels que a + xp = b + yq. Cette relation évoque un théorème important en arithmétique, celui de Bachet, parfois attribué à tort à Bezout : si deux nombres p et q sont premiers entre eux, alors il existe u et v tels que up + vq = 1.
Ces nombres u et v peuvent être calculés au moyen de l'algorithme d'Euclide. Voyons comment il fonctionne sur l'exemple de 11 200 et 3 533. On divise d'abord le plus grand nombre par le plus petit, soit 11 200 par 3 533, ce qui donne la relation 11 200 = 3 × 3 533 + 601, que l'on écrit sous la forme 11 200 – 3 × 3 533 = 601. L'idée de l'algorithme est de produire des combinaisons de 11 200 et 3 533 de plus en plus petites jusqu'à arriver à 1. On divise donc 3 533 par 601, ce qui donne 3 533 = 5 × 601 + 528. En utilisant la relation précédente, on en déduit –5 × 11 200 + 16 × 3 533 = 528. On divise alors 601 par 528, et on continue ainsi jusqu'à obtenir le résultat cherché, soit 1 452 × 11 200 – 4 603 × 3 533 = 1.
Les anneaux modulaires
L'ensemble des entiers entre 0 et n – 1 muni de l'addition et de la multiplication modulo n est un anneau, noté ℤ / nℤ c'est-à-dire que les opérations y suivent les règles habituelles, à l'exception du fait que les éléments non nuls ne sont pas forcément inversibles. Plus précisément, un élément de ℤ / nℤ est inversible s'il est premier avec n. Prenons l'exemple de n = 11 200, dont les facteurs premiers sont 2, 5 et 7. Un élément de ℤ / nℤ est inversible s'il n'est multiple ni de 2, ni de 5 et de 7 ; ainsi, 3 533 est inversible dans cet anneau. L'identité de Bachet trouvée plus haut donne –4 603 × 3 533 = 1 modulo 11 200. L'inverse de 3 533 est donc égal à 11 200 – 4 603, soit 6 597.
La solution dont l'existence et l'unicité sont affirmées dans le théorème des restes chinois s'exprime en fonction d'inverses dans des anneaux modulaires. On reprend les hypothèses et les notations du théorème en notant n le produit pq… puis p' = n / p, q' = n / q… Les nombres p et p', q et q'… sont premiers entre eux deux à deux. On considère u l'inverse de p' modulo p, v celui de q' modulo q… On montre alors que le nombre x = uap' + vbq' + … est la solution cherchée.
Revenons à l'armée de Han Xing avec cet outil. Les nombres p, q et r sont égaux à 3, 5 et 7 ; leur produit n est égal à 105, donc p', q' et r' sont égaux à 35, 21 et 15 respectivement. L'inverse u de p' (soit 35) modulo p = 3 est 2, puisque 70 = 1 modulo 3. Le premier terme uap' est donc égal à 140.
De même, vbq' vaut 63 et wcr' est égal à 30, donc x = 233 = 23 modulo 105, qui est bien le résultat trouvé. Vous savez désormais dénombrer facilement des grandes quantités en les alignant astucieusement !
Lire la suite