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 : 7 est premier et 7 5, donc 5 admet un inverse modulo 7.
2. Étape 2 : Par le petit théorème de Fermat : 5^6 1 7, donc 5^{-1} 5^5 7.
3. Étape 3 : 5^2 = 25 4 7, 5^3 = 5^2 5 4 5 = 20 6 7, 5^5 = 5^3 5^2 6 4 = 24 3 7.
4. Étape 4 : Donc 5^{-1} 3 7. Vérification : 5 3 = 15 1 7 ✓
5. Étape 5 : Ainsi x 2 3 = 6 7, soit x 6 7 ou encore x = 7k + 6 pour k Z.

   x 6 7