Théorème de congruence linéaire

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

En arithmétique modulaire, la question des conditions de résolution d'une congruence linéaire peut être résolue par le théorème de congruence linéaire. Si a et b sont des entiers quelconques et n un entier positif, alors la congruence

axb (mod n)      (1)

possède une solution si et seulement si le PGCD d de (a, n) divise b. Lorsque c'est le cas, et x0 est une solution de (1), alors l'ensemble de toutes les solutions est donné par

\left\{\left.x_0+k\frac{n}{d}\right|k\in\Bbb{Z}\right\}.

En particulier, il existera exactement d solutions dans l'ensemble des résidus {0, 1, 2, … , n − 1}.

Exemples[modifier | modifier le code]

  • Il n'y a pas d'entier x vérifiant 4x ≡ 3 (mod 6), car le pgcd de (4,6) est égal à 2 qui ne divise pas 3.
  • L'équation ax ≡ 2 (mod 6) avec différentes valeurs de a donne
    • 3x ≡ 2 (mod 6) où d = pgcd(3,6) = 3 mais puisque 3 ne divise pas 2, il n'existe pas de solution.
    • 5x ≡ 2 (mod 6) : ici d = pgcd(5,6) = 1, qui divise b quelconque, et donc il existe une unique solution dans {0,1,2,3,4,5} : x = 4.
    • 4x ≡ 2 (mod 6) : ici d = pgcd(4,6) = 2, qui divise 2, et donc il existe exactement deux solutions dans {0,1,2,3,4,5} : x = 2 et x = 5.

Résoudre une congruence linéaire[modifier | modifier le code]

Si le PGCD d de a et de n divise b, alors nous pouvons trouver une solution x à la congruence (1) : l'algorithme d'Euclide étendu nous fournit les entiers r et s qui vérifient la relation ra + sn = d. Alors x = rb/d est la solution. Les autres solutions sont les nombres congrus à x modulo n/d.

Par exemple, la congruence

12x ≡ 20 (mod 28)

possède comme solution pgcd (12, 28) = 4, qui divise 20. L'algorithme d'Euclide étendu donne (−2)×12 + 1×28 = 4, ce qui donne r = −2 et s = 1. Par conséquent, la solution est x = −2×20/4 = −10. Toutes les autres solutions sont congrues à −10 modulo 7 : elles sont donc toutes congrues à 4 modulo 7.

Système de congruences linéaires[modifier | modifier le code]

Par répétition de l'usage du théorème des congruences linéaires, nous pouvons aussi résoudre les systèmes de congruence linéaire, comme dans l'exemple suivant :

Trouver tous les entiers x qui vérifient les relations suivantes :
2x ≡ 2 (mod 6)
3x ≡ 2 (mod 7)
2x ≡ 4 (mod 8)

Par la résolution de la première congruence en utilisant la méthode exposée ci-dessus, nous trouvons x ≡ 1 (mod 3), qui peut être aussi écrit comme x = 3k + 1. En substituant cela dans la deuxième congruence et en simplifiant, nous obtenons

9k ≡ −1 (mod 7)

La résolution de cette congruence fournit k ≡ 3 (mod 7), ou k = 7l + 3. Il s'ensuit ceci x = 3 (7l + 3) + 1 = 21l + 10. En substituant ceci dans la troisième congruence et en simplifiant, nous obtenons

42l ≡ −16 (mod 8)

qui possède la solution l ≡ 0 (mod 4), ou l = 4m. Ceci nous donne x = 21(4m) + 10 = 84m + 10, ou

x ≡ 10 (mod 84)

qui donne toutes les solutions de ce système.

Article détaillé : Théorème des restes chinois.


(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Linear congruence theorem » (voir la liste des auteurs)