Théorème des restes chinois (Chinese remainder theorem)

En mathématiques, le théorème chinois des restes postule que si les restes d'un entier n lorsqu'il est soumis à la division euclidienne par plusieurs entiers sont connus, alors le reste de n lorsqu'il est divisé par le produit de ces entiers peut être déterminé de manière unique, à condition que les diviseurs soient premiers par paires (ce qui signifie qu'aucun diviseur ne partage un facteur commun autre que 1).

Le théorème est également appelé théorème de Sunzi. Les deux désignations reconnaissent sa première formulation documentée, apparue dans Sunzi Suanjing, un manuscrit chinois composé entre le IIIe et le Ve siècle de notre ère. Cette déclaration initiale a été présentée comme un exemple illustratif spécifique :

Par exemple, si le reste de n divisé par 3 est 2, le reste de n divisé par 5 est 3 et le reste de n divisé par 7 est 2, alors, sans données supplémentaires, il est possible de déterminer le reste de n divisé par 105 (le produit de 3, 5 et 7), quelle que soit la valeur spécifique de n. Dans ce cas particulier, le reste est 23. De plus, ce reste représente la seule valeur entière positive pour n inférieure à 105.

Le théorème du reste chinois est largement appliqué dans les calculs impliquant de grands entiers, car il permet la décomposition d'un calcul avec un résultat connu lié en plusieurs calculs analogues impliquant des entiers plus petits.

Le théorème du reste chinois, lorsqu'il est exprimé à l'aide de congruences, est vrai. dans chaque domaine idéal principal. Ses principes ont été étendus pour englober tout cercle arbitraire, grâce à une formulation qui intègre des idéaux bifaces.

Historique

La première formulation documentée de ce problème se trouve dans le texte du Ve siècle Sunzi Suanjing, rédigé par le mathématicien chinois Sunzi :

Il y a certaines choses dont le numéro est inconnu. Si on les compte par trois, il nous en reste deux ; par cinq, il nous en reste trois ; et par sept, il en reste deux. Combien y a-t-il de choses ?

La contribution de Sunzi ne correspond pas aux définitions contemporaines d'un théorème, car elle présente simplement un problème spécifique sans détailler sa solution, sans fournir de preuve générale ou sans décrire un algorithme universel. Un algorithme de solution à ce problème a ensuite été détaillé par Aryabhata (VIe siècle). Des cas particuliers du théorème des restes chinois ont également été reconnus par Brahmagupta (7e siècle) et documentés dans le Liber Abaci de Fibonacci (1202). Le théorème a ensuite été largement généralisé avec une solution complète appelée Da-yan-shu (大衍術) dans le 1247 Traité mathématique en neuf sections de Qin Jiushao. Cet ouvrage a été traduit en anglais au début du XIXe siècle par le missionnaire britannique Alexander Wylie.

Le concept de congruences a été initialement formalisé et utilisé par Carl Friedrich Gauss dans ses Disquisitiones Arithmeticae de 1801. Gauss illustre le théorème des restes chinois à travers un problème calendaire, plus précisément, « pour trouver les années qui ont un certain nombre de périodes par rapport au cycle solaire et lunaire et à l'indiction romaine ». Gauss a présenté une procédure de solution à ce problème qui, bien qu'utilisée précédemment par Leonhard Euler, était en fait une méthodologie ancienne récurrente tout au long de l'histoire.

Déclaration

Considérez les entiers n§23§, ..., n_k, chacun dépassant 1, qui sont communément appelés modules ou diviseurs. Soit N le produit de ces valeurs n_i.

Le théorème des restes chinois stipule que, à condition que les n_i soient premiers entre eux par paires, et si a§89§, ..., a_k sont des entiers satisfaisant la condition 0 ≤ a_i < n_i pour chaque i, alors un entier unique x existe tel que 0 ≤ x < N, et pour chaque i, le reste de la division euclidienne de x par n_i est a_i.

Dans le langage des congruences, cela peut être reformulé comme suit : Si le ${\displaystyle n_{i}}$ sont premiers par paires, et si a§2425§, ..., a_k représentent des entiers arbitraires, alors le système

24§ ( mod n §4041§ ) ⋮ x ≡ un k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}

Une solution existe, et deux solutions distinctes, telles que x§23§ et x§6_{7§, sont congruentes modulo N, ce qui signifie que x§1314§ ≡ x§1718§ (mod N ).}

Dans le domaine de l'algèbre abstraite, ce théorème est fréquemment reformulé comme suit : si les entiers n_i sont premiers par paires, alors la cartographie

x mod N ↦<!-- ↦ --> ( x mod n §3738§ , … , x mod n k ) {\displaystyle x{\bmod {N}}\;\mapsto \;(x{\bmod {n}}_{1},\,\ldots ,\,x{\bmod {n}}_{k})}

établit un isomorphisme en anneau.

Z / N Z ≅<!-- ≅ --> Z / n §3536§ Z × ⋯ × Z / n k Z {\displaystyle \mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z} }

Le théorème chinois des restes établit un isomorphisme entre l'anneau des entiers modulo N et le produit direct des anneaux des entiers modulo n_i. Par conséquent, une séquence d'opérations arithmétiques au sein de ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ peut être effectué en exécutant les mêmes calculs indépendamment dans chaque ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$, puis obtention du résultat final en appliquant l'isomorphisme inverse. Cette approche peut considérablement accélérer les calculs, en particulier lorsque N et le nombre d'opérations sont importants. Cette technique, connue sous le nom de calcul multimodulaire, est largement appliquée en algèbre linéaire impliquant des nombres entiers ou des nombres rationnels.

En termes combinatoires, le théorème peut être reformulé pour affirmer que les progressions arithmétiques infinies d'entiers constituent une famille Helly.

Preuve

L'existence et le caractère unique de la solution peuvent être démontrés de manière indépendante. Néanmoins, la première preuve d'existence, présentée par la suite, repose sur cette unicité.

