Théorème des restes chinois

La forme originale du théorème apparait sous forme de problème dans le livre de Sun Zi, le Sunzi suanjing (en), datant du III^e siècle[1]. Il est repris par le mathématicien chinois Qin Jiushao dans son ouvrage le Shùshū Jiǔzhāng (« Traité mathématique en neuf chapitres ») publié en 1247. Le résultat concerne les systèmes de congruences (voir arithmétique modulaire).

Soient des objets en nombre inconnu. Si on les range par 3 il en reste 2. Si on les range par 5, il en reste 3 et si on les range par 7, il en reste 2. Combien a-t-on d'objets ?

Cette énigme est parfois associée au général Han Xin (en) comptant son armée[2].

La résolution proposée par Sun Zi pour ce problème 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. On peut cependant remarquer que :

• 70 a pour reste 1 dans la division par 3 et pour reste 0 dans les divisions par 5 et 7 ;
• 21 a pour reste 1 dans la division par 5 et pour reste 0 dans les divisions par 3 et 7 ;
• 15 a pour reste 1 dans la division par 7 et pour reste 0 dans les divisions par 3 et 5.

Le nombre 233 (2 × 70 + 3 × 21 + 2 × 15) a bien alors pour restes respectifs 2, 3 et 2 dans les divisions par 3, 5 et 7. Enfin, comme 105 (3×5×7) a pour reste 0 dans les trois types de division, on peut l’ôter ou l'ajouter autant de fois que l'on veut sans changer les valeurs des restes. La plus petite valeur pour le nombre d'objets est alors de 23.

On retrouve ce problème presque à l'identique en 1202 dans le Liber Abbaci de Fibonacci[3] dans le chapitre XII qui concerne les problèmes et énigmes où l'on trouve également le problème des lapins de la suite de Fibonacci. Le problème avait aussi été étudié par Ibn al-Haytham (Alhazen) – voir l'article Mathématiques arabes – dont Fibonacci a pu lire les œuvres.

Euler[4] s'est également intéressé à cette question, ainsi que Gauss[5].

Selon Ulrich Libbrecht (de)[6], la motivation de ce type de calcul chez les Chinois serait l'astronomie. On peut en effet 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 ?

Mais selon Daumas et al.[7], il s'agirait plus probablement de problèmes associés à des comptages par paquets, peut-être d'origine divinatoire.

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 ?

La réponse est 785. Les nombres 17, 11 et 6 étant premiers entre eux deux à deux, les solutions sont distantes d'un multiple de 1122 (17×11×6) ; par ailleurs 785 vérifie bien l'énoncé : 785 = 17×46 + 3 = 11×71 + 4 = 6×130 + 5. Il s'ensuit que 785 est bien le plus petit des nombres possibles[8].

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

Soient ${\displaystyle n_{1}}$, …, ${\displaystyle n_{k}}$ des entiers deux à deux premiers entre eux, c'est-à-dire que PGCD (n_i , n_j) = 1 lorsque i ≠ j. Alors pour tous entiers ${\displaystyle a_{1}}$, …, ${\displaystyle a_{k}}$, il existe un entier ${\displaystyle x}$, unique modulo ${\displaystyle n=\prod _{i=1}^{k}n_{i}}$, tel que

${\displaystyle {\begin{matrix}x\equiv a_{1}{\pmod {n_{1}}}\\\ldots \\x\equiv a_{k}{\pmod {n_{k}}}\\\end{matrix}}}$

Une solution ${\displaystyle x}$ peut être trouvée comme suit. Pour chaque i, les entiers ${\displaystyle n_{i}}$ et ${\displaystyle {\hat {n}}_{i}={\frac {n}{n_{i}}}=n_{1}\ldots n_{i-1}n_{i+1}\ldots n_{k}}$ sont premiers entre eux. D'après le théorème de Bachet-Bézout on peut calculer l'inverse ${\displaystyle v_{i}\,}$de ${\displaystyle {\hat {n}}_{i}}$ modulo ${\displaystyle n_{i}}$. Pour cela, on peut utiliser l'algorithme d'Euclide étendu et obtenir des entiers ${\displaystyle u_{i}\,}$ et ${\displaystyle v_{i}\,}$ tels que ${\displaystyle u_{i}n_{i}+v_{i}{\hat {n}}_{i}=1}$. Si on pose ${\displaystyle e_{i}=v_{i}{\hat {n}}_{i}}$, alors nous avons

${\displaystyle e_{i}\equiv 1{\pmod {n_{i}}}\,}$ et ${\displaystyle e_{i}\equiv 0{\pmod {n_{j}}}\,}$ pour j ≠ i.

