Petit théorème de Fermat et calculs d'inverses modulo p

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Si p est premier et ne divise pas a : a^p-1 1 p. • Pour tout entier a : a^p a p. • Si p ne divise pas a, l'inverse de a modulo p est a^p-2, réduit modulo p. • Pour calculer a^n modulo p, on réduit l'exposant n modulo p - 1.

Le cours

1. Petit théorème de Fermat Soit p un nombre premier. p a a^p-1 1 p et, pour tout a, a^p a p La seconde forme découle de la première (multiplier par a) et reste vraie quand p divise a, car alors les deux membres sont congrus à 0. 2. Inverse modulo p Si p ne divise pas a, il existe un entier u tel que au 1 p ; il est unique modulo p et s'appelle un inverse de a modulo p. Fermat en fournit un : a a^p-2 = a^p-1 1 p. Exemple : 3^5 = 243 = 7 34 + 5, donc 5 est l'inverse de 3 modulo 7 ; en effet 3 5 = 15 1 7. 3. Méthode pour réduire une grande puissance 1. Vérifier que p est premier et ne divise pas a. 2. Diviser l'exposant par p - 1 : n = (p - 1)q + r avec 0 r 3. Conclure : a^n = (a^p-1)^q a^r a^r p. Exemple : 50 = 6 8 + 2, donc 2^50 2^2 = 4 7. 4. Pour résoudre ax b p, multiplier les deux membres par l'inverse de a. 4. Attention Les hypothèses comptent : 9 n'est pas premier et 2^8 = 256 4 9, pas 1 ; de même 7^6 0 7, car 7 divise 7.

Dans ce chapitre