Méthode des substitutions successives

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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[modifier | modifier le code]