Page d'accueil encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Nombre premier


Un nombre premier est un entier naturel strictement supérieur à 1, divisible seulement par 1 et par lui-même.
L'ensemble des nombres premiers est noté ℙ.

Sommaire

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é.

Histoire

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

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

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 en le nombre de chiffres de N. C'est le premier algorithme polynomial connu.

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 tout 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

Le plus grand nombre premier connu

Le plus grand nombre premier connu est 224 036 583-1 (ce nombre comporte 7 235 733 chiffres). Il s'agit du 41e nombre premier de Mersenne (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 record précédent était 220 996 011-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 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 256kk 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.

Applications

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.

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 sont appelés les nombres premiers de Fermat. À l'heure actuelle, F0, F1, F2, F3 et F4 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 1031512 + 9700079 · 1015753 + 1. 11 et 2 sont des palindromes triviaux.

Écart entre les nombres premiers

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 existe 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.

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 :

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

ou, de manière équivalente,

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

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

nous avons alors

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 :

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

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

Références

Merveilleux nombres premiers, de Jean-Paul Delahaye, Éditions Belin - Pour la Science

Liens externes

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



This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the GNU Free Documentation License Page HistoryOriginal ArticleWikipedia