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

• Système d'équations
• algèbre

Ce document provient de « M%C3%A9thode des substitutions successives ».