Résolveur du théorème des restes chinois

Le résolveur du théorème des restes chinois prend un système de congruences simultanées — x congru à chaque reste a_i modulo chaque module n_i — et renvoie la solution unique lorsqu'elle existe. Vous fournissez des tableaux parallèles de restes et de modules ; le moteur les fusionne avec un CRT successif, vérifie la cohérence lorsque les modules partagent des facteurs, et indique à la fois le représentant x entre zéro et module moins un et le module de la classe de solution (le produit des n_i lorsqu'ils sont premiers entre eux deux à deux, sinon leur plus petit commun multiple).

Ce que renvoie le théorème des restes chinois et quand les systèmes échouent

Le célèbre triplet de classe — x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 — donne x ≡ 23 mod 105. Cet outil accepte aussi la forme générale : les modules n'ont pas besoin d'être premiers entre eux deux à deux. Classiquement, si les modules sont premiers entre eux deux à deux, il existe exactement une classe de résidu modulo le produit des n_i qui satisfait toutes les congruences à la fois. Dans ce cas, une solution existe si et seulement si chaque paire de restes s'accorde modulo le PGCD des modules correspondants, et la solution est unique modulo le plus petit commun multiple de tous les n_i. Lorsque les restes ne s'accordent pas, la requête échoue avec invalid_input et un message qui nomme l'incohérence plutôt que d'inventer un faux x. La réponse JSON en cas de succès inclut x, modulus (le module CRT de la classe de solution), product (le produit brut des modules d'entrée), les remainders réduits entre zéro et n_i moins un, une copie des moduli, et count. Cette forme est stable pour les tests de référence, les clients SDK, et les widgets de navigateur qui affichent la réponse à côté d'une liste de vérification. Des tableaux manquants, des longueurs inégales, des modules non positifs, des non-entiers, et des valeurs hors de la plage d'entiers sûrs échouent aussi avec invalid_input, afin que de mauvaises cellules de tableur ne deviennent jamais silencieusement de mauvaises réponses.

Comment les restes et les modules sont lus et comment le CRT successif reste exact

Chaque module doit être un entier sûr positif. Les restes peuvent être négatifs et sont réduits dans l'intervalle canonique avant la fusion. En interne, le moteur commence à partir de la première congruence et fusionne répétitivement la suivante : étant donné x ≡ x0 mod m et x ≡ a mod n, il calcule g égale le PGCD de m et n, rejette le système si a moins x0 n'est pas divisible par g, puis construit la solution mise à jour avec un inverse modulaire de m sur g modulo n sur g et multiplie le module par n sur g pour obtenir le nouveau PPCM. Toutes les multiplications sont protégées afin que le produit et le module CRT intermédiaire restent dans les entiers sûrs de JavaScript ; les produits surdimensionnés échouent clairement plutôt que de déborder. Les champs préférés sont remainders et moduli comme tableaux JSON d'entiers de longueur égale. Les alias a, ai, et residues correspondent à remainders ; n, ni, et mods correspondent à moduli, afin que formulaires, chaînes de requête, et notebooks hérités puissent réutiliser un même contrat. Chaque entrée peut être un entier JSON ou une chaîne décimale avec un signe initial optionnel ; les fractions, la notation scientifique, et les espaces internes sont rejetés.

Où les systèmes CRT apparaissent dans l'étude, l'intuition cryptographique et le code

Sur cette page, le travail s'exécute entièrement dans votre navigateur ; via l'API, chaque résolution réussie coûte $0.002, la validation échouée n'est pas facturée, et rien n'est stocké après le retour de la réponse.