- Methode des substitutions successives
-
Méthode des substitutions successives
En arithmétique modulaire, la méthode des substitutions successives est une méthode pour résoudre les problèmes de système de congruences en utilisant la définition de l'équation de congruence.
Par exemple, considéront le système simple de congruences
- x ≡ 3 (mod 4)
- x ≡ 5 (mod 6)
Maintenant, pour que x ≡ 3 (mod 4) soit vrai, x=3+4j pour un certain entier j. Substituons ceci dans la deuxième équation
- 3+4j ≡ 5 (mod 6)
car nous cherchons une solution pour les deux équations.
Soustrayons 3 des deux cotés (ceci est permis en arithmétique modulaire)
- 4j ≡ 2 (mod 6)
Nous simplifions en divisant par le PGCD de 4 ; 2 et 6. La division par 2 donne :
- 2j ≡ 1 (mod 3)
L'inverse euclidien de 2 mod 3 est 2. Après avoir multiplié les deux cotés par l'inverse, nous obtenons :
- j ≡ 2 × 1 (mod 3)
ou
- j ≡ 2 (mod 3)
Pour que ce qui précède soit vrai : j=2+3k pour un certain entier k. Maintenant, substituons en retour dans 3+4j et nous obtenons
- x=3+4(2+3k)
Développons en
- x=11+12k
pour obtenir la solution
- x ≡ 11 (mod 12)
En général :
- Écrire la première équation dans sa forme équivalente
- La substituer dans la suivante
- Simplifier, utiliser l'inverse si nécessaire
- Continuer jusqu'à la dernière équation
- Substituer en retour, puis simplifier
- Réécrire en retour dans la forme congruente
Si les modules sont premiers entre eux, le théorème des restes chinois donne une formule directe pour obtenir la solution.liens internes
Catégorie : Théorie algorithmique des nombres
Wikimedia Foundation. 2010.
