Calculatrice du Théorème des Restes Chinois

Bienvenue sur la Calculatrice du théorème des restes chinois, un puissant outil de théorie des nombres qui résout des systèmes de congruences simultanées à l'aide du théorème des restes chinois (TRC). Que vous étudiiez l'arithmétique modulaire, que vous vous prépariez à des concours de mathématiques, que vous travailliez sur des problèmes de cryptographie ou que vous exploriez la théorie des nombres, cette calculatrice fournit une solution complète étape par étape avec une visualisation interactive montrant comment les classes de congruence s'alignent sur la solution unique.

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

Le théorème des restes chinois (TRC) est un résultat fondamental de la théorie des nombres qui garantit l'existence et l'unicité d'une solution à un système de congruences simultanées, à condition que les modules soient deux à deux premiers entre eux. Le théorème a été décrit pour la première fois par le mathématicien chinois Sunzi (孫子) dans son ouvrage Sunzi Suanjing (孫子算經) vers le 3ème siècle de notre ère.

Formellement, étant donné le système :

Si tous les modules \(m_1, m_2, \ldots, m_k\) sont deux à deux premiers entre eux (c'est-à-dire que \(\gcd(m_i, m_j) = 1\) pour tout \(i \neq j\)), alors il existe une solution unique \(x\) modulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

Comment fonctionne l'algorithme du TRC

La preuve constructive fournit l'algorithme utilisé par cette calculatrice :

Étape 1 : Calculer M

Calculer le produit de tous les modules :

Étape 2 : Calculer chaque Mᵢ

Pour chaque congruence \(i\), calculez \(M_i = M / m_i\). C'est le produit de tous les modules sauf \(m_i\).

Étape 3 : Trouver les inverses modulaires

Pour chaque \(i\), trouvez \(y_i\) tel que \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) à l'aide de l'algorithme d'Euclide étendu. Comme \(M_i\) et \(m_i\) sont premiers entre eux (tous les modules sont deux à deux premiers entre eux), cet inverse existe toujours.

Étape 4 : Construire la solution

La solution générale est \(x + k \cdot M\) pour tout entier \(k\), ce qui signifie que la solution se répète tous les \(M\) entiers.

Comment utiliser cette calculatrice

1. Saisissez vos congruences : Pour chaque équation \(x \equiv a \pmod{m}\), entrez le reste \(a\) et le module \(m\). Commencez avec 2 congruences et cliquez sur « Ajouter une congruence » pour en obtenir davantage (jusqu'à 10).
2. Vérifiez vos modules : Tous les modules doivent être des entiers positifs ≥ 2 et deux à deux premiers entre eux. La calculatrice vérifie cela automatiquement.
3. Cliquez sur « Résoudre le système » : La calculatrice applique l'algorithme du TRC et affiche la solution unique ainsi que le travail étape par étape.
4. Examinez la visualisation : La droite numérique montre comment les classes de congruence de chaque équation se croisent à la solution.
5. Vérifier : La section de vérification confirme que la solution satisfait chaque congruence d'origine.

Comprendre les résultats

• Plus petite solution non négative (x₀) : La solution unique dans l'intervalle [0, M−1]
• Solution générale : Tous les entiers de la forme x₀ + kM où k est n'importe quel entier
• Tableau de vérification : Confirme que x₀ mod mᵢ = aᵢ pour chaque congruence
• Décomposition étape par étape : Affiche Mᵢ, l'inverse modulaire yᵢ et la somme partielle aᵢ·Mᵢ·yᵢ pour chaque équation
• Droite numérique : Représentation visuelle de la façon dont les classes de restes s'alignent sur la solution

Applications du théorème des restes chinois

Le problème classique de Sunzi

Le problème original du Sunzi Suanjing demande : « Il y a certaines choses dont le nombre est inconnu. Si on les compte par trois, il en reste deux ; par cinq, il en reste trois ; et par sept, il en reste deux. Combien y a-t-il de choses ? »

Cela se traduit par : \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). En utilisant le TRC, la réponse est x = 23 (et plus généralement, 23 + 105k pour tout entier non négatif k).

Quand le TRC ne s'applique-t-il pas ?

• Modules non premiers entre eux : Si une paire de modules partage un facteur commun supérieur à 1, le TRC standard ne garantit pas de solution. Une solution peut encore exister si les restes sont compatibles, mais cette calculatrice nécessite des modules deux à deux premiers entre eux pour l'algorithme standard.
• Congruence unique : Le TRC nécessite au moins 2 congruences. Une seule congruence \(x \equiv a \pmod{m}\) possède déjà la solution triviale x = a.

Algorithme d'Euclide étendu

L'algorithme d'Euclide étendu est essentiel pour le TRC car il permet de trouver l'inverse modulaire. Étant donné des entiers \(a\) et \(b\), il trouve des entiers \(x\) et \(y\) tels que :

Quand \(\gcd(a, b) = 1\), alors \(x\) est l'inverse modulaire de \(a\) modulo \(b\), c'est-à-dire \(a \cdot x \equiv 1 \pmod{b}\).

Foire aux questions

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

Le théorème des restes chinois (TRC) stipule que si vous avez un système de congruences simultanées x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), où tous les modules sont deux à deux premiers entre eux, alors il existe une solution unique modulo M = m₁ × m₂ × ... × mₖ. Ce théorème a été décrit pour la première fois par le mathématicien chinois Sunzi au 3ème siècle.

Que signifie deux à deux premiers entre eux ?

Cela signifie que chaque paire de modules ne partage aucun facteur commun autre que 1. Par exemple, {3, 5, 7} sont deux à deux premiers entre eux car pgcd(3,5)=1, pgcd(3,7)=1 et pgcd(5,7)=1. Cependant, {4, 6, 5} ne le sont PAS car pgcd(4,6)=2.

Comment résoudre un système de congruences étape par étape ?

Pour résoudre avec le TRC : (1) Vérifier que tous les modules sont deux à deux premiers entre eux. (2) Calculer M = produit de tous les modules. (3) Pour chaque congruence, calculer Mᵢ = M/mᵢ. (4) Trouver l'inverse modulaire yᵢ de Mᵢ modulo mᵢ à l'aide de l'algorithme d'Euclide étendu. (5) Calculer la solution x = Σ(aᵢ × Mᵢ × yᵢ) mod M. La solution générale est x + k×M pour tout entier k.

Quelles sont les applications du théorème des restes chinois ?

Le TRC a de nombreuses applications pratiques : la cryptographie RSA l'utilise pour un déchiffrement efficace. L'informatique l'utilise pour l'arithmétique sur de grands nombres en divisant les calculs en morceaux modulaires plus petits. Le traitement du signal applique le TRC dans les codes correcteurs d'erreurs. Les problèmes de planification et de calendrier où les événements se répètent à des intervalles différents utilisent également le TRC.

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

Si les modules ne sont pas deux à deux premiers entre eux, le TRC standard ne s'applique pas directement. Dans certains cas, une solution peut encore exister si certaines conditions de compatibilité sont remplies (les restes doivent être cohérents modulo le PGCD des modules non premiers entre eux). Cependant, si aucune solution n'existe, le système de congruences est incohérent.

Ressources additionnelles

• Théorème des restes chinois - Wikipédia
• Algorithme d'Euclide étendu - Wikipédia
• Arithmétique modulaire - Wikipédia