## [Reconstruction par le Théorème Chinois des Restes](/fr/node/61536) Définition Une technique de reconstruction qui combine les restes d'un entier (ou d'un polynôme) modulo plusieurs modules deux à deux premiers entre eux pour retrouver l'entier original (ou le polynôme) modulo le produit des modules, l'unicité étant garantie modulo ce produit. ## Principe Principe D'après le Théorème Chinois des Restes, un système cohérent de congruences x ≡ r_i (mod m_i) avec gcd(m_i,m_j)=1 admet une solution unique modulo M = ∏ m_i ; des algorithmes constructifs assemblent les restes à l'aide d'inverses modulaires ou de développements en base mixte pour récupérer x mod M. ## Démonstration Démonstration Étant donné x ≡ 2 (mod 3), x ≡ 3 (mod 5) et x ≡ 2 (mod 7), calculer la solution unique modulo 105 en combinant les restes (ici x ≡ 23 (mod 105)), reconstruisant ainsi la classe entière à partir de ses morceaux modulaires. ## Mauvaise application Mauvaise application Appliquer le CRT lorsque les modules ne sont pas deux à deux premiers sans vérifier la compatibilité, ou penser que le CRT reconstruit l'entier absolu plutôt que seulement la classe modulo le produit, conduit à des reconstructions globales erronées ou ambiguës. ## Conséquence Conséquence Une reconstruction CRT correcte permet des algorithmes modulaires : effectuer des calculs lourds modulo des petits nombres premiers et combiner les résultats pour obtenir des valeurs modulo de grands modules composés, favorise la parallélisation et soutient la reconstruction rationnelle/entière. ## Inversion Inversion La réduction modulo chaque module est l'opération inverse : étant donné un entier, calculer ses restes. Dans certains algorithmes, on inverse le CRT en divisant un calcul modulaire en calculs indépendants de faible module pour des raisons d'efficacité. ## Limite Limite Exige des modules deux à deux premiers pour le résultat d'unicité standard ; des généralisations existent pour modules non coprimes mais requièrent des vérifications de compatibilité et peuvent donner plusieurs ou aucune solution ; des bornes entières sont aussi nécessaires pour relever une classe de restes en entier canonique. ## Tension sémantique Tension sémantique Tension avec le relèvement de Hensel et la reconstruction rationnelle : le CRT combine des données modulaires indépendantes globalement, tandis que Hensel élève localement la précision p-adique ; la reconstruction rationnelle peut nécessiter CRT et bornes pour retrouver des rationnels petits. ## Synthèse Synthèse La Reconstruction par le Théorème Chinois des Restes est l'assemblage constructif de restes modulaires en une classe de restes unique modulo le produit de modules deux à deux premiers, permettant la récupération globale à partir de calculs modulaires locaux et constituant l'épine dorsale de nombreux algorithmes modulaires.