eBabylone
.com

Un article de Wikipedia.y-project.com.

Un nombre premier est un entier naturel strictement supérieur à 1, n'admettant que deux entiers naturels diviseurs distincts: 1 et lui-même. L'ensemble des nombres premiers est parfois noté <math>\mathbb P</math>.

Sommaire 1 Exemples 2 Primalité 3 Histoire 3.1 Démonstration d'Euclide 3.2 Remarques 3.3 Autres démonstrations 4 Utilisation 5 Méthodes de calcul 6 Quelques propriétés des nombres premiers 7 Le plus grand nombre premier connu 8 Applications 9 Quelques types particuliers de nombres premiers 10 Écart entre les nombres premiers 11 Les formules menant aux nombres premiers 12 Généralisations 13 Questions ouvertes 14 Citation 15 Les 25 premiers nombres premiers 16 Curiosités 17 Références 18 Liens externes 19 Articles connexes

[] Exemples

Voici la liste complète 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é

La nature première ou non d'un nombre est appelée sa 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 puissances de facteurs premiers de façon unique, à l'ordre près, ainsi un nombre qui peut être décomposé en un produit de facteurs premiers n'est pas premier. Par exemple <math>12 = 2^2 \times 3</math> est composé, tout comme <math>14 = 7 \times 2</math>.

[] Histoire

Les nombres premiers sont étudiés depuis l'Antiquité. Euclide a démontré dans ses Éléments (proposition 20 du livre IX) que les nombres premiers sont en plus grande quantité que toute quantité proposée de nombres premiers. Autrement dit, il existe une infinité de nombres premiers.

[] Démonstration d'Euclide

Considérons une famille finie <math>p_1, p_2, ... p_n</math> de nombres premiers, et montrons qu'on peut former un nombre premier n'appartenant pas à cette famille. Posons P le produit de tous ces nombres premiers et formons le nombre N = P + 1. Lorsqu'on divise N par chaque nombre premier <math>p_i</math>, le reste vaut 1.

N est soit premier lui-même, soit composé. S'il est composé, n'étant divisible par aucun des nombres premiers de la famille <math>p_1, p_2, ... p_n</math>, il est alors le produit de nombres premiers qui ne font pas partie de cette famille.

En conclusion, quel que soit la quantité finie de nombres premiers considérée, il en existe un autre. Il existe donc une infinité de nombres premiers.

[] 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=4, on a N! = 24 et le nombre 25, loin d'être premier, est le carré de 5. 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 P en effectuant le produit de tous les nombres premiers inférieurs à une certaine borne q (primorielle) puis en lui ajoutant 1, c'est à dire P = 2 x 3 x 5 x ... x q + 1, en effet ce procédé ne marche pas par exemple pour : 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30 031 = 59 x 509. On ignore d'ailleurs si on peut obtenir une infinité de nombres premiers de cette façon.

• La démonstration d'Euclide introduit naturellement la suite dite d'Euclide-Mullin, définie de la façon suivante : <math>u_1 = 2</math> et <math>u_</math> est le plus petit nombre premier diviseur de <math>u_1u_2\cdots u_n+1</math>. Les premiers termes de cette suite sont :

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17,...

On ne connaît que les 43 premiers termes de cette suite et on ignore si tous les nombres premiers y apparaissent. Shanks a conjecturé en 1991 que tel était le cas.

[] Autres démonstrations

D'autres mathématiciens ont donné leur propre démonstration de ce résultat; Celle de Kummer est comparable à celle d'Euclide, mais en considérant le produit des nombres premiers, diminué de 1. La preuve d'Euler utilise le fait que <math>\prod_{p\;{\rm premier}} {1 \over 1 - {1 \over p}} = \sum_1^ {1 \over n}</math> qui est une série divergente. Le produit doit donc comporter une infinité de facteurs. 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.

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 <math>\mathbb Z/n\mathbb Z</math> (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^30 402 457-1, il comporte 9 152 052 chiffres. Il s'agit du 43^e nombre premier de Mersenne (M_30402457) annoncé le 25 décembre 2005 grâce aux efforts d'une collaboration qui porte le nom de GIMPS. Le record précédent était 2^{25 964 951}-1, et est aussi un nombre premier de Mersenne découvert par GIMPS le 12 février 2005. 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 des États-Unis d'Amérique.

[] 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 (voir primorielle). 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 <math>F_n = 2^ + 1</math> 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 et g₂ = 1. La suite (g_n) des écarts entre les nombres premiers a été étudiée en profondeur. On peut montrer que les écarts ne sont pas bornés, i.e. pour tout nombre entier naturel N, il existe un indice n tel que g_n > N. Il suffit pour cela de considérer l'intervalle suivant : [ N!+2 ; N!+N ] qui est un intervalle de longueur N?2 ne contenant pas de nombre premiers (quel que soit 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 :

<math>f(n) = 2 + (2n! \ \mod \ (n+1))</math>

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

<math>\pi(m) = \sum_^m \frac

{ \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) } </math>

ou, de manière équivalente,

<math> \pi(m) = \sum_^m \left[ {(j-1)! + 1 \over j} - \left[{(j-1)! \over j}\right] \right] </math>

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

<math>p_n = 1 + \sum_^ \left[ \left[ { n \over 1 + \pi(m) } \right]^{1 \over n} \right]</math>

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

<math>G(k) = k - 1 + \sum_^k \left[ {2 \over j} \left(1 + \sum_^\right]} \left(\left[{ j-1 \over s}\right] - \left[{j \over s}\right]\right) \right)\right] </math>

nous avons alors

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

[] 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 est l'ensemble des nombres premiers des entiers naturels. L'ensemble 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

« Les mathématiciens ont tâché jusqu'ici en vain de découvrir quelque ordre dans la progression des nombres premiers, et l'on a lieu de croire que c'est un mystère auquel l'esprit humain ne saurait jamais pénétrer. Pour s'en convaincre, on n'a qu'à jeter les yeux sur les tables des nombres premiers que quelques-uns se sont donné la peine de continuer au-delà de cent mille et l'on s'apercevra d'abord qu'il n'y règne aucun ordre ni règle. » Euler, 1751.

« 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	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és

• Le nombre premier suivant correspond aux 38 premiers chiffres de Pi (voir Sloane A005042) :
  

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, comprenant 19 un). Les répunits sont des nombres dont l'indice n est tel que 11...111 = (10^n - 1)/9. Les répunits suivants sont premiers (source : Sloane A004023) :
  • <math>R_2</math>,
  • <math>R_</math>,
  • <math>R_</math>,
  • <math>R_</math>,
  • <math>R_</math>,
  • <math>R_</math>,
  • <math>R_</math>.

[] Références

• Jean-Paul Delahaye, Merveilleux nombres premiers, Éditions Belin - Pour la Science, 2000 - ISBN 2701150175
• Paulo Ribenboim, The new book of big prime number records, Springer, 1996, ISBN 0387944575

[] 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/users/manindra/primality_v6.pdf (PDF)
• (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

[] Articles connexes

• 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 aimable
• Nombre amical
• Nombre déficient
• Nombre parfait
• Nombre presque parfait
• Nombre sociable

lt:Pirminis skai?iuszh-min-nan:Sò?-sò?  

Réagissez

Commentez l'encyclopédie:
Attention! tous les commentaites inaproprié seront supprimés

Titre:
Video YouTube ou google:	(doit être en rapport avec le sujet)
Votre mail:	(ne sera pas affiché sur le site)
Un pseudo:
Votre site:
Commentaire	(le html n'est pas autorisé, nombre de caractère maximum = 400)
	(Comment eBabylone 1.0 beta)

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/ nombre premier