Une solution particulière de ce système de congruences est par conséquent

${\displaystyle x=\sum _{i=1}^{k}a_{i}e_{i}~,}$

et les autres solutions sont les entiers congrus à ${\displaystyle x}$ modulo le produit ${\displaystyle n}$.

L'exemple de Sun Zi, présenté plus haut dans la section histoire, se réduit à

${\displaystyle x\equiv 2{\pmod {3}}\,}$

${\displaystyle x\equiv 3{\pmod {5}}\,}$

${\displaystyle x\equiv 2{\pmod {7}}\,}$

on obtient alors

• ${\displaystyle n=3\times 5\times 7=105}$
• ${\displaystyle {n_{1}}=3}$ et ${\displaystyle {\hat {n}}_{1}=5\times 7=35}$ , or ${\displaystyle 2{\hat {n}}_{1}\equiv 1{\pmod {3}}}$ donc ${\displaystyle e_{1}=70}$
• ${\displaystyle n_{2}=5}$ et ${\displaystyle {\hat {n}}_{2}=3\times 7=21}$ , or ${\displaystyle {\hat {n}}_{2}\equiv 1{\pmod {5}}}$ donc ${\displaystyle e_{2}=21}$
• ${\displaystyle n_{3}=7}$ et ${\displaystyle {\hat {n}}_{3}=3\times 5=15}$ , or ${\displaystyle {\hat {n}}_{3}\equiv 1{\pmod {7}}}$ donc ${\displaystyle e_{3}=15}$

une solution pour x est alors ${\displaystyle x=2\times 70+3\times 21+2\times 15=233}$

et les solutions sont tous les entiers congrus à 233 modulo 105, c'est-à-dire à 23 modulo 105.

Les systèmes de congruences peuvent être résolus même si les n_i ne sont pas premiers entre eux deux à deux. Le critère précis est le suivant :

une solution x existe si et seulement si ${\displaystyle a_{i}\equiv a_{j}{\pmod {{\rm {PGCD}}(n_{i},n_{j})}}}$ pour tous i et j. L'ensemble des solutions x forme alors une classe de congruence modulo le PPCM des n_i.

Exemple : le système x ≡ –1 mod 4 et x ≡ –1 mod 6 équivaut à : x + 1 multiple de 4 et 6 c'est-à-dire de PPCM(4, 6) = 12, ou encore : x ≡ –1 mod 12.

