ArithmétiqueThéorème · Glossaire
théorème des restes chinois
Le théorème des restes chinois affirme que, pour des modules entiers au moins égaux à 2 et deux à deux premiers entre eux, tout système imposant un reste entier pour chacun d'eux admet une solution, unique modulo leur produit. Il permet ainsi de reconstruire une classe d'entiers à partir de ses restes, principe utile pour décomposer certains calculs en opérations plus petites.
Sommaire
Ce que vous allez apprendre
- Interpréter un système de congruences comme plusieurs informations de reste.
- Reconnaître la condition de coprimalité deux à deux.
- Construire la solution avec des inverses modulaires.
- Vérifier le résultat sur l'exemple 23 modulo 105.
- Traiter avec prudence les modules qui ont un facteur commun.
En clair
Un nombre laisse le reste 2 quand on le divise par 3, le reste 3 quand on le divise par 5 et le reste 2 quand on le divise par 7. Peut-on retrouver ce nombre ? Le théorème des restes chinois rassemble ces trois indices. Ici, il conduit à 23, puis à tous les nombres obtenus en ajoutant ou en retirant 105.
Chaque division donne une information partielle. Lorsque les diviseurs sont premiers entre eux deux à deux, leur combinaison détermine une seule classe de nombres.
Définition
Le théorème des restes chinois résout simultanément plusieurs congruences. Une congruence indique le reste d'un entier après division par un module. On considère des modules m1, m2, …, mn, tous au moins égaux à 2 et premiers entre eux deux à deux, ainsi que des restes entiers a1, a2, …, an.
Le système admet alors une solution, unique modulo le produit M des modules. Cela signifie que toutes les solutions diffèrent d'un multiple de M. Pour construire une solution, on note Mi le quotient M/mi. Comme Mi et mi sont premiers entre eux, Mi possède un inverse yi modulo mi.
La solution est donnée par . Ce résultat appartient à l'arithmétique modulaire et se généralise en théorie des anneaux. Des cas particuliers sont décrits dans l'Antiquité chinoise par le mathématicien Sun Tzu, au 3e siècle.
Le principe
Si les entiers m1, …, mn, tous au moins égaux à 2, sont premiers entre eux deux à deux, alors le système suivant possède une unique solution modulo leur produit M :
Pour chaque indice i, on pose Mi = M/mi et on choisit l'inverse yi de Mi modulo mi. Une solution s'obtient alors par .
Quand l'utiliser
Le théorème porte sur des congruences d'entiers. Il faut connaître, pour chacune, un module au moins égal à 2 et le reste voulu. Les modules doivent être premiers entre eux deux à deux : le plus grand commun diviseur de chaque paire vaut 1. Cette condition garantit à la fois l'existence d'une solution pour tous les restes et son unicité modulo le produit des modules.
Si deux modules ont un facteur commun, la version donnée par le théorème ne s'applique pas. Par exemple, x ≡ 1 modulo 4 et x ≡ 2 modulo 6 sont incompatibles : la première congruence impose un nombre impair, la seconde un nombre pair. Il faut alors vérifier la compatibilité des restes modulo le plus grand commun diviseur, au lieu d'utiliser directement la formule.
Un exemple, pas à pas
On cherche un entier x qui laisse les restes 2, 3 et 2 lorsqu'il est divisé respectivement par 3, 5 et 7. Ces trois modules sont premiers entre eux deux à deux.
1. Le produit des modules vaut M = 3 × 5 × 7 = 105. On calcule M1 = 35, M2 = 21 et M3 = 15.
2. Les inverses utiles sont y1 = 2, car 35 × 2 ≡ 1 modulo 3, puis y2 = 1 et y3 = 1.
3. La formule donne . Comme 233 = 2 × 105 + 23, on obtient x ≡ 23 modulo 105.
4. Le contrôle est direct : 23 = 7 × 3 + 2, 23 = 4 × 5 + 3 et 23 = 3 × 7 + 2. Les trois restes demandés sont retrouvés.
Le schéma des trois divisions montre comment le même entier 23 satisfait simultanément les trois conditions. Toutes les solutions sont 23 + 105k, où k est un entier.
En pratique
En cryptographie, le théorème permet de remplacer un calcul modulo un grand produit par plusieurs calculs modulo des facteurs premiers entre eux. On le préfère lorsque cette décomposition réduit effectivement la taille des calculs.
En calcul parallèle, les opérations sur les différents modules peuvent être menées séparément, puis recombinées. Un calcul direct reste préférable si le coût de la décomposition et de la reconstruction dépasse le gain attendu.
En codage de l'information, plusieurs restes peuvent représenter un même entier. La reconstruction par le théorème convient lorsque les modules choisis sont premiers entre eux et que l'intervalle de valeurs est maîtrisé.
À ne pas confondre
Une congruence isolée fixe un seul reste modulo un seul entier. Le théorème des restes chinois intervient lorsque plusieurs congruences doivent être satisfaites ensemble. Chercher x ≡ 2 modulo 7 ne nécessite donc pas ce théorème.
L'algorithme d'Euclide étendu calcule notamment un inverse modulo un entier. Il fournit les inverses yi utilisés dans la construction, mais il ne constitue pas à lui seul le théorème de recombinaison.
Une égalité ordinaire désigne une valeur précise, tandis qu'une congruence désigne une classe d'entiers. Ainsi, x ≡ 23 modulo 105 inclut 23, 128 et −82 ; elle ne signifie pas x = 23.
Limites et pièges
Des modules non premiers entre eux ne rendent pas toujours le système impossible, mais la forme classique du théorème ne suffit plus. Le symptôme est un inverse Mi impossible à calculer. Il faut tester si les restes coïncident modulo le plus grand commun diviseur des modules concernés.
L'unicité est une unicité modulo M, non une valeur entière unique. Dans l'exemple, 23, 128 et −82 satisfont le même système. Pour obtenir un représentant unique, il faut imposer un intervalle, par exemple de 0 à 104.
Le reste euclidien canonique est compris entre 0 et mi − 1, mais un entier négatif ou supérieur au module peut représenter la même classe de congruence. On réduit ce représentant pour retrouver le reste canonique. Ainsi, 8 modulo 5 est congru à 3.
Pour aller plus loin
La fiche congruence modulo n précise la relation d'équivalence qui formalise l'idée de même reste.
L'article Une histoire de l'arithmétique modulaire replace les congruences et leurs usages dans le développement de l'arithmétique modulaire.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres