Nombre premier

Un nombre premier est un entier naturel strictement supérieur à 1, admettant exactement deux diviseurs distincts : 1 et lui-même. L'ensemble des nombres premiers est noté ℙ.

Exemples

Voici la liste des 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, 97

Primalité

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 est factorisable. En effet, tout nombre supérieur à 1 et non premier peut être décomposé en un produit de facteurs premiers de façon unique, ainsi un nombre qui peut être décomposé en un produit de facteurs premiers n'est pas premier : par exemple $12 = 2^2 \times 3$ est composé, tout comme $14 = 7 \times 2$ .

Histoire

Les nombres premiers sont étudiés depuis l'Antiquité. Euclide a démontré par l'absurde dans ses Éléments (proposition 20 du livre IX) qu'il en existe une infinité.

Démonstration d'Euclide

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, on ne peut trouver de nombre premier plus grand que tous les autres, ergo il en existe une infinité.

Remarques

Il ne faut pas espérer en déduire pour autant que tout nombre de la forme N!+1 (factorielle n plus 1) est premier, et le contre-exemple est vite trouvé. Pour N=5, on a N! = 120 et le nombre 121, loin d'être premier, est le carré de 11. Mais il n'est en effet divisible par aucun nombre inférieur à 5.

Il ne faut pas non plus espérer pouvoir construire un nouveau nombre premier en effectuant le produit de tous les nombres premiers inférieurs à une certaine borne puis en lui ajoutant 1, en effet ce procédé ne marche pas par exemple pour : 2 x 3 x 5 x 7 x 11 x 13 + 1 = 59 x 509.

Bien qu'il existe une infinité de nombres premiers, il est possible de trouver un intervalle de nombres entiers de longueur aussi grande que l'on veut ne contenant aucun nombre premier ! Par exemple l'intervalle suivant : [ N!+2 ; N!+N ] est un intervalle de longueur N−1 ne contenant pas de nombre premiers (quel que soit N).

Autres démonstrations

D'autres mathématiciens ont donné leur propre démonstration de ce résultat; par exemple celle de Kummer est particulièrement élégante et Furstenberg fournit une preuve utilisant une argumentation topologique.

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.

Utilisation

Les nombres premiers ont de nombreuses utilisations pratiques, dont la cryptographie asymétrique. Les nombres utilisés n'ont d'intérêt que s'ils comportent beaucoup de chiffres, rendant ainsi impossible dans l'état officiel actuel de la technique un craquage en temps réel...

... mais pas un craquage anticipé. On prête à la NSA le projet de constituer une immense base de données inverse ou seraient précalculés tous les couples clé privée/clé publique jusqu'à une certaine taille. Lorsqu'on a un message à craquer, si sa clé publique est dans cette base, il suffit d'y prendre la clé privée associée, peut-être calculée quinze ans plus tôt. Les mémoires à exaoctet sont lentes, mais un seul accès nous suffit.

Méthodes de calcul

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.

L'algorithme AKS découvert en 2002 permet de déterminer si un nombre donné N est premier en utilisant un temps de calcul polynomial.

Image manquante
APL2-Chrono-Primes1000-François-Dominique.PNG

calcul de nombres premiers de 1 à 1000 par la méthode du crible d'Ératosthène

Pour rechercher une liste de tous les nombres premiers inférieurs à une limite n pas trop grande, le crible d'Ératosthène est une méthode simple et efficace : on part de la liste des entiers de 2 à n. On prend le premier nombre non barré de cette liste, 2 (à ce stade aucun nombre n'est barré), et on barre tous les entiers multiples de 2. On répète l'opération en considérant chaque fois le prochain nombre non barré et en barrant ses multiples. Les nombres qui restent non barrés à la fin du processus sont les nombres premiers inférieurs à n. (On peut en fait arrêter le processus dès que les nombres non barrés encore à considérer sont supérieurs à la racine carrée de n, car leurs multiples auront déjà été barrés.)

Quelques propriétés des nombres premiers

Si p est un nombre premier et si p divise un produit ab d'entiers, alors p divise a ou p divise b (lemme de Gauss).
L'anneau $\mathbb Z/n\mathbb Z$ (voir arithmétique modulaire) est un corps si et seulement si n est premier.
La caractéristique d'un corps quelconque est ou bien zéro ou bien un nombre premier.
Si p est un nombre premier et a est un entier quelconque, alors a^p - a est divisible par p (petit théorème de Fermat).
Si G est un groupe fini et si pⁿ est la plus grande puissance du nombre premier p qui divise l'ordre de G, alors G a un sous-groupe d'ordre pⁿ. (théorèmes de Sylow)
Si p est premier et si G est un groupe ayant pⁿ éléments, alors G contient un élément d'ordre p.
Un entier p est premier si et seulement si la factorielle (p-1)! + 1 est divisible par p (théorème de Wilson). Inversement, un entier n > 4 est composé si et seulement si (n-1)! est divisible par n.
Si n est un entier strictement positif, alors il existe toujours un nombre premier p tel que n < p ≤ 2n (postulat de Bertrand).
La somme des inverses de tous les nombres premiers forme une série divergente. (voir la démonstration). Plus précisément, si S(x) désigne la somme de tous les inverses des nombres premiers inférieurs à x, alors S(x) = Θ(ln(ln(x))) pour x → ∞ (voir notation grand O).
Pour tout nombre premier p > 3, il existe un entier naturel n tel que p = 6n - 1 ou p = 6n + 1.
Dans toute progression arithmétique a, a+q, a+2q, a+3q, où les entiers positifs a et q ≥ 1 sont premiers entre eux, il y a une infinité de nombres premiers (théorème de Dirichlet).

