Outil pour appliquer le théorème des restes chinois. Le théorème des restes chinois permet de résoudre des systèmes d'équations de congruences en arithmétique modulaire.
Restes Chinois - dCode
Catégorie(s) : Arithmétique
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Restes Chinois
Calculatrice de Restes Chinois
Réponses aux Questions (FAQ)
Qu'est-ce que le théorème des restes chinois ? (Définition)
Le théorème des restes chinois est le nom donné à un système de congruences simultanées (équations modulaires multiples). Le problème original consiste à considérer un certain nombre d'éléments dont les restes de leurs divisions euclidiennes sont connus.
Exemple : Rangés par 3 il en reste 2. Rangés par 5, il en reste 3 et rangés par 7, il en reste 2. Combien ai-je d'objets ? Cet exercice revient à calculer $ x $ tel que $ x \equiv 2 \mod 3 $ et $ x \equiv 3 \mod 5 $ et $ x \equiv 2 \mod 7 $
Soient une liste de $ k $ entiers $ n_1, ..., n_k $ premiers entre eux et leur produit $ n = \prod_{i=1}^k n_i $. Pour tous entiers $ a_1, ... , a_k $, il existe un autre entier $ x $ qui est unique modulo $ n $, tel que :
$$ \begin{array}{c} x \equiv a_1\pmod{n_1} \\ \ldots \\ x \equiv a_k\pmod{n_k} \end{array} $$
Comment calculer les restes chinois ?
Pour trouver une solution au système de congruences, considérer les nombres $ \hat{n}_i = \frac n{n_i} = n_1 \ldots n_{i-1}n_{i+1}\ldots n_k $ qui sont aussi premiers entre eux. Pour trouver les inverses modulaires, utiliser le théorème de Bézout pour trouver des entiers $ u_i $ et $ v_i $ tels que $ u_i n_i + v_i \hat{n}_i = 1 $. Ici, $ v_i $ est l'inverse de $ \hat{n}_i $ modulo $ n_i $.
Considérer alors les nombres $ e_i = v_i \hat{n}_i \equiv 1 \mod{n_i} $. Une solution particulière du théorème des restes chinois est $$ x = \sum_{i=1}^k a_i e_i $$
Le programme accepte les nombres sous forme de couples (reste A, modulo B) dans les équations de la forme x = A mod B
Exemple : $ (2,3),(3,5),(2,7) \iff \left\{ \begin{array}{ll} x = 2 \mod 3 \\ x = 3 \mod 5 \\ x = 2 \mod 7 \end{array} \right. \Rightarrow x = 23 $
Quand le théorème des restes chinois n'a-t-il pas de solution?
Le système d'équation avec des restes $ r_i $ et des modulos $ m_i $ a des solutions uniquement si l'équation modulaire suivante est vérifiée : $$ r_1 \mod d = r_2 \mod d = \cdots r_n \mod d $$ avec $ d $ le PGCD de tous les modulos $ m_i $.
Code source
dCode se réserve la propriété du code source pour "Restes Chinois". Tout algorithme pour "Restes Chinois", applet ou snippet ou script (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toutes fonctions liées à "Restes Chinois" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou toute base de données, ou accès API à "Restes Chinois" ou tout autre élément ne sont pas publics (sauf licence open source explicite type Creative Commons). Idem avec le téléchargement pour un usage hors ligne sur PC, mobile, tablette, appli iPhone ou Android.
Rappel : dCode est une ressource éducative et pédagogique, accessible en ligne gratuitement et pour tous.
Citation
Le contenu de la page "Restes Chinois" ainsi que ses résultats peuvent être copiés et réutilisés librement, y compris à des fins commerciales, à condition de mentionner dCode.fr comme source.
L'export des résultats est gratuit et se fait simplement en cliquant sur les icônes d'export ⤓ (format .csv ou .txt) ou ⧉ copier-coller.
Pour citer dCode.fr sur un autre site Internet, utiliser le lien :
Dans un article scientifique ou un livre, la citation bibliographique recommandée est : Restes Chinois sur dCode.fr [site web en ligne], consulté le 26/04/2025,
