Nombre premier
Un nombre premier est un entier naturel strictement supérieur à 1, divisible seulement par 1 et par lui-même. Les vingt premiers nombres premiers sont:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
Le fait qu'un nombre soit premier est appelé la primalité. Un entier supérieur à 1 qui n'est pas premier est appelé nombre composé car il se factorise. par exemple, , donc 12 est composé.
Les nombres premiers sont étudiés depuis l'Antiquité. Euclide a prouvé dans ses Éléments (proposition 20 du livre IX) qu'il en existe une infinité par un exemple classique de démonstration par l'absurde :
- Supposons que l'ensemble E de nombres premiers soit fini. Le produit P de tous ces nombres premiers est supérieur à chaque facteur et a fortiori le nombre N = P + 1 aussi. Ainsi N n'est pas dans E, il est composé. Pourtant, lorsqu'on le divise par chaque nombre premier, le reste vaut 1. N, divisible par aucun des nombres premiers, doit être premier lui-même. C'est une contradiction, donc notre supposition initiale est fausse. En conclusion, il existe un nombre infini de nombres premiers.
- Supposons que l'ensemble E de nombres premiers soit fini. Le produit P de tous ces nombres premiers est supérieur à chaque facteur et a fortiori le nombre N = P + 1 aussi. Ainsi N n'est pas dans E, il est composé. Pourtant, lorsqu'on le divise par chaque nombre premier, le reste vaut 1. N, divisible par aucun des nombres premiers, doit être premier lui-même. C'est une contradiction, donc notre supposition initiale est fausse. En conclusion, il existe un nombre infini de nombres premiers.
Bien que l'ensemble des nombres premiers soit infini, nous pourrions nous poser la question : combien y a-t-il de nombres premiers en dessous de 100 000 ? , ou quelle est la probabilité pour qu'un nombre entier aléatoire de 100 chiffres soit premier ? Des questions comme celles-ci trouvent une réponse grà¢ce au théorème des nombres premiers.
Les nombres premiers ont de nombreuses utilisations pratiques, dont la cryptographie asymétrique.
Pour déterminer si un nombre est premier, on utilise des tests de primalité.
Certains tests de primalité sont probabilistes et choisissent un nombre aléatoire appelé « témoin » et vérifient quelque formule impliquant le témoin et le nombre potentiellement premier N. Après plusieurs itérations, ils déclarent N être « sans aucun doute composé » ou « probablement premier ». Ces examens ne sont pas parfaits. Pour un test donné, il peut y avoir plusieurs nombres composés qui seront déclarés « probablement premiers » indépendamment du témoin choisi. De tels nombres sont appelés pseudo-premiers pour ce test. Vous trouverez ici une description du test de primalité de Fermat.
Un nouvel algorithme qui détermine si un nombre donné N est premier et qui utilise utilise un temps polynomial en le nombre de chiffres de N fut récemment décrit.
Pour rechercher une liste de tous les nombres premiers inférieurs à une limite, le crible d'Ératosthène est une méthode simple et efficace.
Il y a beaucoup de questions ouvertes sur les nombres premiers. Par exemple :
Le plus grand nombre premier connu est 2 24 036 583-1 (ce nombre comporte 7 235 733 chiffres). Il s'agit du 41e nombre premier de Mersenne découvert M24036583 découvert le 15 mai 2004 grà¢ce aux efforts d'une collaboration qui porte le nom de GIMPS, rendu public en mai 2004 après une double vérification.
Le nombre premier précédent est 220996011-1, (ce nombre comporte 6 320 430 chiffres), et est aussi un nombre premier de Mersenne, encore découvert par GIMPS le 17 novembre 2003.
Tous les plus grands nombres premiers connus sont des nombres premiers de Mersenne, parce qu'il existe un test de primalité particulièrement rapide adapté aux nombres de cette forme, le test de Lucas-Lehmer.
Quelques uns des plus grands nombres premiers n'ayant pas de forme particulière (c'est-à -dire ne pouvant s'écrire à l'aide d'une formule simple comme les nombres premiers de Mersenne) ont été trouvés en prenant un morceau de données binaires pseudo-aléatoires, et en les convertissant en un nombre n, en multipliant par 256k o๠k est un certain entier strictement positif, et en cherchant des nombres premiers éventuels dans l'intervalle [256kn + 1, 256k(n + 1) - 1].
En fait, pour lancer un coup publicitaire contre l'acte de copyright de Digital Millennium et les autres implémentations du traité de copyright WIPO, quelques personnes ont appliqué cette méthode à différentes formes variées du code DeCSS, en créant l'ensemble des nombres premiers illégaux.
De tels nombres, lorsqu'ils sont convertis en binaire et exécutés comme un programme informatique, enfreignent la loi en vigueur dans une ou plusieurs juridictions.
Les nombres premiers extrêmement grands (c'est-à -dire plus grand que 10100) sont de possibles clés publiques cryptographiques. Les nombres premiers sont aussi utilisés pour construire des tables de hachage et pour constituer des générateurs de nombres pseudo-aléatoires.
Un nombre premier p est dit primoriel s'il est de la forme p = Î (n) ± 1 pour un certain nombre n, o๠Π(n) représente le produit 2 · 3 · 5 · 7 · 11 · ... de tous les nombres premiers inférieurs à n. Un nombre premier est dit factoriel si il est de la forme n! ± 1. Les premiers nombres premiers factoriels sont:
Les nombres premiers de la forme 22n+1 sont appelés les nombres premiers de Fermat.
La suite des chiffres en base dix d'un nombre premier peut être un palindrome, comme dans le nombre premier 1031512 + 9700079 · 1015753 + 1. 11 et 2 sont des palindromes triviaux.
L'écart entre le nème nombre premier pn et le n+1ème nombre premier pn+1 est défini comme étant le nombre de nombres composés compris entre les deux, i.e. gn = pn+1 - pn - 1 (des définitions légèrement différentes sont parfois utilisées).
Nous avons g1 = 0 and g2 = 1.
La suite (gn) des écarts entre les nombres premiers a été étudié en profondeur.
Nous pouvons montrer que les écarts deviennent arbitrairement grands, i.e. pour tout nombre entier naturel N, il existe un indice n tel que gn > N. D'autre part, pour tout nombre réel strictement positif ε, il exsite un indice de début n0 tel que gn < ε · pn pour tout n > n0.
Nous disons que gn est un écart maximal si pour tout m<n, gm < gn. Le plus grand écart maximal connu est de 1131, trouvé par T. Nicely et B. Nyman en 1999. C'est le 64e plus petit écart maximal, et il se situe après le nombre premier 1693182318746371.
Le curieux polynà´me f(n) = n2 - n + 41 donne des nombres premiers pour n = 0,..., 40, mais f(41) est composé. Il n'existe aucun polynà´me qui donne tous les nombres premiers de cette façon.
Il existe un polynà´me à 26 variables à coefficients entiers tel que, si vous limitez les valeurs des variables aux nombres entiers, alors l'ensemble des valeurs strictement positives est égal à l'ensemble des nombres premiers. Cependant, pour quelques valeurs des variables, le résultat est négatif et le nombre peut être alors composé.
La fonction suivante donne tous les nombres premiers, et uniquement les nombres premiers, pour tout entier naturel n:
En utilisant la fonction partie entière, [x] (la partie entière de x est le plus grand entier inférieur au nombre réel x), nous pouvons construire plusieurs formules donnant le nème nombre premier. Ces formules sont aussi basées sur le théorème de Wilson et sont intéressantes dans la pratique: elles permettent de trouver les nombres premiers de manière plus efficace.
Définissons
Le concept de nombre premier est si important qu'il a été généralisé de différentes façons dans des branches variées des mathématiques.
L'ensemble {2,3,5,7,11,...} est l'ensemble des nombres premiers des entiers naturels. L'ensemble {...-11,-7,-5,-3,-2,2,3,5,7,11,...} est l'ensemble des nombres premiers des entiers relatifs. Lorsque nous parlons de nombres premiers sans précision, nous considérons les nombres premiers entiers naturels. Mais il arrive que certains dictionnaires de mathématiques définissent les nombres premiers en considérant les nombres premiers entiers relatifs.
En théorie des nombres, certains mathématiciens parlent de nombres pseudo-premiers, des entiers qui, parce qu'ils satisfont à un certain test, sont considéré comme des nombres premiers probables mais peuvent être en fait composés (comme les nombres de Carmichael). Pour modéliser certaines des propriétés des nombres premiers, nous définissons les polynà´mes premiers ou irréductibles. Plus généralement, nous pouvons définir des éléments premiers et irréductibles dans tout anneau intègre. Les idéaux premiers constituent un outil indispensable et font l'objet d'une étude en algèbre commutative et en géométrie algébrique.
Le nombre premier suivant correspond aux 38 premiers chiffres de Pi :
Merveilleux nombres premiers, de Jean-Paul Delahaye, Éditions Belin - Pour la Science
Utilisation
Méthodes de calcul
Quelques propriétés des nombres premiers
Questions ouvertes
Le plus grand nombre premier connu
Applications
Quelques types particuliers de nombres premiers
Le plus grand nombre premier primoriel connu est Î (24029) + 1, trouvé par Caldwell en 1993. Le plus grand nombre premier factoriel est 3610! - 1 [Caldwell, 1993]. Nous ne savons pas s'il y a une infinité de nombres premiers factoriels ou primoriels.Écart entre les nombres premiers
Les formules menant aux nombres premiers
Cette formule est basée sur le théorème de Wilson mentionné ci-dessus; deux est généré plusieurs fois et tous les autres nombres premiers sont générés exactement une fois par cette fonction.
ou, alternativement,
Ces définitions sont équivalentes; Ï€(m) est le nombre de nombres premiers inférieurs à m. Le nème nombre premier pn peut être écrit sous la forme
Une autre approche n'utilise pas les factorielles et le théorème de Wilson, mais utilise aussi largement la fonction partie entière (S. M. Ruiz 2000): d'abord définissons
nous avons alors,Généralisations
Citation
Les 25 premiers nombres premiers
n
pn
Binaire
1/p
Nombre de
chiffres
de la période
1
2
10
0,5
1
2
3
11
0,3...
1
3
5
101
0,2
1
4
7
111
0,142857...
6
5
11
1011
0,09...
2
6
13
1101
0,076923...
6
7
17
10001
0,0588235294117647...
16
8
19
10011
0,052631578947368421...
18
9
23
10111
0,0434782608695652173913...
22
10
29
11101
0,0344827586206896551724137
931...
28
11
31
11111
0,032258064516129...
15
12
37
100101
0,027...
3
13
41
101001
0,02439...
5
14
43
101011
0,023255813953488372093...
21
15
47
101111
0,0212765957446808510638297
872340425531914893617...
46
16
53
110101
0,0188679245283...
13
17
59
111011
0,0169491525423728813559322
0338983050847457627118644
06779661...
58
18
61
111101
0,0163934426229508196721311
4754098360655737704918032
7868852459...
60
19
67
1000011
0,0149253731343283582089552
23880597...
33
20
71
1000111
0,0140845070422535211267605
6338028169...
35
21
73
1001001
0,01369863...
8
22
79
1001111
0,0126582278481...
13
23
83
1010011
0,0120481927710843373493975
9036144578313253...
41
24
89
1011001
0,0112359550561797752808988
7640449438202247191...
44
25
97
1100001
0,0103092783505154639175257
7319587628865979381443298
9690721649484536082474226
804123711340206185567...
96
Curiosité
Références
Liens externes
Voir aussi
Crible d'Ératosthène ~ nombre premier de Fermat ~ nombre premier de Mersenne ~ GIMPS ~ factorisation en nombres premiers
