Nombre premier

Le nombre 7 est premier car il admet exactement deux diviseurs positifs distincts.

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même). Ainsi, 1 n'est pas premier car il n'a qu'un seul diviseur entier positif ; 0 non plus car il est divisible par tous les entiers positifs. Par opposition, un nombre non nul produit de deux nombres entiers différents de 1 est dit composé. Par exemple 6 = 2 × 3 est composé, tout comme 12 = 3 × 4 ou 2 × 6, mais 11 est premier car 1 et 11 sont les seuls diviseurs de 11.

Les nombres 0 et 1 ne sont ni premiers ni composés. Certains mathématiciens considéraient autrefois (jusqu'au 19e siècle) 1 comme un nombre premier, mais durant le début du 20e siècle, un consensus exclut définitivement sa primalité [1].

Les vingt-cinq nombres premiers inférieurs à 100 sont :

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.

De telles listes de nombres premiers inférieurs à une borne donnée, ou compris entre deux bornes, peuvent être obtenues grâce à diverses méthodes de calcul. Mais il n'existe pas de liste exhaustive (finie) de nombres premiers, car il existe une infinité de nombres premiers (on le sait depuis l' Antiquité : voir Théorème d'Euclide sur les nombres premiers).

La notion de nombre premier est une notion de base en arithmétique élémentaire : le théorème fondamental de l'arithmétique assure qu'un nombre composé est factorisable en un produit de nombres premiers, et que cette factorisation est unique à l'ordre des facteurs près. Elle admet des généralisations importantes dans des branches des mathématiques plus avancées, comme la théorie algébrique des nombres, qui prennent ainsi à leur tour l'appellation d'arithmétique. Par ailleurs, de nombreuses applications industrielles de l'arithmétique reposent sur la connaissance algorithmique des nombres premiers, et parfois plus précisément sur la difficulté des problèmes algorithmiques qui leur sont liés ; par exemple certains systèmes cryptographiques et des méthodes de transmission de l'information. 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.

Découvert le , le plus grand nombre premier connu est le nombre premier de Mersenne 274 207 281 – 1, qui comporte plus de 22 millions de chiffres en écriture décimale.

Éléments historiques

Les entailles retrouvées sur l' os d'Ishango daté à plus de 20 000 ans avant notre ère, mis au jour par l'archéologue Jean de Heinzelin de Braucourt [2] et antérieur à l'apparition de l' écriture (antérieur à 3 200 ans av. J.-C.), semblent isoler quatre groupes de valeurs : 11, 13, 17 et 19. Certains archéologues l'interprètent comme la preuve de la connaissance des nombres premiers. Toutefois, il existe trop peu de découvertes permettant de cerner les connaissances réelles de cette période ancienne [3].

Des tablettes d'argile séchées attribuées aux civilisations qui se sont succédé en Mésopotamie durant le IIe millénaire IIe millénaire av. J.‑C. montrent la résolution de problèmes arithmétiques et attestent des premières connaissances de l'époque. Les calculs nécessitaient de connaître des tables d'inverses d'entiers (les réciproques) dont certaines ont été retrouvées. Dans le système sexagésimal utilisé par la civilisation babylonienne pour écrire les entiers, les réciproques des diviseurs des puissances de 60 (nombres réguliers) se calculent facilement : par exemple, diviser par 24, c'est multiplier par 2 × 60 + 30 et décaler de deux places le rang. Leur connaissance nécessitait une bonne compréhension de la multiplication, de la division et de la factorisation d'entiers. On peut alors légitimement penser qu'ils avaient remarqué la présence de nombres particuliers : les nombres premiers. Mais il n'existe pas de preuve attestant de leur connaissance véritable [4].

Dans les mathématiques égyptiennes, le calcul fractionnaire demandait aussi des connaissances sur les opérations, les divisions d’entiers et les factorisations. Les Égyptiens ne notaient que les inverses d’entiers (1/2, 1/3, 1/4, 1/5, ...) ; l’écriture des fractions se faisait en additionnant des inverses d'entiers, si possible sans répétition (1/2 + 1/6 au lieu de 1/3 + 1/3). Disposer d’une liste des premiers nombres premiers devait être nécessaire.

La première trace incontestable de la présentation des nombres premiers remonte à l'Antiquité (vers 300 av. J.-C.), et se trouve dans les Éléments d’ Euclide (livres VII à IX). Euclide donne la définition des nombres premiers, la preuve de leur infinité, la définition du plus grand commun diviseur (pgcd) et du plus petit commun multiple (ppcm), et les algorithmes pour les déterminer, aujourd’hui appelés algorithmes d’Euclide. Les connaissances présentées lui sont toutefois bien antérieures.

Jalons symboliques

L'esprit ludique et l'émulation ont amené des mathématiciens à définir des seuils de gigantisme pour les nombres premiers, exprimés en nombre de chiffres en base dix. Parmi ces records, battus ou à battre, on notera en particulier :

En janvier 2016, 149 méganombres premiers étaient connus [5]. Le premier à être découvert fut, en 1999, le nombre de Mersenne 26 972 593 − 1 avec ses 2 098 960 chiffres [6], [7], grâce aux efforts du projet collaboratif de calcul distribué Great Internet Mersenne Prime Search (GIMPS).

L' Electronic Frontier Foundation offre des prix de calcul coopératif pour encourager les internautes à contribuer à la résolution de problèmes scientifiques par le calcul distribué. Le GIMPS a ainsi reçu 100 000 dollars pour sa découverte en 2008 du premier nombre premier d'au moins 10 millions de chiffres décimaux. L'EFF offre encore 150 000 et 250 000 dollars respectivement pour la découverte du premier nombre premier de 100 millions et 1 milliard de chiffres décimaux [8].

Historique du plus grand nombre premier connu

Article détaillé : Plus grand nombre premier connu.

Le record du plus grand nombre premier connu a presque toujours été trouvé parmi les nombres de Mersenne, comme le dernier en date, M74207281 = 274 207 281 – 1, un nombre à 22 338 618 chiffres décimaux.

Historique des nombres premiers tous connus ou dénombrés en dessous d'un seuil

Découvrir un nombre premier plus grand que tous ceux déjà connus n'implique pas de connaître tous les nombres premiers intermédiaires.

Plus généralement, la recherche de tous les nombres premiers inférieurs à un nombre donné (premier ou non) constitue un défi mathématique spécifique.

Ce défi fut notamment relevé, jusqu'au seuil de 100 000 000, par le mathématicien autrichien Jakob Philipp Kulik  (de) ( 1793- 1863) [9] :

Date Seuil Quantité (*) Vérificateurs Méthode
Antiquité 1 000 168 Ératosthène, Euclide [10] Essais par division [10]
1746 [10] 100 000 9 592  ?
1797 [10] 400 000 33 860
1811 [10] 1 000 000 78 498
1863 [10] 100 000 000 5 761 455 Jakob Philipp Kulik [10]
2010 [11] 276 = 75 557 863 725 914 323 419 136 1 462 626 667 154 509 638 735 Jens Franke  (de) et al. [11] Évaluation directe de [11]
277 = 151 115 727 451 828 646 838 272 2 886 507 381 056 867 953 916
1024 = 1 000 000 000 000 000 000 000 000 18 435 599 767 349 200 867 866

Notes :

(*)    est la quantité totale de nombres premiers situés sous le seuil (c'est-à-dire dans l'intervalle d'entiers ).

La connaissance de par un calcul algorithmique n'implique pas nécessairement que chacun des nombres premiers soit immédiatement identifiable.
La décomposition en facteurs permet au contraire d'identifier les nombres premiers individuellement.
Other Languages
Afrikaans: Priemgetal
Alemannisch: Primzahl
aragonés: Numero primero
Ænglisc: Frumtæl
العربية: عدد أولي
مصرى: عدد اولى
অসমীয়া: মৌলিক সংখ্যা
azərbaycanca: Sadə ədəd
žemaitėška: Pėrmėnis skaitlios
беларуская: Просты лік
беларуская (тарашкевіца)‎: Просты лік
български: Просто число
brezhoneg: Niver kentael
bosanski: Prost broj
català: Nombre primer
čeština: Prvočíslo
Cymraeg: Rhif cysefin
dansk: Primtal
Deutsch: Primzahl
Zazaki: Amaro primal
Ελληνικά: Πρώτος αριθμός
English: Prime number
Esperanto: Primo
español: Número primo
eesti: Algarv
euskara: Zenbaki lehen
فارسی: عدد اول
suomi: Alkuluku
Võro: Algarv
føroyskt: Primtal
Nordfriisk: Primtaal
贛語: 質數
Hawaiʻi: Helu kumu
hrvatski: Prosti broj
hornjoserbsce: Primowa ličba
Kreyòl ayisyen: Nonm premye
magyar: Prímszámok
Հայերեն: Պարզ թիվ
interlingua: Numero prime
Bahasa Indonesia: Bilangan prima
italiano: Numero primo
日本語: 素数
Patois: Praim nomba
la .lojban.: nalfendi kacna'u
Basa Jawa: Wilangan prima
қазақша: Жай сан
ភាសាខ្មែរ: ចំនួនបឋម
한국어: 소수 (수론)
Lëtzebuergesch: Primzuel
Limburgs: Priemgetaal
lumbaart: Numer primm
latviešu: Pirmskaitlis
македонски: Прост број
монгол: Анхны тоо
Bahasa Melayu: Nombor perdana
မြန်မာဘာသာ: သုဒ္ဓကိန်း
Plattdüütsch: Primtall
Nederlands: Priemgetal
norsk nynorsk: Primtal
norsk: Primtall
ਪੰਜਾਬੀ: ਅਭਾਜ ਸੰਖਿਆ
Piemontèis: Nùmer prim
پنجابی: پرائم نمبر
português: Número primo
română: Număr prim
sicilianu: Nùmmuru primu
srpskohrvatski / српскохрватски: Prost broj
Simple English: Prime number
slovenčina: Prvočíslo
slovenščina: Praštevilo
Soomaaliga: Tiro mutuxan
српски / srpski: Прост број
svenska: Primtal
Kiswahili: Namba tasa
ślůnski: Pjyrszo nůmera
தமிழ்: பகா எண்
Türkçe: Asal sayı
українська: Просте число
اردو: مفرد عدد
oʻzbekcha/ўзбекча: Tub son
vèneto: Nùmaro primo
vepsän kel’: Palatoi lugu
Tiếng Việt: Số nguyên tố
West-Vlams: Priemgetal
хальмг: Экн тойг
ייִדיש: פרימצאל
中文: 素数
文言: 質數
Bân-lâm-gú: Sò͘-sò͘
粵語: 質數