7.4 Construire de grands nombres premiers
231
g
m =
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
g ∗ g ∗ · · · ∗ g
m
m > 0
1
m = 0
g
−1
∗ g
−1
∗ · · · ∗ g
−1
|m|
m < 0.
Dans le cas d’un groupe fini de n ´ el´ ements, on peut se convaincre que le groupe est
de la forme G = {1, g, g
2 , . . . , g
n−1
} et que g
n = 1.
Exemple 7.17 Soient p un nombre premier et G = {1, 2, . . . , p − 1}. Sur G, on d´ efinit
a ∗ b = c si c est le reste de la division de ab par p. Autrement dit, ∗ est la multiplication
modulo p. Avec cette op´ eration, G est un groupe. Nous laissons le lecteur v´ erifier que
∗ est associative. Il est ´ evident que 1 est un ´ el´ ement neutre. Finalement, l’existence de
l’inverse d´ ecoule du corollaire 7.6. Nous verrons ci-dessous au th´ eor` eme 7.22 que ce
groupe est cyclique.
On peut d´ ej` a le v´ erifier pour p = 7 puisque si g = 3, alors g
2 = 2, g
3 = 6, g
4 = 4,
g
5 = 5 et g
6 = 1.
Notation Dans l’exemple ci-dessus et les exemples de groupe que nous rencontrerons ci-dessous, l’op´ eration sera toujours la multiplication modulo n. Dans ce cas, nous
laisserons tomber le signe ∗ pour l’op´ eration et noterons simplement ab au lieu de a ∗ b.
Lagrange a d´ emontr´ e le th´ eor` eme suivant.
Th´ eor` eme 7.18 (th´ eor` eme de Lagrange) Soient G un groupe fini et H un sousgroupe de G. Alors, le nombre d’´ el´ ements de H, not´ e |H|, divise le nombre d’´ el´ ements
de G, not´ e |G|.
Preuve Si H = G, on a fini. Sinon, il existe a 1 ∈ G \ H.
Soit a 1 H = {a 1 ∗ h | h ∈ H}. Alors, |a 1 H| = |H|. En effet, si h = h
alors a 1 ∗ h =
a 1 ∗ h
. Donc, f : H → a 1 H, d´ efinie par h → a 1 ∗ h, est une bijection.
De plus, a 1 H ∩ H = ∅. En effet, si h ∈ a 1 H ∩ H, alors h = a 1 ∗ h
pour h
∈ H.
Donc, a 1 = h ∗ (h
)
−1
∈ H. Contradiction.
Deux cas peuvent maintenant se produire. Si a 1 H ∪ H = G, alors |G| = 2|H|. Sinon,
il existe a 2 ∈ G \ (H ∪ a 1 H). On consid` ere a 2 H = {a 2 ∗ h | h ∈ H}. On it` ere le proc´ ed´ e.
Comme |G| est fini, on peut ´ ecrire G = H ∪ a 1 H ∪ a 2 H ∪ · · · ∪ a n H o` u H et les a i H
sont disjoints et |H| = |a 1 H| = · · · = |a n H|. Alors, |G| = (n + 1)|H|.
Th´ eor` eme 7.19 Si n n’est pas premier, moins de la moiti´ e des nombres a ∈ E =
{1, . . . , n − 1} r´ eussissent le test, c’est-` a-dire satisfont `
a (7.4).
Id´ ee de la preuve La preuve utilise l’astuce suivante. Les ´ el´ ements de E qui sont
relativement premiers avec n forment un groupe G sous la multiplication modulo n.
En effet, remarquons d’abord que le produit aa
de deux nombres a et a
relativement
premiers avec n est encore relativement premier avec n, c’est-` a-dire (aa
, n) = 1. Soit a
231
g
m =
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
g ∗ g ∗ · · · ∗ g
m
m > 0
1
m = 0
g
−1
∗ g
−1
∗ · · · ∗ g
−1
|m|
m < 0.
Dans le cas d’un groupe fini de n ´ el´ ements, on peut se convaincre que le groupe est
de la forme G = {1, g, g
2 , . . . , g
n−1
} et que g
n = 1.
Exemple 7.17 Soient p un nombre premier et G = {1, 2, . . . , p − 1}. Sur G, on d´ efinit
a ∗ b = c si c est le reste de la division de ab par p. Autrement dit, ∗ est la multiplication
modulo p. Avec cette op´ eration, G est un groupe. Nous laissons le lecteur v´ erifier que
∗ est associative. Il est ´ evident que 1 est un ´ el´ ement neutre. Finalement, l’existence de
l’inverse d´ ecoule du corollaire 7.6. Nous verrons ci-dessous au th´ eor` eme 7.22 que ce
groupe est cyclique.
On peut d´ ej` a le v´ erifier pour p = 7 puisque si g = 3, alors g
2 = 2, g
3 = 6, g
4 = 4,
g
5 = 5 et g
6 = 1.
Notation Dans l’exemple ci-dessus et les exemples de groupe que nous rencontrerons ci-dessous, l’op´ eration sera toujours la multiplication modulo n. Dans ce cas, nous
laisserons tomber le signe ∗ pour l’op´ eration et noterons simplement ab au lieu de a ∗ b.
Lagrange a d´ emontr´ e le th´ eor` eme suivant.
Th´ eor` eme 7.18 (th´ eor` eme de Lagrange) Soient G un groupe fini et H un sousgroupe de G. Alors, le nombre d’´ el´ ements de H, not´ e |H|, divise le nombre d’´ el´ ements
de G, not´ e |G|.
Preuve Si H = G, on a fini. Sinon, il existe a 1 ∈ G \ H.
Soit a 1 H = {a 1 ∗ h | h ∈ H}. Alors, |a 1 H| = |H|. En effet, si h = h
alors a 1 ∗ h =
a 1 ∗ h
. Donc, f : H → a 1 H, d´ efinie par h → a 1 ∗ h, est une bijection.
De plus, a 1 H ∩ H = ∅. En effet, si h ∈ a 1 H ∩ H, alors h = a 1 ∗ h
pour h
∈ H.
Donc, a 1 = h ∗ (h
)
−1
∈ H. Contradiction.
Deux cas peuvent maintenant se produire. Si a 1 H ∪ H = G, alors |G| = 2|H|. Sinon,
il existe a 2 ∈ G \ (H ∪ a 1 H). On consid` ere a 2 H = {a 2 ∗ h | h ∈ H}. On it` ere le proc´ ed´ e.
Comme |G| est fini, on peut ´ ecrire G = H ∪ a 1 H ∪ a 2 H ∪ · · · ∪ a n H o` u H et les a i H
sont disjoints et |H| = |a 1 H| = · · · = |a n H|. Alors, |G| = (n + 1)|H|.
Th´ eor` eme 7.19 Si n n’est pas premier, moins de la moiti´ e des nombres a ∈ E =
{1, . . . , n − 1} r´ eussissent le test, c’est-` a-dire satisfont `
a (7.4).
Id´ ee de la preuve La preuve utilise l’astuce suivante. Les ´ el´ ements de E qui sont
relativement premiers avec n forment un groupe G sous la multiplication modulo n.
En effet, remarquons d’abord que le produit aa
de deux nombres a et a
relativement
premiers avec n est encore relativement premier avec n, c’est-` a-dire (aa
, n) = 1. Soit a