Unicité

Supposons que x et y satisfassent à toutes les congruences données. Puisque x et y donnent des restes identiques lorsqu'ils sont divisés par chaque n_i, leur différence, x − y, doit être un multiple de chaque n_i. Étant donné que les n_i sont premiers entre eux par paire, leur produit N divise également x − y, ce qui implique que x et y sont congrus modulo N. Si x et y sont limités à être non négatifs et strictement inférieurs à N (comme spécifié dans la formulation initiale du théorème), alors leur différence ne peut être qu'un multiple de N si et seulement si x = y.

Existence (preuve initiale)

La cartographie

x mod N ↦<!-- ↦ --> ( x mod n §3233§ , … , x mod n k ) {\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})}

Ce mappage transforme les classes de congruence modulo N en séquences de classes de congruence modulo n_i. La preuve d'unicité établit l'injectivité de cette carte. Puisque le domaine et le codomaine possèdent un nombre égal d'éléments, la carte est également surjective, démontrant ainsi l'existence d'une solution.

Bien que simple, cette preuve n'offre aucune méthode directe pour calculer une solution. De plus, il manque de généralisabilité aux contextes où la preuve ultérieure est applicable.

Existence (preuve constructive)

L'existence de x peut être démontrée par une construction explicite. Cette construction comporte deux étapes principales : résoudre dans un premier temps le problème pour deux modules, puis étendre cette solution au cas général via l'induction sur le nombre de modules.

Cas à deux modules

L'objectif est de résoudre le système suivant :

Le système de congruences est défini comme : 24§ ( mod n §4041§ ) x ≡ a §64 ( mod n §81 ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}} .

