Le théorème des restes chinois expliqué

Un nombre laisse 2 dans la division par 3, 3 dans la division par 5 et 2 dans la division par 7. Quel est ce nombre ? Essayez les nombres un par un et vous arrivez à 23 au bout d'un moment, mais la question cache un théorème : tant que les diviseurs n'ont pas de facteur commun, il y a toujours exactement une réponse inférieure à leur produit, et on la trouve sans rien essayer. Le théorème a environ 1 500 ans et sert encore dans les calendriers, l'arithmétique des ordinateurs et la cryptographie qui protège le web.

Trois rangées de marques pour les nombres qui laissent 2 mod 3, 3 mod 5 et 2 mod 7, alignées dans une seule colonne à 23
Trois rangées de marques pour les nombres qui laissent 2 mod 3, 3 mod 5 et 2 mod 7, alignées dans une seule colonne à 23

Un problème du Sunzi Suanjing

Le Sunzi Suanjing, un livre d'arithmétique chinois du IIIᵉ au Vᵉ siècle, demande un nombre d'objets qui laisse 2 quand on les compte par trois, 3 quand on les compte par cinq et 2 quand on les compte par sept. Sa réponse est 23, et sa méthode est celle qu'on enseigne encore : prenez 70 pour chaque objet restant par trois, 21 pour chaque objet restant par cinq et 15 pour chaque objet restant par sept, additionnez, et retranchez 105 autant de fois que possible. 2 × 70 + 3 × 21 + 2 × 15 = 233, et 233 − 2 × 105 = 23. Un poème de l'époque Ming a gardé en mémoire les nombres 70, 21, 15 et 105 pendant des siècles. Qin Jiushao a donné une méthode générale en 1247, le même problème figure dans le Liber Abaci de Fibonacci de 1202, et Carl Friedrich Gauss a énoncé le théorème sous sa forme moderne dans ses Disquisitiones Arithmeticae de 1801.

Une page d’une édition Qing du Sunzi Suanjing, le traité d’arithmétique chinois des IIIe–Ve siècles qui demande un nombre laissant 2, 3 et 2 lorsqu’on compte par trois, par cinq et par sept.
Une page d’une édition Qing du Sunzi Suanjing, le traité d’arithmétique chinois des IIIe–Ve siècles qui demande un nombre laissant 2, 3 et 2 lorsqu’on compte par trois, par cinq et par sept.
Carl Friedrich Gauss, sur un portrait de Christian Albrecht Jensen de 1840. Il introduisit la notation de congruence a ≡ b (mod n) dans ses Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, sur un portrait de Christian Albrecht Jensen de 1840. Il introduisit la notation de congruence a ≡ b (mod n) dans ses Disquisitiones Arithmeticae de 1801.

Ce que dit le théorème

Prenez des modules n₁, n₂, …, nₖ dont aucun couple n'a de facteur commun, et des restes quelconques a₁, a₂, …, aₖ. Il existe alors exactement un entier x entre 0 et N − 1, où N = n₁ × n₂ × … × nₖ, qui laisse le reste aᵢ dans la division par nᵢ, pour tout i. Toutes les autres solutions en diffèrent d'un multiple de N. Dans la notation de l'arithmétique modulaire : le système x ≡ aᵢ (mod nᵢ) a une solution, unique mod N. Autrement dit, un nombre entre 0 et N − 1 et la liste de ses restes portent exactement la même information : 3 × 5 × 7 = 105 nombres et 3 × 5 × 7 = 105 listes de restes possibles, chacune utilisée une fois.

Construire la solution

Les nombres 70, 21 et 15 n'ont rien de magique. Chacun laisse 1 dans la division par son propre module et 0 dans la division par les autres : 70 = 2 × 35 est un multiple de 5 et de 7 et laisse 1 dans la division par 3. En général, on prend Nᵢ = N / nᵢ, multiple de tous les modules sauf nᵢ, et on le multiplie par yᵢ, l'inverse de Nᵢ mod nᵢ. L'inverse existe parce que Nᵢ et nᵢ n'ont pas de facteur commun, et l'algorithme d'Euclide étendu le trouve : il effectue les divisions d'Euclide pour le plus grand commun diviseur et remonte jusqu'à l'identité de Bézout 1 = s × nᵢ + t × Nᵢ, de sorte que t est l'inverse. Alors x = a₁N₁y₁ + a₂N₂y₂ + …, réduit mod N, convient à chaque équation, car chaque terme convient à sa propre équation et disparaît dans toutes les autres.

Une équation à la fois

Il existe une seconde méthode, qui n'a pas besoin du produit de tous les modules. Toute solution de x ≡ 2 (mod 3) s'écrit x = 2 + 3t. Reportez-la dans l'équation suivante : 2 + 3t ≡ 3 (mod 5), donc 3t ≡ 1 (mod 5), et en multipliant par 2, l'inverse de 3 mod 5, on obtient t ≡ 2 (mod 5). Alors x = 2 + 3 × 2 = 8, et les deux premières équations ensemble disent x ≡ 8 (mod 15). Recommencez avec la troisième équation : 8 + 15t ≡ 2 (mod 7) donne t ≡ 1, donc x ≡ 23 (mod 105). Cette substitution garde des nombres plus petits, c'est ainsi qu'un ordinateur résout généralement ces systèmes, et elle marche encore quand les modules ont un facteur commun.