Le plus grand nombre premier connu

Le plus grand nombre premier connu est 2^{25 964 951}-1, il comporte 7 816 230 chiffres. Il s'agit du 42^e nombre premier de Mersenne (M_{25 964 951}) découvert le 18 février 2005 grâce aux efforts d'une collaboration qui porte le nom de GIMPS. Le record précédent était 2^{24 036 583}-1, (ce nombre comporte 7 235 733 chiffres), et est aussi un nombre premier de Mersenne découvert par GIMPS le 15 mai 2004. Tous les plus grands nombres premiers connus sont des nombres premiers de Mersenne car il existe un test de primalité particulièrement rapide adapté aux nombres de cette forme, le test de primalité 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 256^k où k est un certain entier strictement positif, et en cherchant des nombres premiers éventuels dans l'intervalle [256^kn + 1, 256^k(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.

Applications

Les nombres premiers extrêmement grands (c'est-à-dire plus grand que 10¹⁰⁰) 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.

Quelques types particuliers de nombres premiers

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. Le plus grand nombre premier primoriel connu est Π(24029) + 1, trouvé par Chris Caldwell en 1993.

Un nombre premier est dit factoriel s'il est de la forme n! ± 1. Le plus grand nombre premier factoriel connu est 3610! - 1 [Caldwell, 1993]. Les premiers nombres premiers factoriels sont:

n! - 1 est premier pour n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166,...

n! + 1 est premier pour n = 1, 2, 3, 11, 13, 27, 37, 41, 73, 77, 116, 154...

Nous ne savons pas s'il y a une infinité de nombres premiers factoriels ou primoriels.

Les nombres premiers de la forme $F_n = 2^{2^n} + 1$ sont appelés les nombres premiers de Fermat. À l'heure actuelle, F₀, F₁, F₂, F₃ et F₄ sont les seuls nombres de Fermat premiers connus.

La suite des chiffres en base dix d'un nombre premier peut être un palindrome, comme dans le nombre premier 10³¹⁵¹² + 9700079 · 10¹⁵⁷⁵³ + 1. 11 et 2 sont des palindromes triviaux.

Écart entre les nombres premiers

L'écart entre le nème nombre premier p_n et le n+1ème nombre premier p_n+1 est défini comme étant le nombre de nombres composés compris entre les deux, i.e. g_n = p_n+1 - p_n - 1 (des définitions légèrement différentes sont parfois utilisées). Nous avons g₁ = 0 and g₂ = 1. La suite (g_n) 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 g_n > N. D'autre part, pour tout nombre réel strictement positif ε, il existe un indice de début n₀ tel que g_n < ε · p_n pour tout n > n₀.

Nous disons que g_n est un écart maximal si pour tout m<n, g_m < g_n. Le plus grand écart maximal connu est de 1131, trouvé par T. Nicely et B. Nyman en 1999. C'est le 64^e plus petit écart maximal, et il se situe après le nombre premier 1693182318746371.

Les formules menant aux nombres premiers

Le curieux polynôme f(n) = n² − n + 41 donne des nombres premiers pour n allant de 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 de degré 25 à 26 variables à coefficients entiers tel que, si vous limitez les valeurs des variables aux nombres entiers naturels, alors l'ensemble des valeurs strictement positives est égal à l'ensemble des nombres premiers (pour quelques valeurs des variables, le résultat est négatif et le nombre peut être alors composé) :

(k+2)×[1−(wz+h+j−q)²−(2n+p+q+z−e)²−(a²y²−y²+1−x²)

−((e⁴+2e³)(a+1)²+1−o²)²−(16(k+1)³(k+2)(n−1)²+1−f²)²

−(((a+u⁴−u²a)²−1)(n+4dy)²+1−(x−cu)²)²−(ai+k+1−l−i)²

−((gk+2g+k+1)(h+j)+h−z)²−(16r²y⁴(a²−1)+1−u²)²

−(p−m+l(a−n−1)+b(2an+2a−n²−2n−2))²−(z−pm+pla−p²l+t(2ap−p²−1))²

−(q−x+y(a−p−1)+s(2ap+2a−p²−2p−2))²−(a²l²−l²+1−m²)²−(n+l+v−y)²]

Il a été déterminé par Jones, Sato, Wada et Wiens.

La fonction suivante donne tous les nombres premiers, et uniquement les nombres premiers, pour tout entier naturel n>1 :

$f(n) = 2 + (2n! \ \mod \ (n+1))$

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.

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, pour tout entier m, le nombre π(m) de nombres premiers inférieurs à m. On démontre

$\pi(m) = \sum_{j=2}^m \frac { \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) }$

