Résolution modulo p

Énoncé

Résoudre l'équation 5x ≡ 2 (mod 7).

Indice : Comme 7 est premier et 7 ∤ 5, 5 admet un inverse modulo 7. Utilise le petit théorème de Fermat pour le calculer.

Correction

  1. Étape 1 : Résoudre 5x ≡ 2, c'est « diviser par 5 » — sauf qu'on ne divise pas dans les congruences. On multiplie par l'inverse de 5, c'est-à-dire le nombre qui, multiplié par 5, donne 1. Existence de l'inverse : a admet un inverse modulo n si et seulement si PGCD(a, n) = 1.
  2. Étape 2 : L'inverse existe, car 7 est premier et ne divise pas 5.
  3. Étape 3 : On le cherche par balayage, ce qui demande six essais au plus :

    5 × 1 ≡ 5 5 × 2 ≡ 3 5 × 3 = 15 ≡ 1 7

  4. Étape 4 : Donc l'inverse de 5 est 3 :

    5⁻¹ ≡ 3 7

  5. Étape 5 : Une seconde voie, en une ligne. Modulo 7, on a 5 ≡ -2. Or (-2) × 3 = -6 ≡ 1, car -6 + 7 = 1. On retrouve 3 sans aucun essai. Remplacer un nombre par son représentant négatif est souvent le meilleur raccourci de tout le chapitre.
  6. Étape 6 : On multiplie l'équation par 3, ce qui isole x :

    3 × 5x ≡ 3 × 2 ⟹ 15x ≡ 6 ⟹ x ≡ 6 7

  7. Étape 7 : Vérification dans l'équation de départ, jamais dans une ligne intermédiaire :

    5 × 6 = 30 = 7 × 4 + 2 ≡ 2 7 ✓

  8. Étape 8 : L'ensemble des solutions n'est pas un nombre mais une classe entière :

    x ≡ 6 7 soit x = 7k + 6, k ∈ ℤ

  9. Étape 9 : On ne divise JAMAIS une congruence : « 5x ≡ 2 donc x ≡ 2/5 » n'a aucun sens : 2/5 n'est pas un entier. Et diviser par un nombre non inversible est franchement faux : modulo 6, de 2x ≡ 4 on ne peut PAS déduire x ≡ 2 — il y a deux solutions, 2 et 5. Une congruence a une infinité de solutions : x = 6 n'est qu'un représentant : 13, 20, -1 conviennent aussi. Répondre « x = 6 » est incomplet ; la réponse est la classe x ≡ 6 7.