Calculateur du théorème des restes chinois

Q: Comment résoudre un système de congruences à la main sans utiliser la formule du TRC ?

Pour deux congruences, vous pouvez procéder par substitution : partez de la première et écrivez x = a₁ + k·n₁ pour un entier k. Remplacez x dans la seconde congruence, a_1 + k n_1 equiv a_2 ±odn_2, puis trouvez k à l’aide de l’inverse de n_1 modulo n_2. Remplacez ensuite k pour obtenir x, puis réduisez le résultat modulo n_1 n_2. Cette méthode de substitutions successives fonctionne pour un nombre quelconque de congruences, en les résolvant deux par deux.

Q: Que se passe-t-il si les modules ne sont pas premiers entre eux deux à deux ?

Lorsque deux modules ont un facteur commun, le système peut être incompatible et n’avoir aucune solution. Une solution n’existe que si les restes sont compatibles : pour chaque paire, a_i equiv a_j ±odgcd(n_i, n_j). S’ils sont compatibles, la solution reste unique, mais seulement modulo le plus petit commun multiple des modules, et non leur produit. La condition de coprimalité garantit qu’une solution existe toujours ; c’est pourquoi ce calculateur rejette de telles saisies.

Q: Pourquoi la solution est-elle unique et comment trouver toutes les autres solutions ?

L’unicité vient du fait que, si deux nombres x et x' satisfont tous deux le système, leur différence est divisible par chaque module et donc par leur produit N (puisqu’ils sont premiers entre eux). Ainsi, x equiv x' ±odN, ce qui signifie qu’il existe exactement une solution dans l’intervalle 0 ≤ x < N. Toutes les autres solutions sont de la forme x + kN, pour tout entier k, y compris des valeurs négatives comme x - N si votre problème les autorise.

Q: Les restes peuvent-ils être négatifs ou supérieurs au module ?

Oui. Un reste supérieur à son module est automatiquement réduit : par exemple, a = 7 avec n = 5 revient à prendre a = 2. Les restes négatifs fonctionnent aussi : x equiv -1 ±od5 équivaut à x equiv 4 ±od5. La réponse finale est toujours ramenée au plus petit représentant non négatif, dans l’intervalle 0 ≤ x < N.

Q: Comment trouver un inverse modulaire à la main ?

Utilisez l’algorithme d’Euclide étendu : appliquez d’abord l’algorithme d’Euclide ordinaire à N_i et n_i, puis remontez les calculs pour exprimer gcd = 1 sous la forme uN_i + vn_i. Le coefficient u vérifie uN_i equiv 1 ±odn_i, donc y_i = u bmod n_i. Pour un module premier p, vous pouvez aussi utiliser le petit théorème de Fermat : y_i equiv N_i^p-2 ±odp.

Q: Quelles sont les erreurs fréquentes lorsqu’on utilise le théorème des restes chinois ?

Les erreurs les plus fréquentes consistent à utiliser des modules qui ne sont pas premiers entre eux deux à deux (par exemple 4 et 6, qui ont le facteur 2 en commun), à intervertir les champs « reste » et « module » lors de la saisie, à oublier que la réponse est une classe de solutions et non un nombre unique, ou à saisir un module égal à 1, ce qui est techniquement autorisé mais n’apporte aucune information. Vérifiez aussi que vos restes correspondent bien à votre problème : x equiv 2 ±od3 n’est pas la même chose que x equiv 3 ±od2.

Q: Existe-t-il un moyen rapide de vérifier la réponse du calculateur ?

Oui : divisez simplement la réponse par chaque module et vérifiez les restes. Si le résultat est x, vérifiez que x bmod n_i = a_i bmod n_i pour chaque congruence de votre système. Pour une deuxième vérification, calculez x bmod N par une autre méthode, comme les substitutions successives, et assurez-vous d’obtenir la même valeur. Si les deux vérifications réussissent, la solution est correcte, puisque l’unicité modulo N garantit qu’il n’existe aucune autre réponse dans l’intervalle.

Mis à jour : 03.10.2026

Résout un système de congruences simultanées à l’aide du théorème des restes chinois. Saisissez les restes et les modules premiers entre eux deux à deux pour obtenir la plus petite solution non négative.

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

Formule du théorème des restes chinois

Formule

\[ x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \\[1.5em] N = n_1 \cdot n_2 \cdots n_k, \quad N_i = \frac{N}{n_i}, \quad y_i \equiv N_i^{-1} \pmod{n_i} \\[1.5em] x \equiv \sum_{i=1}^{k} a_i \, N_i \, y_i \pmod{N} \]

Où :

\(a_i\) — les restes (les valeurs auxquelles \(x\) doit être congru)
\(n_i\) — les modules, qui doivent être premiers entre eux deux à deux (le plus grand commun diviseur de deux quelconques d’entre eux est 1)
\(N\) — le produit de tous les modules, égal à leur plus petit commun multiple lorsqu’ils sont premiers entre eux
\(N_i\) — le produit de tous les modules sauf \(n_i\)
\(y_i\) — l’inverse modulaire de \(N_i\) modulo \(n_i\), c’est-à-dire le nombre tel que \(N_i y_i \equiv 1 \pmod{n_i}\)
\(x\) — l’unique solution modulo \(N\)