ou, de manière équivalente,

$\pi(m) = \sum_{j=2}^m \left[ {(j-1)! + 1 \over j} - \left[{(j-1)! \over j}\right] \right]$

Le nème nombre premier p_n peut être écrit sous la forme

$p_n = 1 + \sum_{m=1}^{2^n} \left[ \left[ { n \over 1 + \pi(m) } \right]^{1 \over n} \right]$

Une autre approche n'utilise ni les factorielles, ni le théorème de Wilson, mais aussi largement la fonction partie entière (S. M. Ruiz 2000). Définissons d'abord

$G(k) = k - 1 + \sum_{j=2}^k \left[ {2 \over j} \left(1 + \sum_{s=1}^{\left[\sqrt{j}\right]} \left(\left[{ j-1 \over s}\right] - \left[{j \over s}\right]\right) \right)\right]$

nous avons alors

$p_n = 1 + \sum_{k=1}^{2([n \ln(n)]+1)} \left(1 - \left[{G(k) \over n} \right]\right)$

Généralisations

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 Carmichaël). 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.

(ajouter un texte sur la décomposition des entiers de Gauss en entiers de Gauss premiers, car l'anneau des entiers de Gauss est un cet anneau est factoriel, c'est-à-dire que tout entier de Gauss non nul admet une unique décomposition, à un ordre près, en facteurs irréductibles, à une unité près)

Questions ouvertes

Il y a beaucoup de questions ouvertes sur les nombres premiers. Par exemple :

La conjecture de Goldbach: tout nombre pair strictement supérieur à 2, peut-il s'écrire comme somme de deux nombres premiers ?
conjecture des nombres premiers jumeaux: un couple de nombres premiers jumeaux est une paire de nombres premiers dont la différence est égale à 2, comme 11 et 13. Existe-t-il une infinité de jumeaux premiers ?
Toute suite de Fibonacci contient-elle une infinité de nombres premiers ?
Existe-t-il une infinité de nombres premiers de Fermat ?
Y a-t-il toujours un nombre premier entre n² et (n + 1)² pour tout n?
Y a-t-il une infinité de nombres premiers de la forme n² + 1?
Y a-t-il une infinité de nombres premiers factoriels ?
Y a-t-il une infinité de nombres premiers primoriels ?

Citation

« La percée mathématique évidente serait le développement d'un moyen simple de factoriser les grands nombres en facteurs premiers. ». Bill Gates, The Road Ahead, Viking Penguin (1995)

Les 25 premiers nombres premiers

Euler a prouvé une relation entre un nombre premier p (différent de 2 et de 5) et le nombre de chiffres k de la période du développement décimal de 1/p : k est un diviseur de p-1. (Le développement de 1/2 et de 1/5 est fini.)

_n p_n 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és

Le nombre premier suivant correspond aux 38 premiers chiffres de Pi :

31 415 926 535 897 932 384 626 433 832 795 028 841

DIX est un nombre premier (le lire comme chiffres romains, bien entendu)

1 111 111 111 111 111 111 est un nombre premier (il y a 19 un)

Références

Jean-Paul Delahaye, Merveilleux nombres premiers, Éditions Belin - Pour la Science, 2000 - ISBN 2701150175

Liens externes

(en) Chris K. Caldwell: « La page des nombres premiers », http://www.utm.edu/research/primes/
(en) Chris K. Caldwell: « Nombre premiers illégaux », http://primes.utm.edu/glossary/page.php/Illegal.html
(en) J. O'Connor et E. F. Robertson: « histoire MacTutor des nombres premiers », http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html
(en) Carlos Rivera: « les puzzles de nombres premiers » http://www.primepuzzles.net/
La page (en espagnol) de Sebastián Martín Ruiz:http://perso.wanadoo.es/smaranda/
(en) Manindra Agarwal, Nitin Saxena, Neeraj Kayal, « PRIMES is in P », Preprint, August 6, 2002, http://www.cse.iitk.ac.in/news/primality.html
(en) The « PRIMES is in P » FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
(en) Les 100,000 premiers nombres premiers, http://gutenberg.net/etext/65

Voir aussi

Crible d'Ératosthène ~ Crible de Sundaram ~ Nombre premier de Fermat ~ Nombre premier de Mersenne ~ GIMPS ~ Décomposition en produit de facteurs premiers

Nombre abondant - Nombre amical - Nombre déficient - Nombre parfait - Nombre quasi parfait - Nombre sociable

_n	p_n	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