Une méthode de résolution de tels systèmes est la méthode chinoise, qui consiste à se ramener à des modules premiers entre eux deux à deux (dans l'exemple ci-dessus : les modules 4 et 3). Une autre est la méthode des substitutions successives.

La résolution du système ${\displaystyle \left\{{\begin{array}{l}x\equiv r{\pmod {a}}\\x\equiv s{\pmod {b}}\end{array}}\right.}$  , d'inconnue ${\displaystyle x}$ , passe par le calcul du PPCM de ${\displaystyle a}$ et ${\displaystyle b}$.

Une roue dentée comportant ${\displaystyle a}$ dents s'engrène dans une autre roue dentée comportant elle ${\displaystyle b}$ dents. Combien de dents doivent passer pour que sa ${\displaystyle r}$-ième dent vienne en coïncidence avec la ${\displaystyle s}$-ième dent ?

Le PPCM des deux nombres ${\displaystyle a}$ et ${\displaystyle b}$ est ce qui permet de comprendre le comportement périodique de ce système : c'est le nombre de dents séparant deux contacts de même congruence. On peut donc trouver la solution, s'il y en a une, dans l'intervalle ${\displaystyle [1,{\rm {{PPCM}(a,b)]}}}$. Il y a une solution si PGCD(a, b) divise r – s .

Pour cet engrenage, ${\displaystyle \left\{{\begin{array}{l}x\equiv 4~(mod~15)\\x\equiv 10~(mod~12)\end{array}}\right.}$ , PPCM(12,15)=60 , pour x ∈ [1,60] , la solution est x = 34 .

On peut comprendre simplement pourquoi le calcul sur des roues dentées fait intervenir de l'arithmétique modulaire, en remarquant que l'ensemble des dents d'une roue en comptant n peut être paramétré par l'ensemble des racines n-ièmes de l'unité, qui a une structure de groupe naturellement isomorphe à celle de ℤ/nℤ.

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 PPCM des n_i, c'est-à-dire dans le cas présent le produit des n_i, l'application (à valeurs dans l'anneau produit)

est un isomorphisme d'anneaux.

Par exemple, la table suivante[9] compare ${\displaystyle \mathbb {Z} /15\mathbb {Z} }$ et ${\displaystyle \mathbb {Z} /3\mathbb {Z} \times \mathbb {Z} /5\mathbb {Z} }$ et chaque paire d'éléments de ${\displaystyle \mathbb {Z} /3\mathbb {Z} \times \mathbb {Z} /5\mathbb {Z} }$ apparaît exactement une et seule fois :

Pour le montrer, on remarque d'abord que les deux ensembles finis ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ et ${\displaystyle \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z} }$ ont le même nombre d'éléments. Comme ${\displaystyle \phi }$ est un morphisme d'anneaux, 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 ${\displaystyle \alpha \equiv 0\mod {n_{i}}}$ pour ${\displaystyle i=1,\dots ,k}$, c’est-à-dire si ${\displaystyle \alpha }$ est un multiple de chaque n_i, alors ${\displaystyle \alpha \equiv 0\mod n}$, c’est-à-dire ${\displaystyle \alpha }$ est un multiple du produit n₁, …, n_k. 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 deux à deux premiers entre eux, 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 a_i – a_j pour tout couple (i, j).

Pour un anneau principal R, le théorème des restes chinois prend la forme suivante : Si r₁, …, r_k sont des éléments de R qui sont premiers entre eux deux à deux, et r désigne le produit r₁…r_k, alors le morphisme d'anneaux

est un isomorphisme.

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

${\displaystyle u_{i}r_{i}+v_{i}{\frac {r}{r}}_{i}=1}$

Fixons e_i = v_i r / r_i. On a :

${\displaystyle e_{i}\equiv 1{\pmod {r_{i}}}\quad \mathrm {et} \quad e_{i}\equiv 0{\pmod {r_{j}}}}$

pour j ≠ i.

Alors l'inverse de f est le morphisme construit à l'aide des idempotents e_i (mod r) :

Le théorème des restes chinois permet de résoudre explicitement tout système de congruences dans l'anneau euclidien R = K[X] des polynômes sur un corps K, c'est-à-dire tout système de la forme.

${\displaystyle \forall i\in \{0,\ldots ,n\},P\equiv A_{i}{\pmod {R_{i}}}}$

où les données sont des polynômes R_i deux à deux premiers entre eux et des polynômes A_i, et l'inconnue est le polynôme P.

L'interpolation lagrangienne correspond au cas particulier où les R_i sont de la forme X – x_i et les A_i sont constants, et fournit la solution P de degré ≤ n . Plus explicitement, si x₀, x₁, … , x_n sont n + 1 éléments de K distincts deux à deux, on prend pour E_i les polynômes interpolateurs de Lagrange, définis par : ${\displaystyle E_{i}={(X-x_{0})(X-x_{1})...(X-x_{i-1})(X-x_{i+1})...(X-x_{n}) \over (x_{i}-x_{0})(x_{i}-x_{1})...(x_{i}-x_{i-1})(x_{i}-x_{i+1})...(x_{i}-x_{n})}.}$ Pour j différent de i, E_i est divisible par R_j, de sorte que E_i ≡ 0 modulo R_j. Par ailleurs, modulo R_i, X ≡ x_i, de sorte que E_i ≡ 1 modulo R_i.

Pour n + 1 éléments quelconques y₀, y₁, … , y_n de K, dire qu'un polynôme P est tel que P(x_i) = y_i pour tout i, est équivalent à dire que P ≡ y_i modulo R_i. Un tel polynôme P est donné par ${\displaystyle P=\sum _{i=0}^{n}y_{i}E_{i},}$ ce qu'on peut vérifier par un calcul direct.

Le théorème des restes chinois n'a pas lieu en toute généralité dans les anneaux factoriels. Considérons par exemple l'anneau factoriel ${\displaystyle \mathbb {Z} [X]}$. Soit p un nombre premier. Alors p est irréductible dans ${\displaystyle \mathbb {Z} [X]}$, et est par conséquent premier dans cet anneau. Maintenant, posons a₁ = 0, et a₂ = 1, tous deux éléments de ${\displaystyle \mathbb {Z} [X]}$. Posons aussi n₁ = p et n₂ = X.

S'il existait un élément a de ${\displaystyle \mathbb {Z} [X]}$ tel que a = a₁ mod n₁ et a = a₂ mod n₂, alors a serait un polynôme dont les coefficients sont multiples de p, mais qui serait aussi égal à 1 + (un multiple de X) ; cela ne se peut.

Le théorème des restes chinois s'étend de plusieurs façons aux corps munis d'un certain nombre de valuations indépendantes[10] - [11], tels que les anneaux factoriels (et a fortiori principaux), les anneaux de Dedekind etc. On le trouve alors sous le nom de « théorème d'approximation faible (en) » :

Soient v₁, v₂, ... v_n des valuations discrètes indépendantes d'un corps K , a₁, a₂, ... a_n des éléments de K, et k₁, k₂, ... , k_n des entiers relatifs. Alors il existe x ∈ K tel que v_i(x - a_i) = k_i pour tout i.

Le théorème reste vrai pour les valuations non discrètes, en remplaçant les k_i par des éléments du groupe des valeurs des v_i[10].

Le théorème ne suppose pas que les a_i soient éléments d'un anneau, ni que les k_i soient positifs. Par contre, même si les valuations sont issues d'un anneau (intègre) A, x ne peut être supposé élément de A.

Voyons ce que le théorème signifie pour les rationnels en général lorsque les k_i sont positifs, les valuations en jeu étant les valuations p adiques. Si q dénote un nombre rationnel, convenons ici, par homologie avec le cas entier, que q est multiple d'un entier n si le numérateur de q l'est, et si le dénominateur de q est premier avec n. Convenons encore de noter q₁ = q₂ mod n si q₁-q₂ est multiple de n (on peut facilement vérifier que les principes de base des congruences fonctionnent encore pour cette dȩfinition étendue, à quelques adaptations près).

Le théorème d'approximation faible implique[12] alors que si n₁, n₂, ... n_r sont r entiers premiers deux à deux, et q₁, q₂, ... q_r sont r rationels, alors il existe un rationnel q tel que q = q_i mod n_i pour tout i (ce qui est loin de se déduire trivialement du théorème des restes chinois[13]).

On va maintenant faire voir que ce théorème implique le théorème des restes chinois dans ${\displaystyle \mathbb {Z} }$, et même dans les anneaux principaux. En fait, il est même un peu plus général, car il fournit un élément x de valuation p_i-adique exactement égale aux k_i.

Supposons donc que A soit un anneau principal, de corps de fractions K. Avec les notations du début de l'article, si les n_i sont décomposés en produit de puissances de facteurs premiers p_ij^c_i,j, on voit facilement, en répétant éventuellement les a_i correspondants, qu'il suffit de supposer que n_i est une puissance d'un certain élément premier p_i, disons p_i^c_i.

En notant v_i les valuations p_i-adiques correspondantes, le théorème d'approximation faible dit qu'il existe un élément x de K tel que v_i(x - a_i) = c_i pour tout i. Notons x = r/s, où r et s sont des éléments de A premiers entre eux. On a donc

${\displaystyle {r \over s}-a_{i}=p_{i}^{c_{i}}q,\ q\in K,}$

les numérateurs et dénominateurs de q n'étant pas multiples de p_i. Multiplions cette équation par s, puis regardons la modulo p_i^c_i :

${\displaystyle sa_{i}=r\ {\rm {mod}}\ p_{i}^{c_{i}}.}$

Cela implique que s n'est pas multiple de p_i pour tout i, puisque r est premier avec s. Il existe donc t dans A tel que ${\displaystyle st=1\ {\rm {mod}}\ p_{1}^{c_{1}}\cdots p_{n}^{c_{n}}}$. En multipliant la congruence précédente par t, on obtient ${\displaystyle a_{i}=rt\ {\rm {mod}}\ p_{i}^{c_{i}}}$ pour tout i; donc rt satisfait aux conditions du théorème des restes chinois.

Observons pour finir que le théorème d'approximation faible n'est pas englobé par le théorème chinois dans les anneaux généraux, exposé dans la section suivante, car les idéaux premiers associés aux valuations ne réalisent pas nécessairement la condition de Bezout; un exemple simple est l'anneau factoriel ${\displaystyle \mathbb {Z} [X]}$, où l'on a les ideaux premiers ${\displaystyle <p>}$ et ${\displaystyle <X>}$, p un nombre premier quelconque, mais ${\displaystyle <p>+<X>\not =\mathbb {Z} [X]}$.

Si R est un anneau et I₁, …, I_k des idéaux bilatères de R deux à deux premiers entre eux (ce qui signifie que I_i + I_j = R lorsque i ≠ j), on démontre (par récurrence sur k)[14] que le morphisme

est un isomorphisme et que l'idéal intersection de ces idéaux est égal à la somme de tous leurs produits dans n'importe quel ordre :

${\displaystyle I_{1}\cap \cdots \cap I_{k}=\sum _{\sigma \in {\mathfrak {S}}_{k}}I_{\sigma (1)}\cdots I_{\sigma (k)}.}$

Si l'anneau est commutatif, tous ces produits sont égaux et l'intersection des I_i est simplement égale à leur produit. Mais s'il ne l'est pas, pour deux idéaux bilatères I et J premiers entre eux, en général[15] ${\displaystyle I\cap J\neq IJ}$, et l'on a seulement ${\displaystyle I\cap J=IJ+JI}$, d'où l'expression ci-dessus, avec une somme indexée par le groupe symétrique.

Si R est un anneau commutatif général, rien n'autorise à supposer que les idéaux sont co-premiers, même si R est intègre et que ces idéaux sont premiers. Cependant, on peut se demander si le théorème chinois généralisé (c.-à-d. qui ne suppose pas les n_i premiers entre eux, mais impose des conditions sur les a_i) aurait lieu.

C'est justement le cas des anneaux de Prüfer (en) et en réalité, cette propriété les caractérise. Plus précisément[16] - [17], pour qu'un anneau commutatif intègre soit de Prüfer, il faut et il suffit qu'un système de congruences ${\displaystyle x=x_{i}{\ {\rm {mod\ }}}I_{i}}$ admette des solutions dès que ${\displaystyle x_{i}\equiv x_{j}{\rm {\ mod\ }}(I_{i}+I_{j}).}$

Évidemment, si les idéaux I_i sont co-premiers, l'idéal I_i + I_j est R tout entier, donc la condition sur x_i et x_j est toujours vérifiée, et le système de congruence a une solution x. On retrouve bien le théorème chinois, tel qu'exposé au début de cette section.

On a vu qu'une des applications majeures du théorème des restes chinois résidait dans le fait que la résolution d'une congruence modulo un nombre m, produit de deux nombres m₁ et m₂, se réduisait à la résolution de cette même congruence modulo m₁ et m₂, lorsque m₁ et m₂ sont premiers entre eux. Typiquement, les m_i sont des puissances de nombres premiers, le théorème chinois étant poussé le plus loin possible. Cela simplifie déjà considérablement les problèmes théoriques et pratiques, mais comment réduire la question plus encore ? La technique suivante est déjà utilisée par Gauss dans les Disquisitiones arithmeticae. Pratiquée avec habileté, le plus souvent par le biais d'une descente infinie, elle permet une analyse fine des cas où les nombres m₁ et m₂ ne sont pas premiers entre eux, et de ramener finalement la question aux moduli premiers.

Soit ${\displaystyle P(x_{1},x_{2},\ldots x_{n})\equiv 0\mod m}$ une congruence, où ${\displaystyle P}$ est un polynôme de n variables, et m est le produit de m₁ et m₂, non nécessairement premiers entre eux. La résolution de cette congruence équivaut à la résolution successive de ${\displaystyle P(x'_{1},x'_{2},\ldots ,x'_{n})\equiv 0\mod m_{1}}$ puis de ${\displaystyle Q(x''_{1},x''_{2},\ldots ,x''_{n})\equiv 0\mod m_{2}}$ où le polynôme Q à coefficients entiers est égal à

${\displaystyle Q(X_{1},\ldots ,X_{n})={1 \over m_{1}}P(m_{1}X_{1}+x'_{1},\ldots ,m_{1}X_{n}+x'_{n})}$.

L'ensemble des solutions est alors ${\displaystyle \{(x_{i})=(x'_{i}+m_{1}x''_{i}),\ (x'_{i})\in S_{1},\ (x''_{i})\in S_{2}\},}$ où ${\displaystyle S_{1}}$ et ${\displaystyle S_{2}}$ sont les ensembles de solutions des congruences ci-dessus resp.

Observons encore que le théorème des restes chinois peut être vu comme un corollaire de ce lemme, en réduisant la question par induction au cas de deux facteurs ${\displaystyle m_{1}:=n_{1}}$ et ${\displaystyle m_{2}:=n_{2}}$, et en appliquant la méthode précédente au polynôme ${\displaystyle P(X)=n_{2}(X-a_{1})+n_{1}(X-a_{2})}$ (avec les notations du début de l'article).

• Théorème de Bachet-Bézout
• Système couvrant

• Michel Demazure, Cours d'algèbre. Primalité. Divisibilité. Codes., Cassini, coll. « Nouvelle bibliothèque mathématique », 1997 (ISBN 978-2842250003)

• Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes : Fondations pour l'informatique, Paris, Vuibert, 2003, 2^e éd., xiv+688 (ISBN 978-2-7117-4824-2)

• (en) Chinese Remainder Theorem sur cut-the-knot