Théorème des restes chinois - Définition

Introduction

Le théorème des restes chinois est un résultat d'arithmétique modulaire traitant de résolution de systèmes de congruences. Ce résultat, établi initialement pour Z/nZ, se généralise en théorie des anneaux. Ce théorème est utilisé en théorie des nombres.

Fragments d'histoire

La forme originale du théorème, contenue dans un livre du mathématicien chinois Qin Jiushao publié en 1247, est un résultat concernant les systèmes de congruences (voir arithmétique modulaire). Mais on trouve trace d'un problème analogue dans le livre de Sun Zi, le Sunzi suanjing datant du III^e siècle :

Combien l'armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste deux soldats, rangés par 5 colonnes, il reste trois soldats et, rangés par 7 colonnes, il reste deux soldats ?

On peut penser que les Chinois, férus de calculs astronomiques, puissent être intéressés par des concordances de calendrier et qu'ils aient été amenés très tôt à s'intéresser à des questions du type :

Dans combien de jours la pleine lune tombera-t-elle au solstice d'hiver ?

Si la question se pose alors qu'il reste 6 jours avant le solstice d'hiver et 3 jours avant la pleine lune, la question se traduit par :

Existe-t-il un entier x tel que le reste de la division de x par 365 donne 6 et le reste de la division de x par 28 donne 3 ?

La résolution proposée par Sun Zi pour le problème des soldats est la suivante :

Multiplie le reste de la division par 3, c’est-à-dire 2, par 70, ajoute lui le produit du reste de la division par 5, c’est-à-dire 3, avec 21 puis ajoute le produit du reste de la division par 7, c'est-à-dire 2 par 15. Tant que le nombre est plus grand que 105, retire 105.

Mais la solution n'explique qu'imparfaitement la méthode utilisée.

Enfin, il serait dommage de ne pas présenter ce problème concernant des pirates et un trésor, très fréquemment cité pour illustrer le théorème des restes chinois :

Une bande de 17 pirates possède un trésor constitué de pièces d'or d'égale valeur. Ils projettent de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Un nouveau partage donnerait au cuisinier 4 pièces. Dans un naufrage ultérieur, seuls le trésor, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier s'il décide d'empoisonner le reste des pirates ?

L'arithmétique modulaire a rendu ce type de problème plus facile à résoudre.

Résultat pour les anneaux

Dans les anneaux

Le théorème chinois a également une version plus abstraite : si n₁, ..., n_k sont deux à deux premiers entre eux alors, en notant n le produit des n_i, l'application

est un isomorphisme d'anneau.

Pour le montrer, on remarque d'abord que les deux ensembles et ont le même nombre d'éléments. Comme est un morphisme d'anneau, il suffit donc de démontrer qu'il est injectif pour en déduire que c'est un isomorphisme. Pour cela, il suffit de montrer que son noyau est réduit à 0 : si α = 0[n_i] pour , c’est-à-dire si α est un multiple de chaque n_i, alors α = 0[n], c’est-à-dire α est un multiple du produit . Ceci résulte de l'hypothèse que les n_i sont premiers entre eux deux à deux.

Dans le cas où les n_i ne sont pas premiers entre eux, n est leur ppcm et le morphisme ci-dessus n'est qu'injectif. Il existe une solution au problème initial si et seulement si les données sont dans l'image, c'est-à-dire que le pgcd de n_i et n_j divise α_i − α_j pour tout couple i,j.

Dans un anneau principal

Pour un anneau principal R, le théorème des restes chinois prend la forme suivante : Si u₁, ..., u_k sont les éléments de R qui sont premiers entre eux deux à deux, et u désigne le produit u₁...u_k, alors l'anneau R/uR et l'anneau produit R/u₁R x ... x R/u_kR sont isomorphes par l'isomorphisme

tel que

L'isomorphisme inverse peut être construit comme ceci. Pour chaque i, les éléments u_i et u/u_i sont premiers entre eux, et par conséquent, il existe des éléments r et s dans R avec

ru_i + su / u_i = 1

Fixons e_i = s u/u_i. On a :

pour j ≠ i.

Alors l'inverse est la transformation

telle que

Résultat pour les anneaux généraux

Une des formes les plus générales du théorème des restes chinois peut être formulée en termes d'anneau et d'idéal (à gauche ou à droite). Si R est un anneau et I₁, ..., I_k des idéaux de R qui sont deux à deux premiers entre eux (ce qui signife que I_i + I_j = R lorsque i ≠ j), alors l'idéal produit I de ces idéaux est égal à leur intersection, et l'anneau quotient R/I est isomorphe à l'anneau produit R/I₁ x R/I₂ x ... x R/I_k via l'isomorphisme de R / I dans qui à associe .