- Méthode des substitutions successives
-
En mathématiques, la méthode des substitutions successives est une méthode de résolution pour des problèmes de système de congruences en arithmétique modulaire.
Exemple
Par exemple, considérons 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 côté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 côté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
Wikimedia Foundation. 2010.
