Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Théorème de congruence linéaire

En arithmétique modulaire, la question des conditions de résolution d'une congruence linéaire est 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

ax ≡ b (mod n)      (1)

possède une solution si et seulement si le PGCD de (a, n) divise b.

Par exemple, il n'y a pas d'entier x vérifiant la relation suivante :

4x ≡ 3 (mod 6)

mais il existe un entier x qui vérifie :

4x ≡ 2 (mod 6).

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.

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.

Voir aussi Théorème des restes chinois.