Dans ce contexte, n §1011§ {\displaystyle n_{1}} et ${\displaystyle n_{2}>$ sont stipulés comme étant des entiers premiers entre eux.

Selon L'identité de Bézout, il existe deux entiers, spécifiquement m §1011§ {\displaystyle m_{1}} et ${\displaystyle m_{2}>$, qui satisfont à la condition suivante :

m §1011§ n §1819§ + m §2829§ n §3637§ = 1. {\displaystyle m_{1}n_{1}+m_{2}n_{2}=1.}

Ces entiers, m §1011§ {\displaystyle m_{1}} et ${\displaystyle m_{2}>$, sont dérivables grâce à l'application de l'algorithme euclidien étendu.

A une solution particulière s'exprime par conséquent comme :

x = a §1415§ m §2223§ n §3031§ + a §4041§ m §4849§ n §5657§ . {\displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}

Cette affirmation est étayée par ce qui suit :

23§ m §30 n §38 + a §48 m §5657§ n §6465§ = a §8283§ ( §8889§ − m §9798§ n §105106§ ) + a §117 m §125126§ n §133134§ = a §151152§ + ( a §163 − a §174175§ ) m §184185§ n §192193§ , {\displaystyle {\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}}

This implies that x ≡<!-- ≡ --> a §1516§ ( mod n §3233§ ) . {\displaystyle x\equiv a_{1}{\pmod {n_{1}}}.} A similar proof establishes the second congruence, achieved by interchanging the subscripts 1 and 2.

Cas général

Considérons une séquence d'équations de congruence :

24§ ( mod n §4041§ ) ⋮ x ≡ un k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}

Les modules ${\displaystyle n_{i}}$ sont premiers entre eux par paire. Une solution, notée un §3233§ , §3637§ {\displaystyle a_{1,2}> , car les deux équations initiales peuvent être dérivées en utilisant la méthodologie décrite dans la section précédente. L'ensemble des solutions de ces deux équations initiales correspond à l'ensemble complet des solutions de l'équation suivante :

x ≡<!-- ≡ --> un §1516§ , §1920§ ( mod n §3637§ n §4445§ ) . {\displaystyle x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.}

Étant donné que les modules restants ${\displaystyle n_{i}}$ sont premiers avec le produit n §3233§ n §4041§ , {\displaystyle n_{1}n_{2},} cela transforme efficacement le problème d'origine, qui implique k équations, en un problème analogue comprenant k −<!-- − --> §6768§ {\displaystyle k-1} équations. Grâce à l'application itérative de ce processus, les solutions au problème initial sont finalement obtenues.

Existence : Construction directe

Lors de la construction d'une solution, une approche inductive basée sur le nombre de modules n'est pas strictement requise. Néanmoins, cette méthode de construction directe implique généralement des calculs approfondis impliquant de grands nombres, ce qui diminue son efficacité et sa prévalence. Il est à noter que l'interpolation de Lagrange représente un exemple spécifique de cette construction, adaptée aux polynômes plutôt qu'aux entiers.

Laissez ${\displaystyle N_{i}=N/n_{i}}$ représentent le produit de tous les modules sauf un. Étant donné que la ${\displaystyle n_{i}}$ sont premiers par paires, il s'ensuit que ${\displaystyle N_{i}}$ et ${\displaystyle n_{i}}$ sont également premier. Par conséquent, l'identité de Bézout est applicable, garantissant l'existence d'entiers ${\displaystyle M_{i}}$ et ${\displaystyle m_{i}}$ satisfaisant la condition suivante :

${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}$

Une solution pour ce système de congruences est définie comme :

x = ∑<!-- ∑ --> i = §1920§ k a i M i N je . {\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}

En effet, depuis ${\displaystyle N_{j}}$ constitue un multiple de ${\displaystyle n_{i}}$ quand ${\displaystyle i\neq j,>$ il s'ensuit que :

x ≡<!-- ≡ --> a i M i N i ≡<!-- ≡ --> a i ( §4849§ − m i n i ) ≡ a i ( mod n i ) , {\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}

Cette congruence s'applique à chaque ${\displaystyle i.}$.

Calcul

Considérons un système de congruences :

24§ ( mod n §3940§ ) ⋮ x ≡ a k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}}

où le ${\displaystyle n_{i}}$ sont premiers entre eux. Soit N=n§3637§n§4445§⋯nk.{\displaystyle N=n_{1}n_{2}\cdots n_{k}.} Cette section détaille plusieurs méthodes de calcul pour déterminer la solution unique pour ${\displaystyle x}$, contraint par la condition 92§≤x<N,{\displaystyle 0\leq x<>. Ces méthodologies seront ensuite démontrées à l'aide d'un exemple spécifique.

20§(mod§3031§)x≡§4849§(mod§5960§)x≡§7878§(mod§8889§).{\displaystyle {\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}.\end{aligned}}}

Cette section présente plusieurs méthodologies de calcul. Les deux approches initiales conviennent aux exemples à petite échelle mais démontrent une inefficacité significative lorsque le produit n§1011§⋯nk{\displaystyle n_{1}\cdots n_{k}} devient substantiel. À l'inverse, la troisième méthode, qui exploite la preuve d'existence constructive détaillée dans § Existence (preuve constructive), s'avère la plus avantageuse pour les gros produits ou pour une implémentation dans des algorithmes informatiques.

Recherche systématique

Vérifier si une valeur x constitue une solution est simple : il suffit de calculer le reste de la division euclidienne de x par chaque n_i. Par conséquent, pour identifier la solution, il suffit d'examiner séquentiellement des nombres entiers allant de §1213§ à N jusqu'à ce que la bonne solution soit découverte.

Malgré sa simplicité, cette méthode démontre une inefficacité significative. Dans l'exemple spécifique fourni, l'identification de la solution, qui est 39, nécessite l'examen de 40 entiers, dont §23§. Cela constitue un algorithme de temps exponentiel car la taille d'entrée, sans tenir compte d'un facteur constant, correspond au nombre de chiffres dans N, et le nombre opérationnel moyen se rapproche de l'ordre de N.

Par conséquent, cette approche trouve des applications peu fréquentes dans les calculs manuels et les processus informatiques.

Recherche basée sur le tamisage

Le tamisage peut considérablement accélérer le processus de recherche d'une solution. Pour cette technique, nous supposons, sans perte de généralité, que 7§ ≤ a i < n i {\displaystyle 0\leq a_{i} . (Sinon, il suffirait de remplacer chaque ${\displaystyle a_{i}}$ avec le reste obtenu de sa division par ${\displaystyle n_{i}}$). Cette condition indique que la solution fait partie de la progression arithmétique suivante :

a §1011§ , a §2021§ + n §3031§ , a §4041§ + §4647§ n §5253§ , … {\displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots }

En évaluant ces nombres modulo ${\displaystyle n_{2},}$, une solution ${\displaystyle x_{2}}$ pour les deux congruences initiales est finalement identifié. Par la suite, la solution fait partie de la progression arithmétique suivante :

x §1011§ , x §2021§ + n §3031§ n §3839§ , x §4849§ + §5455§ n §6061§ n §6869§ , … {\displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots }

La solution est finalement obtenue en testant les valeurs de ces nombres modulo ${\displaystyle n_{3},>$ et en procédant de manière itérative jusqu'à ce que tout soit terminé. les modules ont été évalués.

Cette méthode démontre une efficacité accrue lorsque les modules sont classés par ordre décroissant, en particulier si 11§ > n §20 . {\displaystyle n_{1}>n_{2}>\cdots >n_{k}.} L'application de ceci à l'exemple donné donne les étapes de calcul suivantes. Initialement, les nombres congrus à 4 modulo 5 (le plus grand module) sont examinés, dont 4, 9 = 4 + 5 et 14 = 9 + 5. Pour chacun d'eux, le reste modulo 4 (le deuxième plus grand module) est calculé jusqu'à obtenir un nombre congru à 3 modulo 4. Par la suite, le processus consiste à ajouter 20 = 5 × 4 de manière incrémentielle et à calculer uniquement les restes modulo 3. Cette procédure aboutit à :

4 modulo 4 donne 0. Continuez.

4 + 5 = 9, soit 1 modulo 4. Continuez.

9 + 5 = 14, soit 2 modulo 4. Continuez.

14 + 5 = 19, soit 3 modulo 4. Ce résultat est acceptable ; le processus continue en évaluant les restes modulo 3 et en ajoutant 5 × 4 = 20 à chaque étape suivante.

19 modulo 3 donne 1. Continuez.

19 + 20 = 39, soit 0 modulo 3. Cela représente la solution finale.

Cette approche est efficace pour les calculs manuels impliquant un produit de modules modeste. Néanmoins, ses performances sont nettement en retard par rapport aux méthodes alternatives lorsqu’il s’agit de produits de modules exceptionnellement grands. Bien qu'elle offre une amélioration substantielle de la vitesse par rapport aux techniques de recherche systématique, cette méthode présente une complexité temporelle exponentielle, la rendant impropre à la mise en œuvre informatique.

Application de la construction d'existence

La preuve d'existence constructive démontre que pour deux modules, une solution peut être dérivée en calculant les coefficients de Bézout de ces modules, suivis d'une séquence de multiplications, d'additions et de réductions modulo n §1011§ n §1819§ {\displaystyle n_{1}n_{2}} pour contraindre le résultat dans l'intervalle ( §3839§ , n §4647§ n §5455§ − §6162§ ) {\displaystyle (0,n_{1}n_{2}-1)} . Étant donné que les coefficients de Bézout sont calculables via l'algorithme euclidien étendu, l'ensemble du processus de calcul présente une complexité temporelle quadratique maximale de O ( ( s §8990§ + s §99100§ ) §107108§ ) , {\displaystyle O((s_{1}+s_{2})^{2}),} où ${\displaystyle s_{i}}$ représente le nombre de chiffres dans ${\displaystyle n_{i}.}$

Lorsqu'il s'agit de plus de deux modules, la méthode établie pour deux modules permet de remplacer n'importe quelle paire de congruences par une congruence singulière, dont le module est le produit des deux d'origine. L'application répétée de cette procédure donne finalement une solution avec une complexité de calcul quadratique par rapport au nombre de chiffres dans le produit de tous les modules. Notamment, cette complexité temporelle quadratique reste invariante quelle que soit la séquence dans laquelle les modules sont combinés. Une approche courante consiste à combiner initialement les deux premiers modules, puis à fusionner le module résultant avec le suivant, et à poursuivre ce processus itératif. Bien que cette stratégie offre une mise en œuvre simple, elle nécessite des calculs approfondis impliquant des valeurs numériques de plus en plus grandes.

Une stratégie alternative consiste à segmenter les modules en paires avec des produits d'ampleurs approximativement équivalentes, puis à appliquer simultanément la méthode des deux modules à chaque paire, puis à répéter le processus avec un ensemble réduit de modules, dont le nombre est environ réduit de moitié. Cette approche facilite considérablement la parallélisation de l’algorithme. De plus, lorsque des algorithmes rapides (en particulier ceux fonctionnant en temps quasi-linéaire) sont utilisés pour les opérations fondamentales, cette méthode permet d'effectuer l'ensemble du calcul en temps quasi-linéaire.

Pour le présent exemple, qui implique seulement trois modules, les deux stratégies susmentionnées convergent et procèdent de manière identique.

L'identité de Bézout pour les entiers 3 et 4 s'exprime comme suit :

§67§ × §1112§ + ( − §2021§ ) × §2728§ = 1. {\displaystyle 1\times 4+(-1)\times 3=1.}

La substitution de ces valeurs dans la formule précédemment établie pour démontrer l'existence donne :

§67§ × §1112§ × §1617§ + §2021§ × ( − §3031§ ) × §3738§ = − §4445§ {\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}

Ce résultat représente une solution pour les deux congruences initiales ; toutes les autres solutions sont dérivées en ajoutant n'importe quel multiple de 3 × 4 = 12 à −9. Bien que n'importe laquelle de ces solutions puisse être utilisée, la solution 3 = −9 +12 est préférée en raison de sa valeur absolue plus petite, ce qui simplifie probablement les calculs ultérieurs.

L'identité de Bézout pour les entiers 5 et 3 × 4 = 12 est donnée par :

${\displaystyle 5\times 5+(-2)\times 12=1.}$

Réappliquer la formule identique donne une solution au problème :

${\displaystyle 5\times 5\times 3+12\times (-2)\times 4=-21.}$

Des solutions supplémentaires sont dérivées en incorporant n'importe quel multiple de 3 × 4 × 5 = 60, la plus petite solution positive étant −21 + 60 = 39.

Représentation en tant que système diophantien linéaire

Le système de congruences abordé par le théorème des restes chinois peut être reformulé comme un système d'équations diophantiennes linéaires :

23§ + x §3233§ n §4041§ ⋮ x = un k + x k n k , {\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}

Ici, les entiers inconnus sont ${\displaystyle x}$ et les variables ${\displaystyle x_{i}.}$ Par conséquent, toute méthodologie générale pour résoudre de tels systèmes, y compris la réduction de la matrice du système à la forme normale de Smith ou à la forme normale d'Hermite, peut être appliquée pour déterminer la solution du théorème chinois des restes. Néanmoins, conformément au résultat typique de l'application d'un algorithme général à un problème spécialisé, cette stratégie s'avère moins efficace que l'approche détaillée dans la section précédente, qui s'appuie directement sur l'identité de Bézout.

Sur les principaux domaines idéaux

Le théorème des restes chinois, tel que présenté dans la section § Énoncé, a été articulé sous trois formes distinctes : en utilisant des restes, des congruences et un isomorphisme en anneau. Généralement, la formulation impliquant des restes est inapplicable aux principaux domaines idéaux, étant donné que les restes manquent de définition au sein de ces anneaux. Néanmoins, les deux autres versions restent valables au sein d'un domaine idéal principal R ; cela nécessite de remplacer "entier" par "élément du domaine" et ${\displaystyle \mathbb {Z} }$ avec R. Ces deux versions du théorème sont vraies dans ce contexte car leurs preuves, à l'exception de la preuve d'existence initiale, dérivent du lemme d'Euclide et de l'identité de Bézout, qui sont tous deux valables dans tous les domaines principaux.

En général, cependant, le théorème fonctionne uniquement comme un théorème d'existence, n'offrant aucune méthode explicite pour calculer la solution à moins qu'un algorithme pour déterminer les coefficients de l'identité de Bézout ne soit disponible.

Sur les anneaux polynomiaux univariés et les domaines euclidiens

L'énoncé basé sur les restes présenté dans le § Énoncé du théorème ne peut pas être universellement généralisé à tous les principaux domaines idéaux ; cependant, son extension aux domaines euclidiens est simple.

Le théorème des restes chinois pour les polynômes peut être formellement énoncé comme suit : Soit

La construction de la solution peut être réalisée grâce à des méthodes détaillées dans § Existence (preuve constructive) ou § Existence (preuve directe). Néanmoins, l'approche de preuve directe peut être rationalisée en employant la décomposition en fractions partielles plutôt que l'algorithme euclidien étendu.

Par conséquent, l'objectif est de déterminer un polynôme ${\displaystyle P(X)>$ qui satisfait les congruences suivantes :

P ( X ) ≡<!-- ≡ --> A i ( X ) ( mod P i ( X ) ) , {\displaystyle P(X)\equiv A_i(X){\pmod {P_i(X)}},}

pour i = §1011§ , … , k . {\displaystyle i=1,\ldots ,k.}

Considérez les polynômes suivants :

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}.\end{aligned}}}$

