Introduction
Le théorème chinois des restes est un résultat fondamental en arithmétique modulaire, nommé ainsi car il était connu des mathématiciens chinois dès le 3ème siècle après J.-C. Ce théorème permet de résoudre des systèmes d'équations de congruences simultanées et a de nombreuses applications en mathématiques et en informatique.
Énoncé du Théorème
Soit m₁, m₂, ..., mₖ des entiers positifs deux à deux premiers entre eux, et a₁, a₂, ..., aₖ des entiers quelconques. Alors le système d'équations de congruences :
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)
admet une solution unique modulo M = m₁ × m₂ × ... × mₖ.
Démonstration
La démonstration du théorème chinois des restes repose sur la construction explicite d'une solution. Voici les étapes principales :
- Calculer M = m₁ × m₂ × ... × mₖ
- Pour chaque i de 1 à k, calculer Mᵢ = M / mᵢ
- Trouver les inverses modulaires yᵢ tels que Mᵢ × yᵢ ≡ 1 (mod mᵢ)
- La solution est donnée par : x ≡ (a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ) (mod M)
Exemple d'Application
Problème
Trouver un nombre x qui satisfait les congruences suivantes :
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Solution
1. M = 3 × 5 × 7 = 105
2. M₁ = 35, M₂ = 21, M₃ = 15
3. y₁ = 2, y₂ = 1, y₃ = 1 (inverses modulaires)
4. x ≡ (2×35×2 + 3×21×1 + 2×15×1) (mod 105) ≡ 23 (mod 105)
Donc, la solution est x = 23 (ou tout nombre congru à 23 modulo 105).
Applications
Le théorème chinois des restes a de nombreuses applications, notamment :
- En cryptographie, pour le chiffrement RSA
- Dans les algorithmes de calcul de calendriers
- Pour l'optimisation de calculs en arithmétique modulaire
- Dans la théorie des codes correcteurs d'erreurs
Note importante
L'hypothèse que les modules mᵢ sont deux à deux premiers entre eux est cruciale pour l'unicité de la solution. Sans cette condition, le théorème ne s'applique pas directement, mais des généralisations existent pour traiter ces cas.
Conclusion
Le théorème chinois des restes est un outil puissant en arithmétique modulaire. Sa compréhension est essentielle pour aborder des concepts plus avancés en théorie des nombres et en algèbre abstraite. N'hésitez pas à pratiquer avec divers exemples pour consolider votre compréhension.
Pratiquer avec des exercices