Calculateur du théorème des restes chinois

Le théorème des restes chinois, souvent abrégé CRT en anglais, réunit plusieurs conditions modulaires en une solution. Une congruence telle que x ≡ 2 modulo 3 signifie que la division de x par 3 laisse un reste de 2. Ce calculateur accepte trois équations de ce type et trouve le plus petit entier positif ou nul qui les satisfait simultanément. Le théorème classique s'applique lorsque les modules sont premiers entre eux deux à deux, c'est-à-dire que chaque paire a un plus grand commun diviseur égal à un. Il existe alors exactement une solution modulo le produit des modules. Pour les modules 3, 5 et 7, ce produit vaut 105. Si la plus petite solution est 23, alors 23, 128, 233 et tous les nombres obtenus en ajoutant ou en retranchant 105 satisfont le même système. L'algorithme constructif commence par multiplier tous les modules pour former M. Pour chaque équation, il divise M par le module de cette équation afin d'obtenir un produit partiel. Comme les modules sont premiers entre eux deux à deux, ce produit possède un inverse multiplicatif modulo le module omis. Multiplier chaque reste, produit partiel et inverse crée un terme qui satisfait une congruence tout en valant zéro pour les autres. La somme des termes, réduite modulo M, donne la réponse. Le CRT s'applique bien au-delà de la théorie des nombres scolaire. Il permet des calculs efficaces sur de grands entiers et intervient en cryptographie, théorie des codes, cycles calendaires, plannings tournants, calcul formel et reconstruction de valeurs à partir de restes. Il est particulièrement utile lorsqu'un calcul difficile peut être décomposé en calculs plus petits et indépendants modulo plusieurs nombres, puis recombiné. Saisissez des restes entiers et des modules supérieurs à un. Un reste peut être négatif ou dépasser son module, car la réduction le normalise automatiquement. Cette version exige volontairement des modules premiers entre eux deux à deux pour suivre le théorème standard et garantir une classe de congruence unique. Certains systèmes aux modules non premiers entre eux ont une solution, mais ils nécessitent un contrôle de compatibilité supplémentaire et ne sont pas pris en charge. Vérifiez toujours le résultat en le divisant par chaque module et en contrôlant le reste.