Calculatrice du Théorème des Restes Chinois : Résolvez les Systèmes Modulaires Étape par Étape
Une calculatrice du théorème des restes chinois résout un système de congruences simultanées — des énoncés comme x ≡ 2 (mod 3) et x ≡ 3 (mod 5) — en les combinant en une seule congruence modulo le produit (ou le plus petit commun multiple) des moduli individuels. La méthode remonte à environ 1 500 ans au texte mathématique chinois Sunzi Suanjing, et aujourd'hui elle sous-tend les optimisations de la cryptographie RSA, les calculs de calendrier et les codes correcteurs d'erreurs, en plus d'être un élément incontournable des cours de mathématiques discrètes et de théorie des nombres. Ce guide vous explique comment la calculatrice fonctionne en interne, comment vérifier si un système a une solution, comment trouver les inverses modulaires dont la méthode dépend, deux exemples complètement résolus — l'un avec des moduli premiers entre eux par paires et l'autre sans — ainsi que les erreurs courantes et les problèmes de pratique.
Sommaire
- 01Qu'est-ce que le Théorème des Restes Chinois ?
- 02Comment Fonctionne une Calculatrice du Théorème des Restes Chinois ?
- 03Comment Vérifier si les Moduli Sont Compatibles ?
- 04Qu'est-ce qu'un Inverse Modulaire et Comment le Trouver ?
- 05Exemple Travaillé : Résoudre les Congruences Premières entre Eux par Paires
- 06Exemple Travaillé : Réconcilier les Moduli Non Premiers Entre Eux
- 07Reconstruire la Plus Petite Solution Non-Négative
- 08Quelles Sont les Erreurs les Plus Courantes du Théorème des Restes Chinois ?
- 09Problèmes de Pratique : Testez Vos Compétences en Calculatrice du Théorème des Restes Chinois
Qu'est-ce que le Théorème des Restes Chinois ?
Le Théorème des Restes Chinois (TRC) énonce que si vous avez un système de congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), et les moduli m₁, m₂, ..., mₙ sont premiers entre eux par paires (chaque paire n'a pas de facteur commun sauf 1), alors il existe exactement une solution pour x modulo M, où M = m₁ × m₂ × ... × mₙ. Le théorème tire son nom de sa première apparition connue dans le texte chinois du 3e au 5e siècle Sunzi Suanjing (Manuel d'arithmétique du Maître Sun), qui posait l'énigme désormais classique : trouvez un nombre qui laisse un reste de 2 lorsqu'il est divisé par 3, un reste de 3 lorsqu'il est divisé par 5, et un reste de 2 lorsqu'il est divisé par 7. Cette énigme — et la méthode du TRC qui la résout — réapparaît constamment en dehors de la salle de classe : la cryptographie RSA utilise le TRC pour accélérer le déchiffrement en travaillant avec des moduli plus petits au lieu d'un seul énorme, les informaticiens l'utilisent pour représenter les grands nombres sous forme de tuples de résidus plus petits pour une arithmétique plus rapide, et les systèmes de calendrier l'utilisent pour réconcilier les cycles de différentes longueurs (jours de la semaine, jours du mois et cycles d'années bissextiles).
Théorème des Restes Chinois : pour les moduli premiers entre eux par paires m₁, ..., mₙ, le système x ≡ aᵢ (mod mᵢ) a exactement une solution modulo M = m₁ × m₂ × ... × mₙ.
Comment Vérifier si les Moduli Sont Compatibles ?
La version de manuel du Théorème des Restes Chinois exige des moduli premiers entre eux par paires, mais les systèmes réels — en particulier ceux qui apparaissent dans les problèmes d'ordonnancement ou de cryptographie — ont souvent des moduli qui partagent des facteurs. Une version généralisée du TRC s'applique toujours, mais seulement si le système réussit d'abord un test de compatibilité : pour chaque paire de congruences x ≡ aᵢ (mod mᵢ) et x ≡ aⱼ (mod mⱼ), les deux doivent être d'accord sur le chevauchement, ce qui signifie aᵢ ≡ aⱼ (mod pgcd(mᵢ, mⱼ)). Si ce test échoue pour une seule paire, le système n'a aucune solution du tout, quoi qu'il en soit — et une bonne calculatrice le rapporte au lieu de retourner un nombre incorrect.
1. Étape 1 : Calculer pgcd(mᵢ, mⱼ) pour chaque paire de moduli
Pour un système de deux congruences, il n'y a qu'une seule paire à vérifier. Pour un système de trois congruences, vérifiez les trois paires.
2. Étape 2 : Réduire les deux résidus modulo ce pgcd
Prenez aᵢ mod pgcd(mᵢ, mⱼ) et aⱼ mod pgcd(mᵢ, mⱼ). S'ils correspondent, la paire est compatible.
3. Étape 3 : Exemple d'un système incompatible
Prenez x ≡ 1 (mod 4) et x ≡ 0 (mod 6). pgcd(4, 6) = 2. Réduisez : 1 mod 2 = 1, et 0 mod 2 = 0. Puisque 1 ≠ 0, aucun entier ne satisfait les deux congruences — le système n'a pas de solution, et une calculatrice du théorème des restes chinois devrait signaler exactement cela au lieu de forcer une réponse.
Règle de compatibilité pour les moduli non premiers entre eux : x ≡ aᵢ (mod mᵢ) et x ≡ aⱼ (mod mⱼ) ne peuvent tous deux être vrais que si aᵢ ≡ aⱼ (mod pgcd(mᵢ, mⱼ)).
Qu'est-ce qu'un Inverse Modulaire et Comment le Trouver ?
L'inverse modulaire d'un nombre a modulo m est un autre nombre b tel que a × b ≡ 1 (mod m) — il joue le même rôle que 1/a dans la division ordinaire, mais restreint aux nombres entiers dans un modulus fixe. Un inverse modulaire existe si et seulement si pgcd(a, m) = 1, ce qui est exactement pourquoi le Théorème des Restes Chinois standard exige des moduli premiers entre eux par paires : cela garantit que chaque Mᵢ a un inverse mod mᵢ. Le moyen le plus fiable de trouver un inverse modulaire à la main est l'algorithme euclidien étendu, qui exécute l'algorithme pgcd ordinaire en avant puis revient en arrière pour exprimer 1 comme une combinaison de a et m.
1. Étape 1 : Exécuter l'algorithme euclidien en avant
Trouvez l'inverse de 4 mod 7. Divisez à plusieurs reprises : 7 = 1×4 + 3, puis 4 = 1×3 + 1, puis 3 = 3×1 + 0. Les restes sont 3, puis 1, puis 0, confirmant pgcd(4, 7) = 1, donc un inverse existe.
2. Étape 2 : Revenir en arrière pour isoler 1
À partir de l'avant-dernière ligne, 1 = 4 − 1×3. Substituez 3 = 7 − 1×4 de la première ligne : 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. Étape 3 : Lire l'inverse
L'équation 1 = 2×4 − 1×7 signifie 2×4 ≡ 1 (mod 7), donc l'inverse de 4 mod 7 est 2. Vérification rapide : 4 × 2 = 8 = 7 + 1, qui est en effet ≡ 1 (mod 7).
Pour les petits moduli, il est souvent plus rapide de tester les candidats directement : multipliez a par 1, 2, 3, ... mod m jusqu'à ce que le produit soit 1. Pour les moduli plus grands, l'algorithme euclidien étendu est bien plus fiable.
Exemple Travaillé : Résoudre les Congruences Premières entre Eux par Paires
C'est le problème classique du Sunzi Suanjing : trouvez x tel que x ≡ 2 (mod 3), x ≡ 3 (mod 5), et x ≡ 2 (mod 7). Les moduli 3, 5 et 7 sont premiers entre eux par paires, donc la formule TRC standard s'applique directement.
1. Étape 1 : Calculer M
M = 3 × 5 × 7 = 105.
2. Étape 2 : Calculer chaque Mᵢ et son inverse
M₁ = 105/3 = 35. 35 mod 3 = 2, et l'inverse de 2 mod 3 est 2 (puisque 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, et l'inverse de 1 mod 5 est 1. M₃ = 105/7 = 15. 15 mod 7 = 1, et l'inverse de 1 mod 7 est 1.
3. Étape 3 : Combiner
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. Étape 4 : Vérifier
23 ÷ 3 = 7 reste 2 ✓. 23 ÷ 5 = 4 reste 3 ✓. 23 ÷ 7 = 3 reste 2 ✓. La plus petite solution non-négative est x = 23, et chaque autre solution est 23 + 105k pour tout entier k.
x ≡ 23 (mod 105) — la même réponse qu'une calculatrice du théorème des restes chinois retourne instantanément, et le même puzzle qui a ouvert cette branche de la théorie des nombres il y a plus de mille ans.
Exemple Travaillé : Réconcilier les Moduli Non Premiers Entre Eux
Maintenant résolvez x ≡ 3 (mod 4) et x ≡ 1 (mod 6), où 4 et 6 ne sont pas premiers entre eux (ils partagent un facteur de 2). La formule standard de l'exemple coprime par paires ne s'applique pas directement, mais le système peut toujours avoir une solution unique modulo le plus petit commun multiple des moduli, à condition qu'il réussisse d'abord le test de compatibilité.
1. Étape 1 : Vérifier la compatibilité
pgcd(4, 6) = 2. Réduisez les deux résidus : 3 mod 2 = 1, et 1 mod 2 = 1. Ils correspondent, donc le système est compatible et une solution existe.
2. Étape 2 : Trouver le modulus combiné
Au lieu de multiplier 4 × 6 = 24, utilisez le plus petit commun multiple : lcm(4, 6) = 12. La solution sera unique modulo 12, pas 24.
3. Étape 3 : Substituer et résoudre
Écrivez x = 4k + 3 à partir de la première congruence, puis substituez dans la deuxième : 4k + 3 ≡ 1 (mod 6), donc 4k ≡ −2 ≡ 4 (mod 6). Les deux côtés et le modulus partagent un facteur de pgcd(4, 6) = 2, donc divisez la congruence entière par 2 : 2k ≡ 2 (mod 3). L'inverse de 2 mod 3 est 2, donc k ≡ 2×2 ≡ 1 (mod 3).
4. Étape 4 : Reconstruire x
k = 3j + 1 pour tout entier j, donc x = 4(3j + 1) + 3 = 12j + 7. La plus petite solution non-négative est x = 7.
5. Étape 5 : Vérifier
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. Donc x ≡ 7 (mod 12) est correct, et diviser la congruence par le facteur partagé — plutôt que de l'ignorer — est l'étape qui rend le TRC non-coprime fonctionnel.
Quand les moduli partagent un facteur commun, vous ne pouvez pas utiliser la formule coprime par paires telle quelle — vous devez diviser la congruence résultante par pgcd(mᵢ, mⱼ) avant de trouver l'inverse, ou l'inverse n'existera pas.
Reconstruire la Plus Petite Solution Non-Négative
Chaque système du théorème des restes chinois qui réussit son vérification de compatibilité a infiniment de solutions entières, pas seulement une — mais elles sont toutes congruentes l'une à l'autre modulo M (ou modulo lcm(m₁, ..., mₙ) dans le cas non-coprime). Par convention, une calculatrice rapporte le plus petit représentant non-négatif de cette famille infinie, la valeur x₀ satisfaisant 0 ≤ x₀ < M, car c'est la réponse canonique unique la plus facile à énoncer, comparer et vérifier. Chaque autre solution est simplement x₀ plus ou moins un multiple de M.
1. Réduire une somme intermédiaire négative
La somme pondérée à l'étape 4 de la méthode de la calculatrice peut être négative si un résidu aᵢ est négatif ou si un inverse modulaire a été calculé comme un représentant négatif. Si la somme est, disons, S = −37 et M = 45, ajoutez M à plusieurs reprises jusqu'à ce que le résultat soit non-négatif : −37 + 45 = 8, donc la plus petite solution non-négative est x₀ = 8, pas −37.
2. L'ensemble de solutions complet
Une fois que vous avez x₀, l'ensemble de solutions complètes est chaque entier de la forme x₀ + kM pour k = ..., −2, −1, 0, 1, 2, .... Dans l'exemple Sunzi ci-dessus, c'est 23, 128, 233, ... et aussi −82, −187, et ainsi de suite — mais 23 est celui que vous rapportez sauf si une plage spécifique est demandée.
Un résultat intermédiaire négatif ou surdimensionné n'est pas faux — il n'a juste pas encore été réduit. Ajoutez ou soustrayez des multiples de M jusqu'à ce que la valeur se situe dans [0, M).
Quelles Sont les Erreurs les Plus Courantes du Théorème des Restes Chinois ?
La plupart des erreurs dans les problèmes de TRC proviennent de l'omission d'une vérification plutôt que d'un calcul final défectueux, c'est pourquoi il vaut la peine de ralentir au début d'un problème plutôt qu'à la fin.
1. Appliquer la formule coprime aux moduli non premiers entre eux
Si deux moduli partagent un facteur, calculer M comme leur produit direct et rechercher les inverses modulaires de la manière standard échouera silencieusement ou produira une réponse incorrecte — vérifiez toujours pgcd(mᵢ, mⱼ) = 1 pour chaque paire d'abord.
2. Confondre un inverse modulaire avec une fraction ordinaire
L'inverse de 4 mod 7 est 2, pas 1/4 — les inverses modulaires sont des nombres entiers trouvés via l'algorithme euclidien étendu (ou la multiplication d'essai pour les petits moduli), jamais des fractions.
3. Ne pas réduire correctement les nombres négatifs modulo m
−2 mod 6 est 4, pas −2 et pas 2 — continuez à ajouter le modulus jusqu'à ce que le résultat soit dans la plage [0, m). Tronquer ou prendre la valeur absolue au lieu d'ajouter le modulus est une source fréquente de mauvaises réponses.
4. Oublier de diviser par le facteur partagé dans les systèmes non-coprime
Quand les moduli partagent un facteur commun, une congruence comme 4k ≡ 4 (mod 6) doit être divisée par pgcd(4, 6) = 2 pour devenir 2k ≡ 2 (mod 3) avant de pouvoir trouver un inverse — 4 n'a pas d'inverse mod 6 du tout, puisque pgcd(4, 6) ≠ 1.
5. S'arrêter avant de réduire la somme finale modulo M
La somme pondérée de l'étape 4 (par exemple, 233 dans le problème Sunzi) n'est pas la réponse finale — elle doit être réduite modulo M (233 mod 105 = 23) pour atteindre la plus petite solution non-négative.
Si votre réponse ne satisfait pas chaque congruence originale quand vous la substituez, revérifiez le test de compatibilité et les inverses modulaires d'abord — c'est là que presque chaque erreur de TRC se produit réellement.
Problèmes de Pratique : Testez Vos Compétences en Calculatrice du Théorème des Restes Chinois
Travaillez sur ces trois systèmes à la main, en vérifiant d'abord la coprimité par paires ou la compatibilité, avant de les comparer avec les solutions ci-dessous. Le deuxième problème est délibérément insoluble — reconnaître cela est aussi important que de trouver une réponse numérique quand elle existe.
1. Problème 1 (coprime par paires)
Résolvez : x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Réponse : M = 105. M₁ = 35 avec inverse 2 mod 3 ; M₂ = 21 avec inverse 1 mod 5 ; M₃ = 15 avec inverse 1 mod 7. Somme = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Vérification : 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Solution : x ≡ 34 (mod 105).
2. Problème 2 (moduli incompatibles — pas de solution)
Résolvez : x ≡ 2 (mod 8), x ≡ 5 (mod 12). pgcd(8, 12) = 4. Réduisez : 2 mod 4 = 2, et 5 mod 4 = 1. Puisque 2 ≠ 1, le système est incompatible et n'a pas de solution — une calculatrice du théorème des restes chinois devrait retourner cette conclusion plutôt qu'un nombre incorrect.
3. Problème 3 (moduli non-coprime compatibles)
Résolvez : x ≡ 5 (mod 9), x ≡ 2 (mod 6). pgcd(9, 6) = 3. Réduisez : 5 mod 3 = 2, et 2 mod 3 = 2 — compatible. lcm(9, 6) = 18. Écrivez x = 9k + 5, substituez : 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Divisez par pgcd(9, 6) = 3 : 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). Donc k = 2j + 1, donnant x = 9(2j+1) + 5 = 18j + 14. Vérification : 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Solution : x ≡ 14 (mod 18). Si vous voulez vérifier chaque inverse modulaire et étape de réduction sur un problème comme celui-ci, le résolveur mathématique pas à pas de Solvify vous expliquera chaque étape de la même façon que ce guide.
Le moyen le plus rapide de développer une véritable maîtrise du Théorème des Restes Chinois est de résoudre un mélange de systèmes coprime, non-coprime-mais-compatibles et incompatibles — reconnaître quel cas vous êtes dedans est la moitié de la compétence.
Articles connexes
Calculatrice du Théorème des Restes : Comment Trouver les Restes Étape par Étape
Un concept de reste différent mais connexe — ce guide couvre le théorème des restes des polynômes, un contexte utile avant de s'attaquer aux congruences modulaires.
Calculatrice d'Élimination de Gauss : Résolvez les Systèmes Linéaires Étape par Étape
Une autre méthode de calculatrice systématique et algorithmique — comparez comment l'élimination de Gauss et le Théorème des Restes Chinois réduisent chacun un système à une réponse unique.
Résolution de Problèmes Mathématiques Étape par Étape : Un Cadre Répétable pour Tout Problème
Le cadre en 5 étapes de ce guide s'applique directement aux problèmes de TRC : identifier ce qui est donné, choisir une méthode, travailler systématiquement et vérifier le résultat.
Solveurs mathématiques
Résolveur Smart Scan
Prenez une photo d'un système de congruence ou d'un problème de théorie des nombres et obtenez une solution instantanée du Théorème des Restes Chinois étape par étape.
Solutions Étape par Étape
Voyez chaque inverse modulaire, test de compatibilité et étape de réduction expliqués, pas seulement le résidu final.
Tuteur Mathématique IA
Posez des questions de suivi sur les inverses modulaires, les moduli premiers entre eux, ou pourquoi un système n'a pas de solution, avec des réponses adaptées à votre problème exact.
Matières connexes
Fondations de l'Algèbre
Le confort avec les fractions et les restes rend l'arithmétique modulaire et le Théorème des Restes Chinois bien plus faciles à apprendre.
Calculatrice du Rang de Matrice
Une autre méthode de calculatrice algorithmique et adjacente à la théorie des nombres — une pratique utile pour le même état d'esprit systématique et étape par étape que le TRC exige.
Comment Fonctionne une Calculatrice du Théorème des Restes Chinois ?
Une calculatrice du théorème des restes chinois automatise quatre étapes qui sont fastidieuses à suivre à la main une fois qu'un système compte trois congruences ou plus, en particulier les calculs d'inverses modulaires. En interne, elle traite chaque congruence comme une paire (aᵢ, mᵢ), confirme que les moduli peuvent être utilisés ensemble, puis construit la solution unique en utilisant une somme pondérée plutôt que des essais et erreurs. Comprendre ces quatre étapes vous permet de vérifier le résultat d'une calculatrice ou de résoudre le même problème à la main lors d'un examen où aucune calculatrice n'est autorisée.
1. Étape 1 : Vérifier les moduli
Confirmez que chaque paire de moduli est première entre eux (pgcd = 1). Si une paire partage un facteur commun, la calculatrice bascule vers la vérification de compatibilité décrite dans la section suivante au lieu de la formule standard.
2. Étape 2 : Calculer le modulus combiné M
Multipliez tous les moduli ensemble : M = m₁ × m₂ × ... × mₙ. C'est le modulus de la réponse finale combinée.
3. Étape 3 : Trouver chaque produit partiel et son inverse modulaire
Pour chaque congruence i, calculez Mᵢ = M / mᵢ (le produit de tous les moduli sauf mᵢ), puis trouvez l'inverse modulaire de Mᵢ modulo mᵢ — appelez-le yᵢ, où Mᵢ × yᵢ ≡ 1 (mod mᵢ).
4. Étape 4 : Combiner et réduire
Additionnez aᵢ × Mᵢ × yᵢ pour chaque congruence, puis réduisez cette somme modulo M pour obtenir la plus petite solution non-négative unique x.