La décomposition en fractions partielles de {\displaystyle 1/Q(X)} donnek polynômes, en particulier {\displaystyle S_i(X)}, où le degré de chaque polynôme satisfait

{\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^k{\frac {S_i(X)}{P_i(X)}}.}

Par conséquent,

{\displaystyle 1=\sum _{i=1}^{k}S_i(X)Q_i(X)}.

Par conséquent, une solution au système de congruence simultanée est représentée par le polynôme :

{\displaystyle \sum _{i=1}^{k}A_i(X)S_i(X)Q_i(X)}.

En effet, nous observons :

∑<!-- ∑ --> i = §1516§ k A i ( X ) S i ( X ) Q i ( X ) = A i ( X ) + ∑ j = §9293§ k ( A j ( X ) − A i ( X ) ) S j ( X ) Q j ( X ) ≡ A i ( X ) ( mod P i ( X ) ) , {\displaystyle \sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+\sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},}

pour §67§ ≤ i ≤ k . {\displaystyle 1\leq i\leq k.>

Cette solution peut posséder un degré dépassant D=∑<!-- ∑ -->i=§1920§kdi.{\displaystyle D=\sum _{i=1}^{k}d_{i}.}. La solution unique, ayant un diplôme inférieur à ${\displaystyle D}$${\displaystyle B_{i}(X)>$${\displaystyle A_{i}(X)S_{i}(X)}$${\displaystyle P_{i}(X).}$

P(X)=∑<!-- ∑ -->i=§2526§kBi(X)Qi(X).{\displaystyle P(X)=\sum _{i=1}^{k}B_{i}(X)Q_{i}(X).}

Interpolation de Lagrange

L'interpolation de Lagrange représente une instance spécifique du théorème chinois des restes pour les polynômes. Pour cette application, considérons k polynômes moniques, chacun de degré un :

${\displaystyle P_{i}(X)=X-x_{i}.}$

Ces polynômes sont premiers par paire si toutes les valeurs xi{\displaystyle x_i} sont distincts. Selon le théorème du reste polynomial, le reste obtenu en divisant un polynôme ${\displaystyle P(X)}$ par ${\displaystyle P_{i}(X)>$ est ${\displaystyle P(x_{i})}$.

Laissez A §1011§ , … , A k {\displaystyle A_{1},\ldots ,A_{k}} représentent des constantes, qui sont des polynômes de degré 0, dans ${\displaystyle K.>$ L'interpolation de Lagrange et le théorème des restes chinois établissent l'existence d'un polynôme unique ${\displaystyle P(X),>$ avec un diplôme inférieur à ${\displaystyle k}$, tel que :

${\displaystyle P(x_{i})=A_{i},}$

pour chaque ${\displaystyle i.}$

Dans ce contexte spécifique, la formule d'interpolation de Lagrange correspond précisément au résultat dérivé de la construction susmentionnée de la solution. Pour élaborer, considérez :

34§ k ( X − x i ) Q i ( X ) = Q ( X ) X − x i . {\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}

La décomposition en fraction partielle de §89§ Q ( X ) {\displaystyle {\frac {1}{Q(X)}}} est le suivant :

§89§ Q ( X ) = ∑ i = §3334§ k §4344§ Q i ( x i ) ( X − x i ) . {\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}

Lorsque le membre de droite est réduit à un dénominateur commun, l'expression suivante est obtenue :

∑<!-- ∑ --> i = §1516§ k §2526§ Q i ( x i ) ( X − x i ) = §7273§ Q ( X ) ∑ i = §9596§ k Q i ( X ) Q i ( x i ) , {\displaystyle \sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},}

Le numérateur, étant un polynôme de degré inférieur à ${\displaystyle k,}$ est évalué à un. Cela se produit car il prend la valeur un pour ${\displaystyle k}$ valeurs distinctes de ${\displaystyle X.}$

L'application de la formule générale susmentionnée donne la formule d'interpolation de Lagrange :

P ( X ) = ∑<!-- ∑ --> i = §2526§ k A i Q i ( X ) Q i ( x i ) . {\displaystyle P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}

Interpolation Hermite

L'interpolation Hermite représente une application du théorème chinois des restes adaptée aux polynômes univariés, une méthode qui peut incorporer des modules de degrés arbitraires. Cela contraste avec l'interpolation de Lagrange, qui est limitée aux modules de degré un.

L'objectif de ce problème est de déterminer un polynôme du degré minimum réalisable, tel que le polynôme et ses dérivées initiales prennent des valeurs spécifiées à des points fixes désignés.

Pour définir cela plus précisément, laissez x§1011§,…,xk{\displaystyle x_{1},\ldots ,x_{k}} représente ${\displaystyle k}$ éléments du champ au sol ${\displaystyle K,>$i=§8182§,…,k,{\displaystyle i=1,\ldots ,k,> let ai,§116117§,ai,§130131§,…,ai,ri−§159160§{\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}} désignent les valeurs du premier ${\displaystyle r_{i}}$ dérivés du polynôme souhaité évalué à xi{\displaystyle x_i} (cela inclut la 0ème dérivée, qui est la la valeur du polynôme lui-même).L'objectif est de déterminer un polynôme${\displaystyle P(X)>$ tel que sa j-ième dérivée prenne la valeur ai,j{\displaystyle a_{i,j}} à xi,{\displaystyle x_i,> pour tous i=§300301§,…,k{\displaystyle i=1,\ldots ,k} et j=§329330§,…,rj.{\displaystyle j=0,\ldots ,r_{j}.}

Maintenant, considérons le polynôme

P je ( X ) = ∑<!-- ∑ --> j = §3132§ r je − §4647§ un je , j j ! ( X − x je ) j . {\displaystyle P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}

Cette expression représente le polynôme de Taylor d'ordre r je −<!-- − --> §1718§ {\displaystyle r_{i}-1} centré sur ${\displaystyle x_{i}}$, correspondant au polynôme inconnu ${\displaystyle P(X).}$ Par conséquent, la condition suivante doit être satisfaite :

${\displaystyle P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.}$

À l'inverse, tout polynôme ${\displaystyle P(X)>$ qui satisfait à ces ${\displaystyle k}$ les congruences seront spécifiquement vérifiées, pour tous je = §4849§ , … , k {\displaystyle i=1,\ldots,k}

P ( X ) = P je ( X ) + o ( X −<!-- − --> x je ) r je −<!-- − --> §6465§ {\displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}

Par conséquent, {\displaystyle P_i(X)} représente son polynôme d'ordre de Taylor{\displaystyle r_i-1} à{\displaystyle x_i}. Cela implique que{\displaystyle P(X)} résout le problème initial d'interpolation Hermite. Le théorème du reste chinois stipule l'existence d'un polynôme précisément avec un degré inférieur à la somme des{\displaystyle r_i,} qui satisfait ces{\displaystyle k} congruences.

Il existe plusieurs méthodologies pour calculer la solution {\displaystyle P(X).} Une approche implique la méthode décrite au début du § Sur les anneaux polynomiaux univariés et les domaines euclidiens. Alternativement, les constructions fournies dans § Existence (preuve constructive) ou § Existence (preuve directe) peuvent être utilisées.

Généralisation aux modules non-Coprime

Le théorème des restes chinois peut être généralisé pour englober les modules non premiers entre eux.

Considérez {\displaystyle n_1,\dots ,n_k} comme un ensemble de des entiers positifs, et{\displaystyle a_1,\dots ,a_k} comme un ensemble correspondant d'entiers. Le système de congruences simultanées

Considérez le système de congruences suivant : 24§ ( mod n §4041§ ) ⋮ x ≡ a k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}

Une solution à ce système existe si et seulement si, pour tous les indices distincts ${\displaystyle \gcd(n_{i},n_{j})>$ divise la différence ${\displaystyle a_{i}-a_{j}>$, où ${\displaystyle i\neq j.>$

Si cette condition est remplie, l'ensemble de solutions constitue une classe de congruence unique modulo N = lcm ( n §2021§ , … , n k ) . {\displaystyle N={\text{lcm}}(n_{1},\dots ,n_{k}).} Cela implique que deux solutions distinctes diffèrent d'un multiple de ${\displaystyle N}$, et en ajoutant un multiple de ${\displaystyle N}$ à une solution produira toujours une autre solution valide.

Pour illustrer ce concept pour un système impliquant deux congruences, considérons ${\displaystyle m,n>$ sous forme d'entiers positifs et ${\displaystyle a,b>$ sous forme d'entiers arbitraires. Définir ${\displaystyle g=\gcd(m,n)>$ comme plus grand diviseur commun et ${\displaystyle M=\operatorname {lcm} (m,n)}$ comme multiple le plus petit commun. Par la suite, considérons le système de congruences suivant :

${\displaystyle {\begin{aligned}x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}},\end{aligned}}>$

Le système possède une solution unique modulo ${\displaystyle M=mn/g}$ si la condition ${\displaystyle a\equiv b{\pmod {g}}}$ est satisfait ; sinon, aucune solution n'existe.

Utiliser l'identité de Bézout pour exprimer ${\displaystyle g=um+vn>$, une solution particulière peut être formulée comme :

${\displaystyle x={\frac {avn+bum}{g}}.}$

Cette expression donne une valeur entière car g est un diviseur à la fois de m et de n.

Généralisation aux anneaux arbitraires

Le théorème chinois des restes s'étend à n'importe quel anneau grâce à l'application d'idéaux premiers entre eux, également appelés idéaux comaximaux. Deux idéaux, I et J, sont définis comme premiers entre eux s'il existe des éléments ${\displaystyle i\in I}$ et ${\displaystyle j\in J}$ de telle sorte que leur somme soit égale à un : ${\displaystyle i+j=1.}$ Cette relation spécifique fonctionne de manière analogue à l'identité de Bézout au sein des preuves associées à cette généralisation, qui par ailleurs présentent une similitude substantielle. L'énoncé formel de cette généralisation est présenté ci-dessous.

Considérez I§34§, ..., I_k comme des idéaux à deux faces au sein d'un anneau ${\displaystyle R}$, et laissez I désigner leur carrefour. À condition que ces idéaux soient premiers entre eux par paire, l'isomorphisme suivant est valable :

37§ ) × ⋯ × ( R / I k ) x mod I ↦ ( x mod Je §103104§ , … , x mod I k ) , {\displaystyle {\begin{aligned}R/I&\to (R/I_{1})\times \cdots \times (R/I_{k})\\x{\bmod {I}}&\mapsto (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{aligned}}}

Une relation existe entre l'anneau de quotient ${\displaystyle R/I}$ et le produit direct des anneaux ${\displaystyle R/I_{i},>$.Dans ce contexte, "${\displaystyle x{\bmod {I}}}$" désigne l'image de l'élément ${\displaystyle x}$ dans l'anneau de quotient défini par l'idéal ${\displaystyle I.}$ De plus, si ${\displaystyle R}$ est commutatif, l'idéal l'intersection d'idéaux premiers entre eux par paire est équivalente à leur produit, exprimé comme suit :

Je=Je§1415§∩Je§2526§∩⋯∩Jek=I§5253§I§5960§⋯Ik,{\displaystyle I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},}

Cette égalité est valide si I_i et I_j sont premiers entre eux par paire pour tout i ≠ j.

Interprétation en termes d'idempotents

Laissez I§1011§,I§2021§,…,Jek{\displaystyle I_{1},I_{2},\dots ,I_{k}} désignent des idéaux bilatéraux premiers entre eux par paire de telle sorte que leur intersection soit l'idéal zéro : ⋂<!-- ⋂ -->i=§6263§kIi=§8081§,{\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}. Cela établit un mappage :

φ<!-- φ --> :R→<!-- → -->(R/I§2829§)×⋯×(R/Ik){\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}

Considérant l'isomorphisme susmentionné, fi=(§1819§,…,§2728§,…,§3637§){\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)} désigne l'élément dans (R/Je§6667§)×⋯×(R/Ik){\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})} où tous les composants sont §107108§ à l'exception du i-ème composant, qui est §111112§. De plus, définissez ei=φ<!-- φ -->−<!-- − -->§137138§(fi).{\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}

Les éléments ${\displaystyle e_{i}}$ constituent un ensemble d'idempotents centraux qui sont orthogonaux par paires. Plus précisément, cela implique que ${\displaystyle e_{i}^{2}=e_{i}}$ (idempotence) et eiej=ejei=§100101§{\displaystyle e_{i}e_{j}=e_{j}e_{i}=0} (orthogonalité) pour tous les i et j distincts. De plus, les relations suivantes sont valables : e§124125§+⋯+en=§145146§,{\textstyle e_{1}+\cdots +e_{n}=1,} et Ii=R(§177178§−ei).{\displaystyle I_{i}=R(1-e_{i}).}

En résumé, ce théorème des restes chinois généralisé établit une équivalence entre la spécification d'idémpotents bilatéraux premiers entre eux par paires avec une intersection nulle et l'identification d'idempotents orthogonaux centraux par paires dont la somme collective vaut 1.

Applications

Numérotation des séquences

Le théorème chinois des restes facilite la construction des numérotations de Gödel pour les séquences, un élément essentiel dans la preuve des théorèmes d'incomplétude de Gödel.

Transformation de Fourier rapide

L'algorithme FFT à facteur premier, également connu sous le nom d'algorithme de Good-Thomas, utilise le théorème des restes chinois pour simplifier le calcul d'une transformée de Fourier rapide de taille n §1011§ n §1819§ {\displaystyle n_{1}n_{2}> . Cette réduction transforme le problème en calcul de deux transformées de Fourier rapides de plus petites tailles, spécifiquement n §4041§ {\displaystyle n_{1}} et ${\displaystyle n_{2}>$, à condition que n §8485§ {\displaystyle n_{1}} et ${\displaystyle n_{2}>$ sont premiers entre eux.

Chiffrement

Le théorème du reste chinois est fréquemment utilisé dans la plupart des implémentations RSA, en particulier lors du processus de signature des certificats HTTPS et lors des opérations de décryptage.

De plus, le théorème du reste chinois trouve une application dans les schémas de partage de secrets. Il s'agit de répartir un ensemble d'actions au sein d'un groupe, permettant la récupération collective (mais non individuelle) d'un secret spécifique à partir de ces actions. Chaque part correspond à une congruence, et le secret lui-même est dérivé de la solution du système de congruences utilisant le théorème chinois des restes. Lorsqu'il est utilisé dans le partage de secrets, le théorème chinois du reste est souvent combiné avec des séquences entières spécifiques conçues pour garantir que le secret ne peut pas être reconstruit à partir d'un sous-ensemble de partages inférieur à une cardinalité prédéterminée.

Résolution d'ambiguïté de plage

Les techniques permettant de résoudre l'ambiguïté de portée dans les systèmes radar à moyenne fréquence de répétition d'impulsions peuvent être conceptualisées comme une application spécifique du théorème chinois du reste.

Décomposition des surjections de groupes abéliens finis

Pour une surjection donnée Z / n →<!-- → --> Z / m {\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m} entre les groupes abéliens finis, le reste chinois Le théorème fournit une méthode complète pour décrire de telles cartographies. Initialement, le théorème établit des isomorphismes.

44§ un §5354§ × ⋯ × Z / p n je un je Z / m ≅ Z / p m §137138§ b §147148§ × ⋯ × Z / p m j b j & \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}

Il est établi que { p m §1617§ , … , p m j } ⊆ { p n §5859§ , … , p n je } {\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}} .De plus, pour toute carte induite

${\displaystyle \mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}}$

dérivé de la surjection initiale, on observe que ${\displaystyle a_{k}\geq b_{l}}$ et ${\displaystyle p_{n_{k}}=p_{m_{l}},}$. En effet, pour toute paire de nombres premiers ${\displaystyle p,q}$, les seules surjections non nulles

${\displaystyle \mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}}$

