Qu'est-ce qu'un nombre premier ?
Un nombre premier est un entier qui a exactement deux diviseurs : 1 et lui-même. 2, 3, 5, 7, 11 et 13 sont premiers ; 9 ne l'est pas, puisqu'il est divisible par 3. Deux cas trompent souvent :
- 1 n'est pas premier : il n'a qu'un seul diviseur, lui-même ;
- 2 est le seul nombre premier pair : tout autre nombre pair est divisible par 2.
Un entier à partir de 2 qui n'est pas premier est dit composé : il s'écrit comme un produit de nombres premiers, sa décomposition en facteurs premiers.
Comment savoir si un nombre est premier ?
À la main, on essaie de diviser le nombre par 2, 3, 5, 7, 11… c'est-à-dire par les nombres premiers successifs. Inutile d'aller au-delà de sa racine carrée : si n = a × b avec a ≤ b, alors a × a ≤ n, donc a ne dépasse pas √n.
aucun diviseur de 2 à √n ⇒ n est premierCe calculateur procède ainsi jusqu'à mille milliards (1012), soit au plus un million d'essais. Au-delà, il utilise le test de Miller-Rabin avec les 13 premiers nombres premiers comme bases, de 2 à 41. Ce test est d'ordinaire probabiliste, mais avec ces 13 bases il est prouvé sans erreur pour tout nombre inférieur à 3 317 044 064 679 887 385 961 981, soit environ 3,3 × 1024 (Sorenson et Webster, 2015, référencé par l'OEIS) : c'est pourquoi l'outil s'arrête à 1024, la recherche du nombre premier suivant restant sous cette borne.
Quand le nombre n'est pas premier, l'outil donne le calcul qui le prouve (n = p × q), puis sa décomposition et la liste de ses diviseurs jusqu'à 1015.
Le crible d'Ératosthène
Pour obtenir tous les nombres premiers jusqu'à N, on écrit les entiers de 2 à N, puis on garde 2 et on barre ses multiples, on garde 3 et on barre ses multiples, et ainsi de suite avec le premier nombre non barré. On peut commencer à barrer à partir du carré de chaque nombre gardé, et s'arrêter quand ce carré dépasse N : tout ce qui reste non barré est premier. Le mode « Lister » de l'outil applique ce crible jusqu'à 100 000.
| Jusqu'à | Nombres premiers |
|---|---|
| 100 | 25 |
| 1 000 | 168 |
| 10 000 | 1 229 |
| 100 000 | 9 592 |
Les 25 nombres premiers inférieurs à 100 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97.
Trois exemples
√97 vaut un peu moins de 10 : on essaie 2, 3, 5 et 7. Aucun ne divise 97, donc 97 est premier. Le premier suivant est 101.
La somme de ses chiffres, 12, est un multiple de 3 : 561 = 3 × 187, donc 561 n'est pas premier. Sa décomposition est 3 × 11 × 17, et il a 8 diviseurs.
Ce nombre à 19 chiffres vaut 261 − 1. Trop grand pour les divisions, il passe le test de Miller-Rabin sur les 13 bases : il est premier.
L'erreur fréquente : 91 a l'air premier
91 est impair, ne se termine ni par 0 ni par 5, et la somme de ses chiffres (10) n'est pas un multiple de 3 : il passe les critères de divisibilité les plus connus. Mais il est divisible par 7. Tant qu'on n'a pas essayé tous les nombres premiers jusqu'à la racine carrée (ici 2, 3, 5 et 7), on ne peut pas conclure.
Questions fréquentes
1 est-il un nombre premier ?
Non. Un nombre premier a exactement deux diviseurs distincts, 1 et lui-même ; 1 n'en a qu'un. Le plus petit nombre premier est 2.
Jusqu'où chercher un diviseur pour savoir si un nombre est premier ?
Jusqu'à sa racine carrée. Si n = a × b avec a ≤ b, alors a ne dépasse pas √n : sans diviseur jusque-là, n est premier. Pour 97, il suffit d'essayer 2, 3, 5 et 7.
Combien y a-t-il de nombres premiers inférieurs à 100 ?
25 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97.
Le test de Miller-Rabin peut-il se tromper ?
Avec des bases tirées au hasard, il donne une réponse très probable. Avec les 13 premiers nombres premiers comme bases, de 2 à 41, il est prouvé exact pour tout nombre inférieur à environ 3,3 × 10²⁴ : c'est ce qu'utilise cet outil.
Y a-t-il un plus grand nombre premier ?
Non : il existe une infinité de nombres premiers, comme l'a démontré Euclide. Seuls les plus grands nombres premiers connus changent, à mesure qu'on en découvre.
Une erreur ? Signalez-la, nous la corrigeons.