Résolution modulo $p$

Énoncé

Résoudre l'équation 5x 2 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^{-1} 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 x = 7k + 6,\ k Z

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.