sont définissables exclusivement si ${\displaystyle p=q}$ et ${\displaystyle a\geq b}$.

Ces observations sont cruciales pour la construction de l'anneau d'entiers profinis, qui est défini comme une limite inverse de toutes ces applications.

Théorème de Dedekind

Le théorème de Dedekind aborde l'indépendance linéaire des caractères. Soit M un monoïde et k représente un domaine intégral, qui est considéré comme un monoïde sous son opération de multiplication inhérente sur k. Par conséquent, toute collection finie ( f_i )_i∈I d'homomorphismes monoïdes distincts  f_i : M → k présente une indépendance linéaire. Cela implique que toute famille (α_i)_i∈I d'éléments α_i ∈ k qui satisfait la condition suivante :

∑<!-- ∑ --> je ∈<!-- ∈ --> Je α<!-- α --> je f je = §3940§ {\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}

doit correspondre précisément à la famille (0)_i∈I.

Preuve. Dans un premier temps, supposons que k constitue un corps ; sinon, le domaine intégral k peut être remplacé par son champ quotient sans modifier le résultat. Les homomorphismes monoïdes  f_i  : M → k peuvent être étendus linéairement aux homomorphismes k-algèbre F_i : k[M] → k, où k[M] désigne l'anneau monoïde de M sur k. Par conséquent, en raison de la linéarité, la condition