Le théorème affirme que, lorsque les modules sont premiers entre eux deux à deux, le système admet exactement une solution dans l’intervalle \(0 \le x < N\). La formule construit cette solution en associant chaque reste à l’inverse du produit partiel correspondant.

Théorème des restes chinois – exemple de calcul

Exemple : trouver \(x\) tel que \(x \equiv 2 \pmod{3}\) et \(x \equiv 3 \pmod{5}\) — ce sont les valeurs par défaut du calculateur.

\[ N = 3 \times 5 = 15 \]

\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{car } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]

\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{car } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]

\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]

Résultat : \(x = 8\) modulo \(15\). En effet, la division de \(8\) par \(3\) donne un quotient de \(2\) et un reste de \(2\), tandis que la division de \(8\) par \(5\) donne un quotient de \(1\) et un reste de \(3\) : les deux congruences sont donc vérifiées. La solution suivante est \(8 + 15 = 23\), puis \(38\), et ainsi de suite.

Comment utiliser le calculateur

Saisissez le Nombre de congruences (au moins 2). D’autres paires reste/module apparaissent automatiquement.
Pour la première congruence, saisissez le reste dans reste 1 (\(a_1\)) et le module dans module 1 (\(n_1\)).
Faites de même pour reste 2 / module 2 et pour toute paire supplémentaire.
Lisez la Plus petite solution non négative \(x\) et le Modulo (PPCM des modules) \(N\). Tout nombre de la forme \(x + kN\) (\(k = 0, 1, 2, \dots\)) satisfait également le système.

Qu’est-ce que le théorème des restes chinois ?

Le théorème des restes chinois (TRC) est un résultat classique de la théorie des nombres, décrit pour la première fois par le mathématicien chinois Sunzi vers le IIIe–Ve siècle de notre ère. Il répond à la question suivante : étant donné plusieurs diviseurs et les restes de la division d’un nombre inconnu par chacun d’eux, peut-on retrouver ce nombre ? Le théorème dit que oui — à condition que les modules soient premiers entre eux deux à deux — et que la réponse est unique dans un intervalle dont la longueur est le produit de tous les modules.

Voici une façon concrète de se le représenter : si un panier contient \(x\) œufs, qu’il en reste 2 lorsqu’on les compte par groupes de 3 et 3 lorsqu’on les compte par groupes de 5, alors \(x \equiv 2 \pmod{3}\) et \(x \equiv 3 \pmod{5}\). Le TRC détermine \(x\) de manière unique modulo 15 — dans ce cas, \(x = 8, 23, 38, \dots\)

Ce théorème est important parce qu’il montre qu’un système de nombreuses congruences à petits modules équivaut à une seule congruence à grand module. On peut ainsi remplacer des calculs avec un très grand module par des calculs parallèles avec plusieurs petits modules plus pratiques, puis recombiner les résultats. Cette recombinaison utilise des inverses modulaires, que vous pouvez calculer séparément avec le calculateur d’inverse multiplicatif modulo ; les inverses de ce type sont également liés au petit théorème de Fermat et au théorème d’Euler.

Interpréter le résultat

Le calculateur renvoie la plus petite solution non négative \(x\) et le module combiné \(N\). L’ensemble des solutions est \(x, x + N, x + 2N, \dots\) et, si les réponses négatives ont un sens dans votre problème, \(x - N\) et les valeurs inférieures conviennent aussi. Puisque la solution est unique modulo \(N\), deux saisies différentes qui produisent le même \(x \pmod{N}\) décrivent exactement le même système.

Hypothèses et limites

Les modules doivent être premiers entre eux deux à deux. Aucun couple de modules ne doit avoir de facteur commun supérieur à 1 ; sinon, le calculateur signale une erreur. Si deux modules valent, par exemple, 4 et 6 (tous deux divisibles par 2), le système peut n’avoir aucune solution ou avoir plusieurs solutions modulo leur PPCM.
Compatibilité du système. Lorsque les modules sont premiers entre eux, le théorème donne toujours une solution : c’est tout l’intérêt du TRC. Des contradictions entre les congruences ne peuvent apparaître que si la condition de coprimalité n’est pas respectée.
Les restes peuvent dépasser le module. Une saisie telle que \(a = 7, n = 5\) est interprétée comme \(7 \equiv 2 \pmod 5\) ; le calculateur réduit automatiquement la réponse finale modulo \(N\).
Les modules doivent être des entiers positifs. La valeur 0 et les nombres négatifs sont rejetés.
Grands systèmes. Comme \(N\) est le produit de tous les modules, il croît très vite. Avec de nombreux modules, les nombres en jeu peuvent dépasser la plage dans laquelle les calculs standard en virgule flottante sont exacts.

