7.4 Construire de grands nombres premiers
229
satisfont `
a (7.4). On doit aussi montrer que, si n est premier, alors tous les nombres
a ∈ E r´ eussissent le test.
Le symbole de Jacobi Soient a, b ∈ N relativement premiers. Le symbole de Jacobi
J(a, b) prend ses valeurs dans {1, −1}. Si b est premier, on pose
J(a, b) =
1,
si ∃x ∈ N x
2
≡ a (mod b),
−1,
sinon.
Si b n’est pas premier, on peut alors ´ ecrire b = p 1 . . . p r (les p i ne sont pas n´ ecessairement
distincts), et J(a, b) est d´ efini par
J(a, b) = J(a, p 1 ) · · · J(a, p r ) =
r
i=1
J(a, p i ).
(Le symbole de Jacobi J(a, b) est aussi not´ e
a
b
dans certains livres de th´ eorie des
nombres.) On voit bien que cette d´ efinition est un peu obscure et, de plus, difficile ` a
manipuler. En effet, comment v´ erifie-t-on s’il existe x tel que x
2
≡ a (mod b), c’est` a-dire que a est un carr´ e dans l’arithm´ etique modulo b (on dit que a est un r´ esidu
quadratique) ? De plus, la d´ efinition suppose que l’on connaisse la factorisation de b. On a
donc l’impression de tourner en rond ! Il existe heureusement une mani` ere algorithmique
de calculer J(a, b) sans passer par la d´ efinition. Nous illustrerons son utilisation sur des
exemples.
Le th´ eor` eme suivant que nous citerons sans preuve donne cette mani` ere algorithmique de calculer J(a, b). Remarquons que, pour notre probl` eme, nous pouvons nous
limiter au cas a ≤ b et b impair.
Th´ eor` eme 7.14 Si (a, b) = 1, pour a ≤ b et b impair, alors on a
J(a, b) =
⎧
⎪ ⎨
⎪ ⎩
1,
si a = 1,
J(
a
2 , b)(−1)
b 2 −1
8
,
si a pair,
J(b (mod a), a)(−1)
(a−1)(b−1)
4
, si a impair et a > 1.
(7.5)
Dans la formule (7.5), remarquons que les exposants
b
2 −1
8
et
(a−1)(b−1)
4
sont toujours
des entiers (exercice 16).
Exemple 7.15 Prenons a = 130 et b = 207. Alors,
J(130, 207) = J(65, 207)(−1)
42848
8
= J(65, 207)(−1)
5356
= J(65, 207) = J(12, 65)(−1)
64×206
4
= J(12, 65)
= J(6, 65)(−1)
4224
8
= J(6, 65)(−1)
528 = J(6, 65)
= J(3, 65)(−1)
528 = J(3, 65) = J(2, 3)(−1)
2×64
4
= J(2, 3) = J(1, 3)(−1)
8
8 = −J(1, 3) = −1.
229
satisfont `
a (7.4). On doit aussi montrer que, si n est premier, alors tous les nombres
a ∈ E r´ eussissent le test.
Le symbole de Jacobi Soient a, b ∈ N relativement premiers. Le symbole de Jacobi
J(a, b) prend ses valeurs dans {1, −1}. Si b est premier, on pose
J(a, b) =
1,
si ∃x ∈ N x
2
≡ a (mod b),
−1,
sinon.
Si b n’est pas premier, on peut alors ´ ecrire b = p 1 . . . p r (les p i ne sont pas n´ ecessairement
distincts), et J(a, b) est d´ efini par
J(a, b) = J(a, p 1 ) · · · J(a, p r ) =
r
i=1
J(a, p i ).
(Le symbole de Jacobi J(a, b) est aussi not´ e
a
b
dans certains livres de th´ eorie des
nombres.) On voit bien que cette d´ efinition est un peu obscure et, de plus, difficile ` a
manipuler. En effet, comment v´ erifie-t-on s’il existe x tel que x
2
≡ a (mod b), c’est` a-dire que a est un carr´ e dans l’arithm´ etique modulo b (on dit que a est un r´ esidu
quadratique) ? De plus, la d´ efinition suppose que l’on connaisse la factorisation de b. On a
donc l’impression de tourner en rond ! Il existe heureusement une mani` ere algorithmique
de calculer J(a, b) sans passer par la d´ efinition. Nous illustrerons son utilisation sur des
exemples.
Le th´ eor` eme suivant que nous citerons sans preuve donne cette mani` ere algorithmique de calculer J(a, b). Remarquons que, pour notre probl` eme, nous pouvons nous
limiter au cas a ≤ b et b impair.
Th´ eor` eme 7.14 Si (a, b) = 1, pour a ≤ b et b impair, alors on a
J(a, b) =
⎧
⎪ ⎨
⎪ ⎩
1,
si a = 1,
J(
a
2 , b)(−1)
b 2 −1
8
,
si a pair,
J(b (mod a), a)(−1)
(a−1)(b−1)
4
, si a impair et a > 1.
(7.5)
Dans la formule (7.5), remarquons que les exposants
b
2 −1
8
et
(a−1)(b−1)
4
sont toujours
des entiers (exercice 16).
Exemple 7.15 Prenons a = 130 et b = 207. Alors,
J(130, 207) = J(65, 207)(−1)
42848
8
= J(65, 207)(−1)
5356
= J(65, 207) = J(12, 65)(−1)
64×206
4
= J(12, 65)
= J(6, 65)(−1)
4224
8
= J(6, 65)(−1)
528 = J(6, 65)
= J(3, 65)(−1)
528 = J(3, 65) = J(2, 3)(−1)
2×64
4
= J(2, 3) = J(1, 3)(−1)
8
8 = −J(1, 3) = −1.