Calculateur du théorème des restes chinois (TRC) — Résoudre des congruences simultanées
Résout un système de congruences simultanées x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... grâce au théorème des restes chinois. Vérifie automatiquement que les modules sont premiers entre eux deux à deux et fournit la plus petite solution non négative ainsi que la solution générale.
Exemple résolu : le problème du « nombre inconnu » du Sunzi Suanjing
Un problème classique tiré du Sunzi Suanjing (le « classique mathématique de Sun Tzu »), un traité d'arithmétique chinois datant approximativement du IIIe au Ve siècle, souvent cité comme l'origine du théorème des restes chinois. La question « quel nombre laisse un reste de 2 divisé par 3, un reste de 3 divisé par 5 et un reste de 2 divisé par 7 ? » a pour réponse 23, modulo 105.
| Condition 1 | x ≡ 2 (mod 3) |
|---|---|
| Condition 2 | x ≡ 3 (mod 5) |
| Condition 3 | x ≡ 2 (mod 7) |
| Solution | x ≡ 23 (mod 105) |
Ce qu’est le théorème des restes chinois
Le théorème des restes chinois résout des systèmes de congruences du genre **« quel nombre laisse 2 en le divisant par 3, 3 par 5 et 2 par 7 ? »**. Si les modules sont tous premiers entre eux, il existe exactement une solution dans l’intervalle que fixe leur produit. Cet outil prend jusqu’à cinq congruences et rend la plus petite solution positive ou nulle, avec la solution générale.
**Seule la forme classique est traitée : celle où tous les modules sont premiers entre eux.** Si deux d’entre eux partagent un diviseur supérieur à un, le système ne se résout pas par cette voie et un message le signale ; le théorème généralisé pour des modules non premiers entre eux sort du cadre. **Les modules doivent être des entiers à partir de 2**, et les restes se ramènent d’eux-mêmes à l’intervalle allant de zéro jusqu’au-dessous de leur module : des valeurs égales ou supérieures au module, et négatives, sont donc admises. Le calcul se fait sur des entiers de précision arbitraire : nulle limite de chiffres.
Comment se servir du calculateur
- Saisissez le reste et le module Pour chaque congruence, donnez le reste a et le module n. Ils valent pour x ≡ a (mod n).
- Ajoutez des congruences Par « ajouter une congruence », alignez-en jusqu’à cinq. Plus il y en a, plus large l’intervalle — le produit des modules — sur lequel la solution demeure unique.
- Résolvez Appuyez sur résoudre : vous obtenez la plus petite solution positive ou nulle, avec la solution générale modulo le produit des modules.
- Suivez le détail du calcul Pour chaque congruence figurent Nᵢ (le produit des modules privé du sien) et Mᵢ (l’inverse de Nᵢ). Ils servent à recouper une solution obtenue à la main.
- Des modules premiers entre eux sont exigés Un message disant que les modules ne sont pas premiers entre eux signifie que deux partagent un diviseur — 4 et 6, par exemple. Revoyez la combinaison.
Astuces pour en tirer le meilleur parti
- Si les modules (nᵢ) ne sont pas premiers entre eux deux à deux, une erreur s'affiche — par exemple mod 4 et mod 6 partagent le facteur 2, donc ce calculateur ne peut pas résoudre ce système (il faudrait le TRC généralisé).
- Inutile de réduire vous-même le reste aᵢ : même s'il est négatif ou supérieur à nᵢ, le calculateur le normalise automatiquement en mod nᵢ en interne avant de résoudre.
- Vous pouvez ajouter de 2 à 5 congruences. Pratique pour les énigmes exigeant qu'un nombre satisfasse trois conditions périodiques ou plus à la fois, comme le célèbre problème « deviner le nombre de soldats ».
- La solution générale est affichée sous la forme x ≡ résultat (mod N) : ajouter n'importe quel multiple de N au résultat satisfait toujours toutes les congruences d'origine.
Où le théorème est utile
Exercices d’arithmétique et préparation aux examens
Il sert à recouper une réponse faite à la main. Nᵢ et Mᵢ paraissant aussi, on cerne l’endroit où une erreur s’est glissée.
Étudier des algorithmes cryptographiques
L’optimisation CRT qui accélère le déchiffrement RSA applique ce théorème directement. Le mécanisme se suit en chiffres.
Trouver quand des cycles coïncident
Les instants où des événements de périodes différentes tombent ensemble s’écrivent comme un système de congruences.
Refaire le problème classique
Le « nombre inconnu » du Sunzi Suanjing — laissant 2 par 3, 3 par 5 et 2 par 7 — vaut 23 modulo 105. Saisissez-le tel quel et voyez.
Quand vous voulez les outils voisins d’arithmétique
Pour les inverses et les congruences elles-mêmes, voyez l’arithmétique modulaire ; pour les plus grands communs diviseurs, PGCD et PPCM ; pour la décomposition, la factorisation en nombres premiers.
Termes relatifs au théorème des restes chinois
- Théorème des restes chinois
- Le théorème énonçant qu’un système de congruences à modules premiers entre eux possède une solution unique modulo leur produit.
- Congruence
- Une expression de la forme x ≡ a (mod n), disant que le reste de x divisé par n égale a.
- Module
- Le nombre par lequel on divise. Ici borné aux entiers à partir de 2.
- Premiers entre eux
- Deux entiers dont le plus grand commun diviseur est 1. Le théorème classique exige que deux quelconques des modules le soient.
- Premiers entre eux deux à deux
- Pour trois nombres ou plus : que deux quelconques d’entre eux soient premiers entre eux. Un ensemble peut avoir 1 pour plus grand commun diviseur sans l’être deux à deux.
- Inverse modulaire
- Le x vérifiant a·x ≡ 1 (mod n). Dans le théorème, il paraît au moment de trouver Mᵢ, l’inverse de Nᵢ.
- Algorithme d’Euclide étendu
- L’algorithme qui rend les coefficients de Bézout en même temps que le plus grand commun diviseur. C’est lui qui calcule un inverse modulaire.
- Solution générale
- La plus petite solution positive ou nulle, augmentée de tout multiple entier du produit des modules, écrite sous la forme x ≡ 23 (mod 105).
Questions fréquentes
Anecdote — D'un traité d'arithmétique du IIIe siècle à l'accélération du chiffrement RSA
Le théorème des restes chinois remonte à un problème du Sunzi Suanjing, un classique arithmétique chinois que l'on situe généralement entre le IIIe et le Ve siècle de notre ère. Sa célèbre énigme du « nombre inconnu » — trouver un nombre laissant des restes de 2, 3 et 2 lorsqu'il est divisé respectivement par 3, 5 et 7 — capturait déjà l'idée essentielle du théorème moderne : reconstituer un nombre inconnu à partir de plusieurs restes de division.
L'une des applications pratiques les plus importantes du théorème des restes chinois aujourd'hui est l'accélération du déchiffrement RSA. Le déchiffrement RSA nécessite d'élever un grand nombre à une puissance modulo un nombre composé n = p × q, où p et q sont de grands nombres premiers. Plutôt que de travailler directement modulo n, le TRC permet d'effectuer le calcul indépendamment modulo p et modulo q, puis de recombiner les résultats — une technique appelée CRT-RSA qui peut théoriquement accélérer le déchiffrement de près de quatre fois, et qui est implémentée dans de nombreuses bibliothèques cryptographiques.
Cet outil prend en charge la forme classique du théorème, qui exige que tous les modules soient premiers entre eux deux à deux. Lorsque les modules partagent des facteurs communs (par exemple mod 4 et mod 6), une solution peut parfois encore exister, mais sa détermination nécessite le théorème des restes chinois généralisé, ce qui dépasse le cadre de cet outil.