7.4 Construire de grands nombres premiers
233
Q
(x) = x
r + c r−1 x
r−1 + · · · + c 1 x + c 0 .
Alors, si x ∈ S, Q(x) ≡ Q
(x) (mod n). Donc, si x ∈ S,
P (x) ≡ (x − a 1 )Q
(x) + γ (mod n).
´
Evaluons en a 1 . Nous obtenons P (a 1 ) ≡ γ (mod n). Donc, γ = 0 et
P (x) ≡ (x − a 1 )Q
(x) (mod n).
Alors, P (x) ≡ 0 (mod n) si et seulement si n | (x − a 1 )Q
(x). Comme n est premier,
ceci est vrai si et seulement si x ≡ a 1 (mod n) ou Q
(x) ≡ 0 (mod n). De par
l’hypoth` ese d’induction, Q
(x) ≡ 0 (mod n) a au plus r solutions. Donc, P (x) ≡
0 (mod n) a au plus r + 1 solutions.
2. D’apr` es le petit th´ eor` eme de Fermat (th´ eor` eme 7.9), tout x ∈ S \ {0} est une
solution de P n−1 (x) ≡ 0 (mod n). Donc, cette congruence a exactement n − 1
solutions distinctes. Soit d un diviseur de n − 1 : n − 1 = dk. Alors on peut ´ ecrire
P n−1 (x) = (x
d
− 1)Q(x) pour Q(x) =
k−1
i=0 x
id . Comme, en vertu de 1., P d (x) =
x
d
− 1 ≡ 0 (mod n) a au plus d solutions et que Q(x) ≡ 0 (mod n) a au plus
(k − 1)d solutions, si P d (x) ≡ 0 (mod n) a moins de d solutions, cela donnera moins
de d + (k − 1)d = n − 1 solutions pour P n−1 (x) ≡ 0 (mod n), soit une contradiction.
Donc, P d (x) ≡ 0 (mod n) a exactement d solutions distinctes dans S \ {0} = E.
Th´ eor` eme 7.22 Si n est premier, l’ensemble E = {1, . . . , n − 1}, muni de la multiplication modulo n est un groupe cyclique. Si g ∈ E est tel que E = {g, g
2 , . . . , g
n−1 = 1},
alors g est appel´ e racine primitive de E.
Preuve Commen¸ cons par remarquer que E = {1, . . . , n − 1} est un groupe sous la
multiplication modulo n. En effet, comme n est premier, tout a ∈ E est relativement
premier avec n. La conclusion d´ ecoule du corollaire 7.6.
D’apr` es le petit th´ eor` eme de Fermat (th´ eor` eme 7.9), pour tout a dans E, on a a
n−1 =
1. (a
n−1 = 1 est une ´ egalit´ e d’´ el´ ements d’un groupe. Elle signifie a
n−1
≡ 1 (mod n).)
Soit r ≥ 1 l’entier minimum tel que a
r = 1. On sait qu’un tel r existe puisque a
n−1 = 1.
Ce r est appel´ e l’ordre de a. Regardons l’ensemble F = {a, a
2 , . . . , a
r = 1}. Il est facile de
v´ erifier que c’est un sous-groupe de E qui contient r ´ el´ ements. Alors, de par le th´ eor` eme
de Lagrange, r | n − 1. On doit montrer qu’il existe un a dont l’ordre est exactement
n − 1. Soit d un diviseur propre de n − 1. D´ emontrons qu’on a exactement d ´ el´ ements
de G dont l’ordre divise d. En effet, tout ´ el´ ement a dont l’ordre divise d est une solution
de la congruence x
d
− 1 ≡ 0 (mod n). Le r´ esultat d´ ecoule de la partie 2 du Lemme 7.21.
D´ ecomposons n − 1 en facteurs premiers : n − 1 = p
k1
1 . . . p
ks
s , et consid´ erons les
polynˆ omes Q p
k i
i
(x) = x
p
k i
i −1. En vertu de la partie 2 du Lemme 7.21, chaque congruence
Q p
k i
i
(x) ≡ 0 (mod n) a exactement p
ki
i solutions dans E : toutes ces solutions sont des
233
Q
(x) = x
r + c r−1 x
r−1 + · · · + c 1 x + c 0 .
Alors, si x ∈ S, Q(x) ≡ Q
(x) (mod n). Donc, si x ∈ S,
P (x) ≡ (x − a 1 )Q
(x) + γ (mod n).
´
Evaluons en a 1 . Nous obtenons P (a 1 ) ≡ γ (mod n). Donc, γ = 0 et
P (x) ≡ (x − a 1 )Q
(x) (mod n).
Alors, P (x) ≡ 0 (mod n) si et seulement si n | (x − a 1 )Q
(x). Comme n est premier,
ceci est vrai si et seulement si x ≡ a 1 (mod n) ou Q
(x) ≡ 0 (mod n). De par
l’hypoth` ese d’induction, Q
(x) ≡ 0 (mod n) a au plus r solutions. Donc, P (x) ≡
0 (mod n) a au plus r + 1 solutions.
2. D’apr` es le petit th´ eor` eme de Fermat (th´ eor` eme 7.9), tout x ∈ S \ {0} est une
solution de P n−1 (x) ≡ 0 (mod n). Donc, cette congruence a exactement n − 1
solutions distinctes. Soit d un diviseur de n − 1 : n − 1 = dk. Alors on peut ´ ecrire
P n−1 (x) = (x
d
− 1)Q(x) pour Q(x) =
k−1
i=0 x
id . Comme, en vertu de 1., P d (x) =
x
d
− 1 ≡ 0 (mod n) a au plus d solutions et que Q(x) ≡ 0 (mod n) a au plus
(k − 1)d solutions, si P d (x) ≡ 0 (mod n) a moins de d solutions, cela donnera moins
de d + (k − 1)d = n − 1 solutions pour P n−1 (x) ≡ 0 (mod n), soit une contradiction.
Donc, P d (x) ≡ 0 (mod n) a exactement d solutions distinctes dans S \ {0} = E.
Th´ eor` eme 7.22 Si n est premier, l’ensemble E = {1, . . . , n − 1}, muni de la multiplication modulo n est un groupe cyclique. Si g ∈ E est tel que E = {g, g
2 , . . . , g
n−1 = 1},
alors g est appel´ e racine primitive de E.
Preuve Commen¸ cons par remarquer que E = {1, . . . , n − 1} est un groupe sous la
multiplication modulo n. En effet, comme n est premier, tout a ∈ E est relativement
premier avec n. La conclusion d´ ecoule du corollaire 7.6.
D’apr` es le petit th´ eor` eme de Fermat (th´ eor` eme 7.9), pour tout a dans E, on a a
n−1 =
1. (a
n−1 = 1 est une ´ egalit´ e d’´ el´ ements d’un groupe. Elle signifie a
n−1
≡ 1 (mod n).)
Soit r ≥ 1 l’entier minimum tel que a
r = 1. On sait qu’un tel r existe puisque a
n−1 = 1.
Ce r est appel´ e l’ordre de a. Regardons l’ensemble F = {a, a
2 , . . . , a
r = 1}. Il est facile de
v´ erifier que c’est un sous-groupe de E qui contient r ´ el´ ements. Alors, de par le th´ eor` eme
de Lagrange, r | n − 1. On doit montrer qu’il existe un a dont l’ordre est exactement
n − 1. Soit d un diviseur propre de n − 1. D´ emontrons qu’on a exactement d ´ el´ ements
de G dont l’ordre divise d. En effet, tout ´ el´ ement a dont l’ordre divise d est une solution
de la congruence x
d
− 1 ≡ 0 (mod n). Le r´ esultat d´ ecoule de la partie 2 du Lemme 7.21.
D´ ecomposons n − 1 en facteurs premiers : n − 1 = p
k1
1 . . . p
ks
s , et consid´ erons les
polynˆ omes Q p
k i
i
(x) = x
p
k i
i −1. En vertu de la partie 2 du Lemme 7.21, chaque congruence
Q p
k i
i
(x) ≡ 0 (mod n) a exactement p
ki
i solutions dans E : toutes ces solutions sont des