Applications du TRC

Au-delà de la théorie pure des nombres, le TRC est un outil utilisé dans plusieurs domaines. En cryptographie, il accélère le déchiffrement RSA en calculant séparément le résultat modulo chaque facteur premier, puis en recombinant les résultats ; il sous-tend également des schémas à seuil comme le partage de secret de Shamir. En informatique, il permet de créer des systèmes de numération résiduelle qui effectuent des additions et des multiplications en parallèle sur de petits modules. On le retrouve aussi dans le hachage, la planification et les calculs calendaires — ainsi que dans les problèmes classiques de « comptage de soldats par rangées » qui ont initialement motivé les travaux de Sunzi.

Questions fréquentes

Comment résoudre un système de congruences à la main sans utiliser la formule du TRC ?

Pour deux congruences, vous pouvez procéder par substitution : partez de la première et écrivez x = a₁ + k·n₁ pour un entier \(k\). Remplacez \(x\) dans la seconde congruence, \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\), puis trouvez \(k\) à l’aide de l’inverse de \(n_1\) modulo \(n_2\). Remplacez ensuite \(k\) pour obtenir \(x\), puis réduisez le résultat modulo \(n_1 n_2\). Cette méthode de substitutions successives fonctionne pour un nombre quelconque de congruences, en les résolvant deux par deux.

Que se passe-t-il si les modules ne sont pas premiers entre eux deux à deux ?

Lorsque deux modules ont un facteur commun, le système peut être incompatible et n’avoir aucune solution. Une solution n’existe que si les restes sont compatibles : pour chaque paire, \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). S’ils sont compatibles, la solution reste unique, mais seulement modulo le plus petit commun multiple des modules, et non leur produit. La condition de coprimalité garantit qu’une solution existe toujours ; c’est pourquoi ce calculateur rejette de telles saisies.

Pourquoi la solution est-elle unique et comment trouver toutes les autres solutions ?

L’unicité vient du fait que, si deux nombres \(x\) et \(x'\) satisfont tous deux le système, leur différence est divisible par chaque module et donc par leur produit \(N\) (puisqu’ils sont premiers entre eux). Ainsi, \(x \equiv x' \pmod{N}\), ce qui signifie qu’il existe exactement une solution dans l’intervalle \(0 \le x < N\). Toutes les autres solutions sont de la forme \(x + kN\), pour tout entier \(k\), y compris des valeurs négatives comme \(x - N\) si votre problème les autorise.

Les restes peuvent-ils être négatifs ou supérieurs au module ?

Oui. Un reste supérieur à son module est automatiquement réduit : par exemple, \(a = 7\) avec \(n = 5\) revient à prendre \(a = 2\). Les restes négatifs fonctionnent aussi : \(x \equiv -1 \pmod{5}\) équivaut à \(x \equiv 4 \pmod{5}\). La réponse finale est toujours ramenée au plus petit représentant non négatif, dans l’intervalle \(0 \le x < N\).

Comment trouver un inverse modulaire à la main ?

Utilisez l’algorithme d’Euclide étendu : appliquez d’abord l’algorithme d’Euclide ordinaire à \(N_i\) et \(n_i\), puis remontez les calculs pour exprimer \(\gcd = 1\) sous la forme \(uN_i + vn_i\). Le coefficient \(u\) vérifie \(uN_i \equiv 1 \pmod{n_i}\), donc \(y_i = u \bmod n_i\). Pour un module premier \(p\), vous pouvez aussi utiliser le petit théorème de Fermat : \(y_i \equiv N_i^{p-2} \pmod{p}\).

Quelles sont les erreurs fréquentes lorsqu’on utilise le théorème des restes chinois ?

Les erreurs les plus fréquentes consistent à utiliser des modules qui ne sont pas premiers entre eux deux à deux (par exemple 4 et 6, qui ont le facteur 2 en commun), à intervertir les champs « reste » et « module » lors de la saisie, à oublier que la réponse est une classe de solutions et non un nombre unique, ou à saisir un module égal à 1, ce qui est techniquement autorisé mais n’apporte aucune information. Vérifiez aussi que vos restes correspondent bien à votre problème : \(x \equiv 2 \pmod{3}\) n’est pas la même chose que \(x \equiv 3 \pmod{2}\).

Existe-t-il un moyen rapide de vérifier la réponse du calculateur ?

Oui : divisez simplement la réponse par chaque module et vérifiez les restes. Si le résultat est \(x\), vérifiez que \(x \bmod n_i = a_i \bmod n_i\) pour chaque congruence de votre système. Pour une deuxième vérification, calculez \(x \bmod N\) par une autre méthode, comme les substitutions successives, et assurez-vous d’obtenir la même valeur. Si les deux vérifications réussissent, la solution est correcte, puisque l’unicité modulo \(N\) garantit qu’il n’existe aucune autre réponse dans l’intervalle.