Modules avec un facteur commun

Si deux modules ont un facteur commun, leurs équations se chevauchent : x ≡ 1 (mod 4) dit déjà que x est impair, et x ≡ 4 (mod 6) dit que x est pair, donc aucun x ne vérifie les deux. En général, x ≡ a (mod m) et x ≡ b (mod n) peuvent être vraies ensemble exactement quand a et b laissent le même reste dans la division par g = gcd(m, n), c'est-à-dire quand g divise a − b. La solution est alors unique mod lcm(m, n) = m × n / g, et non mod m × n. La vieille énigme du panier d'œufs, qui en laisse 1 quand on les sort par 2, 3, 4, 5 ou 6 et aucun quand on les sort par 7, a pour réponse 301, qui se répète tous les 420 = lcm(2, 3, 4, 5, 6, 7). Un système a une solution exactement quand chaque paire de ses équations concorde, donc un système impossible contient toujours une paire qui se contredit.

Calendriers, ordinateurs et RSA

En 1583, Joseph Scaliger a combiné trois cycles du calendrier, le cycle solaire de 28 ans, le cycle lunaire de 19 ans et l'indiction de 15 ans, en une période julienne de 28 × 19 × 15 = 7 980 ans. D'après le théorème, chaque année a sa propre combinaison des trois numéros de cycle, et la période commence en 4713 av. J.-C., la dernière année où les trois valaient 1 ; les astronomes comptent encore les jours juliens à partir de là. Les ordinateurs se servent du théorème pour calculer avec d'énormes nombres sous forme de listes de petits restes, qu'on peut additionner et multiplier séparément et en parallèle, puis réunir à la fin. Le déchiffrement RSA fonctionne de la même façon : c^d mod n avec n = p × q se calcule comme deux puissances mod p et mod q, réunies par le théorème, environ quatre fois plus vite qu'une puissance mod n. Des schémas de partage de secret, comme ceux de Mignotte et d'Asmuth et Bloom, cachent un secret dans des restes, de sorte que seul un nombre suffisant d'entre eux le révèle.

Ron Rivest, Adi Shamir et Len Adleman (de gauche à droite)
Ron Rivest, Adi Shamir et Len Adleman (de gauche à droite)

À vous de jouer

Ouvrez le solveur pour saisir n'importe quel système de congruences, jusqu'à 20 équations et des nombres d'au plus 200 chiffres, ou choisissez l'un des exemples résolus : le problème de Sunzi, le panier d'œufs, la période julienne, deux horaires de bus, le déchiffrement RSA et un système sans solution. Le calcul est détaillé avec vos nombres, par la construction ou par substitution, avec l'algorithme d'Euclide étendu pour chaque inverse. L'image marque les nombres qui vérifient chaque équation, pour voir la seule colonne où elles se rejoignent toutes, ou dispose les restes de deux équations dans une table où chaque nombre a sa propre case.

Questions fréquemment posées

La solution d'un système de congruences est-elle unique ?

Seulement à un multiple du module près. Si x = 23 résout le problème de Sunzi, alors 23 + 105 = 128, 233 et −82 le résolvent aussi, car ajouter 105 ne change aucun reste. Le théorème dit qu'il y a exactement une solution entre 0 et 104 ; avec des modules à facteurs communs, exactement une en dessous de leur plus petit commun multiple.

Pourquoi les modules doivent-ils être premiers entre eux ?

Pour la construction, parce que Nᵢ doit avoir un inverse mod nᵢ, ce qui n'est possible que s'ils n'ont pas de facteur commun. Pour le théorème lui-même, parce que des facteurs communs font se chevaucher certaines équations : un système n'a alors aucune solution ou en a moins de différentes, et les solutions se répètent tous les plus petits communs multiples au lieu de tous les produits.

Comment trouver un inverse modulaire à la main ?

Avec l'algorithme d'Euclide étendu. Pour l'inverse de 15 mod 7 : 15 = 2 × 7 + 1, donc 1 = 15 − 2 × 7, et 15 × 1 ≡ 1 (mod 7) : l'inverse est 1. Pour 35 mod 3 : 35 = 11 × 3 + 2 et 3 = 1 × 2 + 1, donc 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, et l'inverse de 35 mod 3 est −1 ≡ 2. Pour de petits modules, on peut aussi essayer simplement 1, 2, 3, … jusqu'à ce que le produit laisse 1.

Quel rapport entre le théorème et les horloges ?

Un reste mod n est une position sur une horloge à n heures. Deux horloges à 3 et 5 heures, lancées ensemble et avancées d'une heure à la fois, affichent chacune des 15 paires de positions une fois avant de revenir au départ, car 3 et 5 n'ont pas de facteur commun. Des horloges à 4 et 6 heures reviennent après 12 pas et n'affichent que 12 des 24 paires : une position impaire et une position paire n'apparaissent jamais ensemble.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le solveur du théorème des restes chinois