∑<!-- ∑ --> je ∈<!-- ∈ --> Je α<!-- α --> je f je = §3940§ , {\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}

rend ensuite

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

De plus, pour tout i, j ∈ I où i ≠ j, les deux k-applications linéaires F_i : k[M] → k et F_j  : k[M] → k ne sont pas mutuellement proportionnels. S'ils l'étaient, alors  f_i  et  f_j  présenteraient également une proportionnalité, et par conséquent seraient identiques, étant donné qu'en tant qu'homomorphismes monoïdes, ils remplissent la condition :  f_i (1) = 1 = f_j (1). Ce résultat contredit directement la prémisse initiale de leur distinction.

Par conséquent, les noyaux Ker F_i et Ker F_j sont manifestement distincts. Étant donné que k[M]/Ker F_i ≅ F_i (k[M]) = k forme un champ, il s'ensuit que Ker F_i constitue un idéal maximal de k[M] pour chaque i dans I. En raison de leur nature distincte et maximale, les idéaux Ker F_i et Ker F_j sont premiers entre eux chaque fois que i ≠ j. L'application du théorème des restes chinois (applicable aux anneaux généraux) établit alors l'isomorphisme suivant :

Le mappage ${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

Où,

Le terme ${\displaystyle K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.}$

Par conséquent, la carte est alors définie comme :

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

Le mappage est surjectif. Dans le contexte des isomorphismes k[M]/Ker F_i → F_i (k[M]) = k, l'application Φ est représentée par :

Par la suite,

∑<!-- ∑ --> je ∈<!-- ∈ --> Je α<!-- α --> je F je = §3940§ {\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}

rendements

∑<!-- ∑ --> je ∈<!-- ∈ --> Je α<!-- α --> je tu je = §3940§ {\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}

pour chaque vecteur (u_i)_i∈I dans l'image de la carte ψ. Étant donné que ψ est surjectif, il s'ensuit que

∑<!-- ∑ --> je ∈<!-- ∈ --> Je α<!-- α --> je tu je = §3940§ {\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}

pour n'importe quel vecteur

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

Par conséquent, le vecteur (α_i)_i∈I est égal au vecteur zéro (0)_i∈I. Q.E.D.

Système de couverture

• Système de couverture
• Principe de Hasse
• Système de numérotation des résidus

Remarques

Références

• Dauben, Joseph W. (2007), "Chapitre 3 : Mathématiques chinoises", dans Katz, Victor J. (éd.), Les mathématiques de l'Égypte, de la Mésopotamie, de la Chine, de l'Inde et de l'Islam : un livre source, Princeton University Press, pp. 187–384, ISBN 978-0-691-11485-9Dence, Joseph B. ; Dence, Thomas P. (1999), Éléments de la théorie des nombres, Academic Press, ISBN 9780122091308Duchet, Pierre (1995), "Hypergraphs", dans Graham, R. L. ; Grötschel, M. ; Lovász, L. (éd.), Handbook of Combinatorics, Vol. 1, 2, Amsterdam : Elsevier, pp. 381–432, MR 1373663
• Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae, traduit par Clarke, Arthur A. (deuxième édition corrigée), New York : Springer, ISBN 978-0-387-96254-2Irlande, Kenneth ; Rosen, Michael (1990), Une introduction classique à la théorie moderne des nombres (2e éd.), Springer-Verlag, ISBN 0-387-97329-XJones, Gareth A. ; Jones, J. Mary (1998). Théorie élémentaire des nombres. Londres ; New York : Springer.ISBN 3-540-76197-7.Kak, Subhash (1986), "Aspects informatiques de l'algorithme Aryabhata" (PDF), Indian Journal of History of Science, 21 (1) : 62–71Katz, Victor J. (1998), Une histoire des mathématiques / Une introduction (2e éd.), Addison Wesley Longman, ISBN 978-0-321-01618-8Libbrecht, Ulrich (1973), Les mathématiques chinoises au XIIIe siècle : le "Shu-shu Chiu-chang" de Ch'in Chiu-shao, Dover Publications Inc, ISBN 978-0-486-44619-6Ore, Øystein (1952), "Le théorème général des restes chinois", The American Mathematical Monthly, 59 (6) : 365–370, doi:10.2307/2306804, JSTOR 2306804, MR 0048481Ore, Oystein (1988) [1948], Théorie des nombres et son histoire, Dover, ISBN 978-0-486-65620-5Pisano, Leonardo (2002), Liber Abaci de Fibonacci, traduit par Sigler, Laurence E., Springer-Verlag, pp.402–403, ISBN 0-387-95419-8Rosen, Kenneth H. (1993), Théorie élémentaire des nombres et ses applications (3e éd.), Addison-Wesley, ISBN 978-0201-57889-8Sengupta, Ambar N. (2012), Représenter les groupes finis : une introduction semi-simple, Springer, ISBN 978-1-4614-1232-8Bourbaki, N. (1989), Algèbre I, Springer, ISBN 3-540-64243-9Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introduction aux algorithmes (deuxième éd.), MIT Press et McGraw-Hill, ISBN 0-262-03293-7.
  • Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introduction aux algorithmes (deuxième éd.), MIT Press et McGraw-Hill, ISBN 0-262-03293-7Ding, Cunsheng ; Pei, Dingyi ; Salomaa, Arto (1996), Théorème du reste chinois : applications en informatique, codage, cryptographie, World Scientific Publishing, pp. 1–213, ISBN 981-02-2827-9Hungerford, Thomas W. (1974), Algèbre, Textes d'études supérieures en mathématiques, Vol. 73, Springer-Verlag, p.131–132, ISBN 978-1-4612-6101-8Knuth, Donald (1997), L'art de la programmation informatique, vol. 2 : Algorithmes seminumériques (troisième éd.), Addison-Wesley, ISBN 0-201-89684-2"Théorème des restes chinois", Encyclopédie des mathématiques, EMS Press, 2001 [1994]
    • "Théorème du reste chinois", Encyclopédie des mathématiques, EMS Press, 2001 [1994]Weisstein, Eric W., "Théorème des restes chinois", MathWorld
    • Texte intégral du Sun-tzu Suan-ching (chinois) – Projet de texte chinois