Plus petite solution
Module
Modules

    Équations

    En savoir plus sur le théorème des restes chinois

    Solveur du théorème des restes chinois

    Comptez un tas d'objets par trois et il en reste 2, par cinq il en reste 3, par sept il en reste 2 : il y en a 23, ou 128, ou 233, une réponse tous les 105. C'est le problème du Sunzi Suanjing qui a donné son nom au théorème des restes chinois. Saisissez n'importe quel système de congruences x ≡ a (mod n), avec autant d'équations et des nombres aussi grands que vous voulez, et voyez la réponse, le calcul avec vos nombres et une image qui montre pourquoi ça marche. Quand les équations ne peuvent pas toutes être vraies, le solveur nomme les deux qui se contredisent et montre pourquoi. Saisissez les équations x ≡ a (mod n), une par ligne : a est le reste et n le module. Ajoutez une ligne avec Ajouter une équation, ou avec Entrée dans le dernier module, et supprimez-en une avec ×. Les entiers jusqu'à 200 chiffres fonctionnent, et a peut être négatif. Ou choisissez un exemple résolu. Les tuiles montrent la plus petite solution et sa période ; en dessous viennent les premières solutions positives et une vérification de chaque équation. L'image marque les nombres qui vérifient chaque équation, et la colonne où chaque ligne porte une marque est la solution ; la table des restes montre deux équations à la fois. Le calcul est détaillé avec vos nombres, par la construction classique ou par substitution.

    Comment ça marche

    1. Saisissez les équations x ≡ a (mod n), une par ligne, ou choisissez un exemple résolu comme le problème de Sunzi, le panier d'œufs ou la période julienne.
    2. Lisez la plus petite solution, le module avec lequel elle se répète et les premières solutions positives, chacune vérifiée sur chaque équation.
    3. Suivez le calcul étape par étape, par la construction ou par substitution, et passez l'image de la droite numérique à la table des restes.

    Comment fonctionne la construction

    Quand aucun couple de modules n'a de facteur commun, on peut construire la solution directement. Multipliez les modules : pour le problème de Sunzi, N = 3 × 5 × 7 = 105. Pour chaque équation, prenez Nᵢ = N / nᵢ, un multiple de tous les autres modules : 35, 21 et 15. Cherchez ensuite l'inverse yᵢ de Nᵢ mod nᵢ avec l'algorithme d'Euclide étendu : 35 laisse 2 dans la division par 3, et 2 × 2 = 4 ≡ 1 (mod 3), donc y₁ = 2 ; 21 et 15 laissent 1, leurs inverses valent donc 1. Alors x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, et 233 mod 105 = 23. Chaque terme convient à sa propre équation et est un multiple des autres modules, donc la somme convient à toutes.

    Quand les modules ont un facteur commun

    Un système dont les modules ont des facteurs communs peut quand même avoir une solution. Deux équations x ≡ a (mod m) et x ≡ b (mod n) peuvent être vraies ensemble exactement quand a − b est un multiple de gcd(m, n), et la solution se répète alors tous les lcm(m, n) au lieu de tous les m × n. Deux bus qui partent aux minutes 5 et 11, toutes les 12 et toutes les 18 minutes, se retrouvent à la minute 29 puis toutes les 36 minutes, car 11 − 5 = 6 est un multiple de gcd(12, 18) = 6. Mais x ≡ 1 (mod 4) et x ≡ 4 (mod 6) ne peuvent jamais être vraies ensemble : la première rend x impair, la seconde pair. Un système entier a une solution exactement quand chaque paire de ses équations en a une, et c'est ainsi que le solveur trouve les deux qui se contredisent.

    Questions fréquemment posées

    Que dit le théorème des restes chinois ?

    Si aucun couple parmi les modules n₁, n₂, … n'a de facteur commun, alors pour tous restes a₁, a₂, … il existe exactement un x entre 0 et N − 1 tel que x ≡ aᵢ (mod nᵢ) pour tout i, où N est le produit des modules. Toute autre solution en diffère d'un multiple de N : pour le problème de Sunzi, les solutions sont 23, 128, 233 et ainsi de suite, une tous les 105.

    Pourquoi l'appelle-t-on chinois ?

    Le plus ancien problème connu de ce genre se trouve dans le Sunzi Suanjing, un livre d'arithmétique chinois écrit entre le IIIᵉ et le Vᵉ siècle : comptés par trois, par cinq et par sept, des objets laissent 2, 3 et 2. Qin Jiushao a donné une méthode générale pour ces problèmes en 1247, et Carl Friedrich Gauss a énoncé le théorème sous sa forme moderne en 1801.

    Et si les modules ne sont pas premiers entre eux ?

    Alors il peut n'y avoir aucune solution, et s'il y en a une, elle se répète tous les plus petits communs multiples des modules au lieu de tous les produits. Deux équations concordent quand leurs restes sont égaux modulo le gcd de leurs modules. L'énigme des œufs utilise 2, 3, 4, 5, 6 et 7, qui ont des facteurs communs, et a pourtant une solution : 301, qui se répète tous les 420.

    Comment RSA utilise-t-il le théorème des restes chinois ?

    Déchiffrer un message RSA revient à calculer c^d mod n, où n = p × q. Il est plus rapide de calculer séparément c^d mod p et c^d mod q, avec l'exposant réduit mod p − 1 et q − 1, puis de réunir les deux résultats avec le théorème. Avec des nombres deux fois plus courts, chacune des deux puissances demande environ un huitième du travail, donc le déchiffrement est environ quatre fois plus rapide, et la plupart des logiciels RSA procèdent ainsi.

    Quelle taille peuvent avoir les nombres ?

    Jusqu'à 20 équations, avec des nombres d'au plus 200 chiffres chacun. Le solveur travaille avec des entiers exacts dans votre navigateur, donc la réponse est exacte quelle que soit sa longueur, et rien n'est envoyé nulle part.

    Prêt à l'essayer ?

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

    Aller à l'éditeur