Ordre et racines primitives modulo p
Dans tout le problème, p désigne un nombre premier.
Ordre d'un entier modulo p
Soit x
. On appelle ordre de x modulo p le plus petit entier i
1 tel que xi
1 (p)
(s'il existe).
1. Quels sont les entiers relatifs qui possèdent un ordre modulo p ? Montrer que leur
ordre est inférieur ou égal à p- 1.
2. Déterminer l'ordre modulo 7 de tous les entiers relatifs (sous réserve d'existence).
3. Soit x un entier d'ordre r modulo p.
a. Montrer que la suite (xk)k
est périodique modulo p et déterminer sa plus petite période.
b. Quels sont les entiers k
tels que xk
1 (p) ?
c. Montrer que pour tous k,l
, on a xk
xl (p) si et seulement si k
l (r).
d. Déterminer, pour tout k 
, l'ordre de xk modulo p (en fonction de k et r).
Indication. On pourra commencer par examiner les entiers k premiers avec r.
4. a. On note (
/p
)* =
/p
\ {0}.
Vérifier que ((
/p
)*,
)est un groupe
et que l'application
: (
(
/p
)*)
(k
xk)
est un morphisme de groupes (l'entier x étant toujours supposé d'ordre r modulo p).
b. Déterminer le noyau de ce morphisme puis retrouver très simplement à l'aide de
les résultats des questions 3.b et 3.c.
Racines primitives modulo p
Un entier x est appelé une racine primitive modulo p s'il est d'ordre p-1 modulo p
(d'après la question 1, c'est la plus grande valeur envisageable pour l'ordre).
5. Exemples. Montrer que 2 est une racine primitive modulo 11. Déterminer toutes les
racines primitives modulo 7.
6. Montrer qu'un entier x est une racine primitive modulo p si et seulement si l'on a
(
/p
)*= {x,x2, ... , xp-1}
7. Un autre exemple.
a. Montrer que 2 est une racine primitive modulo 197 en efectuant le moins de
calcul possible (on indiquera les calculs efectués).
Indication. Utiliser la décomposition en facteurs premiers de p-1 pour chercher l'ordre
de 2 modulo p = 197.
b. Résoudre l'équation x5
1 (197).
c. Résoudre l'équation x7
1 (197).
On cherchera des méthodes évitant d'efectuer 197 essais !
d. Soit n 2 N. Combien l'équation xn
1 (197) possède-t-elle de solutions dans
l'intervalle [0; 196] ?
Nombre de racines d'un polynôme modulo p
Soit f : x
a0 + a1x + ... + anxn un polynôme à coecients entiers (a0;...; an 
),
de degré n, tel que annon
0 (p). Dans tout ce qui suit, la variable x sera supposée
appartenir à
.
8. Comparer f(x) et f(x + p) modulo p.
On dit qu'un entier x0 est racine de f modulo p si l'on a f(x0)
0 (p). Le nombre de
racines de f modulo p est le nombre d'entiers de l'intervalle [0; p- 1] qui sont racines
de f modulo p.
9. a. Soit x0 une racine de f modulo p. Montrer qu'il existe un polynôme g à coe-
cients entiers tel que pour tout x 
,
f(x)
(x - x0)g(x) (p):
b. Montrer que f possède au plus n racines modulo p.
10. Application. Montrer que pour tout x 
, on a
xp-1 - 1
(x - 1)(x - 2)...(x - p + 1) (p):
En déduire une preuve du théorème de Wilson : (p - 1)!
-1 (p).