Un nombre primer és un nombre enter superior a 1 que admet exactament dos divisors: 1 i ell mateix.Niven- Zuckerman: Introducción a la teoría de números Els nombres primers menors que 100 són:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 i 97.

Noteu el fet que tots els nombres naturals són divisibles entre ells mateixos i entre la unitat. Però els que no són primers, a més, també són divisibles per altres nombres. El nombre primer més petit és el 2 i, de fet, és l'únic nombre primer que és també parell, ja que qualsevol parell més gran és múltiple de dos.

El teorema fonamental de l'aritmètica estableix que qualsevol enter positiu superior a 1 pot representar-se sempre com un producte de nombres primers, i aquesta representació (factorització) és única. El teorema d'Euclides prova que existeixen infinits nombres primers. A més se sap que no hi ha límit per a la distància entre dos primers consecutius, això és, donat un nombre N, es poden trobar dos nombres primers a i b tals que entre a i b no hi ha altres nombres primers i que la diferència entre a i b és superior a N.

Encara no s'ha pogut provar, però es conjectura, que existeixen infinits nombres primers de la forma p1 = p₂ + 2 (sent p1 i p₂ primers) o primers bessons. Sí que s'ha provat que els únics primers trigèmins (primers de la forma p1 = p₂ + 2 i p₂ = p₃ + 2) són 3, 5 i 7.

Hi ha nombrosos algorismes per trobar nombres primers. El més senzill seria provar de dividir cada nombre per tots els inferiors o iguals a la seva arrel quadrada, però és molt poc eficient perquè requereix moltes divisions innecessàries; per exemple, un cop provat el dos, no cal provar tots els nombres parells, que se sap que seran divisibles per dos. Una extensió d'aquesta idea és el sedàs d'Eratòstenes.

A desembre de 2020, el nombre primer més gran conegut és un primer de Mersenne amb 24.862.048 dígits decimals.

Història L'os d'Ishango, data de fa més de 20.000 anys (abans de l'aparició de l'escriptura). El va trobar l'arqueòleg Jean de Heinzelin de Braucourt.Marcus du Sautoy, La symphonie des nombres premiers P.42 Presenta unes osques que semblen representar quatre nombres primers: 11, 13, 17 i 19. Alguns arqueòlegs interpreten aquest fet com una prova que qui les va fer coneixia els nombres primers. Amb tot, existeixen molt poques troballes que permetin entendre els coneixements que tenia realment l'home d'aquella època.Préhistoire de la géométrie: le problème des sources , article de Olivier Keller

Nombroses tauletes d'argila seca atribuïdes a les civilitzacions que es van anar succeint a Mesopotàmia al llarg del II mil·lenni aC mostren la resolució de problemes aritmètics i acrediten els coneixements de l'època. Per calcular divisions necessitaven conèixer l'invers dels naturals, s'han trobat tauletes amb aquestes taules d'inversos. En el sistema sexagesimal que empraven els babilonis per escriure els nombres, els inversos dels divisors de potències de 60 es calculen fàcilment, per exemple, dividir entre 24 equival a multiplicar per 150 () i desplaçar la coma sexagesimal dos llocs (ja que ). Per conèixer-ho calia una sòlida comprensió de la multiplicació, la divisió i la factorització dels enters.

En les matemàtiques egípcies, el càlcul de fraccions requeria coneixements sobre les operacions, la divisió de naturals i la factorització. Els egipcis només operaven amb les anomenades fraccions unitàries, és a dir, les que tenien numerador igual a 1 (. Les fraccions de numerador diferent d'1 s'escrivien com a suma d'inversos de naturals, si podia ser sense repetició ( en comptes de . Per a això segurament calia tenir una taula dels primers nombres primers.

La primera prova indiscutible del coneixement dels nombres primers es remunta al voltant de l'any 300 aC i es troba en els Elements d'Euclides (volums VII a IX). Euclides defineix els nombres primers, demostra que n'hi ha infinits, defineix el màxim comú divisor i el mínim comú múltiple i proporciona els algorismes per determinar-los que avui es coneixen com a algorisme d'Euclides. Els Elements contenen també el teorema fonamental de l'aritmètica i la manera de construir un nombre perfecte a partir d'un nombre primer de Mersenne.

El garbell o sedàs d'Eratòstenes, atribuït a Eratòstenes de Cirene, és un mètode senzill que permet trobar nombres primers.

miniatura|Pierre de Fermat. Després de l'època de la Grècia antiga, no hi va haver gaires avenços en l'estudi dels nombres primers fins al . El 1640 Pierre de Fermat va enunciar sense demostrar-lo el petit teorema de Fermat, més endavant el van demostrar Leibniz i Euler. Pot ser que molt abans ja es coneguera un cas especial d'aquest teorema a la Xina.Joseph Needham (Ed.) Mathematics and the Sciences of the Heavens and the Earth Science and Civilisation in China, Vol. 3 Ch. 19 Cambridge University Press, 1959

Fermat va enunciar la conjectura de què tots els nombres de la forma són primers (per això aquests nombres s'anomenen nombres de Fermat) i va verificar la hipòtesi fins a n = 4 (és a dir, 2¹⁶ + 1). Però Euler va demostrar que el següent nombre de Fermat (2³²+1) és compost (un dels seus factors primers és 641). De fet, fins avui no s'ha trobat cap altre nombre primer de Fermat a banda dels que ja coneixia Fermat.

El monjo francès Marin Mersenne va investigar els nombres primers de la forma 2p − 1, amb p primer. En honor seu, avui s'anomenen nombres de Mersenne.

Els treballs d'Euler en teoria de nombres contenen molts resultats referents als nombres primers. Va demostrar que la sèrie infinita (la suma dels inversos dels nombres primers) és divergent. El 1747 va demostrar que tots els nombres perfectes parells són de la forma , on el segon factor és un nombre primer de Mersenne.

A començaments del , Legendre i Gauss van conjecturar de forma independent que, quan tendeix a infinit, la quantitat de nombres primers menors o iguals que tendeixen asimptòticament a , on és el logaritme natural de . Les idees que Riemann va expressar en un treball de 1859 sobre la funció zeta van obrir un camí que conduiria a la demostració del teorema dels nombres primers. Hadamard i De la Vallée-Poussin, cada un per separat, van donar forma a aquest esquema i van aconseguir demostrar el teorema el 1896.

Actualment, en el cas de nombres grans, per comprovar si un nombre és primer, no es fa per divisions successives. Molts matemàtics han desenvolupat tests de primalitat, sovint restringits a categories específiques de nombres primers. Alguns exemples són el test de Pépin per als nombres de Fermat (1877), el teorema de Proth (~1878), la prova de Lucas-Lehmer per a nombres de Mersenne (a partir de 1856)The Largest Known Prime by Year: A Brief History Prime Curios!: 17014... 05727 (39 xifres) i el test de Lucas-Lehmer generalitzat. També existeixen algorismes per a nombres arbitraris (és a dir, sense necessitat que pertanyin a una determinada categoria), però són molt més lents, com és el cas del test APRT-cl, el test de primalitat per corbes el·líptiques i el AKS.

Durant molt de temps, es pensava que l'aplicació dels nombres primers era molt limitada fora de la matemàtica pura. Això va canviar en els anys 1970 amb el desenvolupament de la criptografia de clau pública, en la que els nombres primers eren la base dels primers algorismes com l'algorisme RSA.

Des del 1951, el nombre primer més gran conegut sempre ha estat descobert amb l'ajuda d'ordinadors. La recerca de nombres primers cada vegada més grans ha suscitat interès fins i tot fora de la comunitat matemàtica. En els últims anys han guanyat popularitat projectes de computació distribuïda tals com el GIMPS.

Definició Un nombre primer és un nombre natural que té dos i només dos divisors naturals diferents, l'1 i ell mateix.

Fins al , els matemàtics majoritàriament consideraven que l'1 era primer, entenent-se que la definició de nombre primer consistia en la divisibilitat entre 1 i ell mateix però que no requeria un nombre mínim de divisors diferents. Molts treballs matemàtics continuen sent vàlids malgrat considerar l'1 com un nombre primer, per exemple el treball de Stern i Zeisel. La llista de Derrick Norman Lehmer de nombres primers fins al 10.006.721, reimpresa fins a l'any 1956Hans Riesel, 'Prime Numbers and Computer Methods for Factorization '. New York: Springer (1994): 36 </ref> començava amb l'1 com a primer nombre primer.<ref>Richard K. Guy & John Horton Conway, 'The Book of Numbers '. New York: Springer (1996): 129 -130 El canvi de nomenclatura es va produir perquè que fos vàlid el següent enunciat del teorema fonamental de l'aritmètica: «tot nombre natural té una representació única com a producte de factors primers, llevat de l'ordre».""Why is the number one not prime? " ". Retrieved 2007-10-02. A més, els nombres primers tenen moltes propietats que no té l'1, tals com la relació del nombre amb el valor corresponent de la funció d'Euler o la funció suma de divisors.""Arguments for and against the primality of 1 "

Demostració de la infinitud dels nombres primers

La primera demostració de la infinitud dels nombres primers la proporcionà Euclides al llibre IX dels Elements. En la matemàtica moderna, sovint s'ha distorsionat la demostració i s'ha considerat un exemple clàssic de demostració indirecta (no constructiva), però la demostració original és constructiva. Euclides no diu explícitament que existeixen infinits nombres primers, l'enunciat que demostra és que «els nombres primers són més que qualsevol quantitat donada de nombres primers» i la demostració consisteix a construir un nombre primer que no és cap dels donats.

La demostració dels Elements comença amb una quantitat finita donada de nombres primers. Es construeix m el mínim comú múltiple d'aquests primers, i es considera el nombre m + 1. Aquest nombre pot ser primer o no ser-ho. Si ho és, aleshores ja s'ha trobat un primer més dels que hi havia al començament. Si no ho és, aleshores ha de tenir com a divisor un nombre primer. Aquest primer no és cap dels nombres primers amb què s'havia començat, ja que si ho fos aleshores seria divisor tant de m com de m + 1, i en conseqüència seria divisor d1, la qual cosa és absurda. Així doncs, també en aquest cas s'ha trobat un primer diferent dels del començament. Per tant, la demostració conclou, «els nombres primers són més que qualsevol quantitat donada de nombres primers».

L'enunciat modern, que «existeixen infinits nombres primers», s'ha de demostrar indirectament, per reducció a l'absurd. S'ha de suposar que el conjunt de tots els nombres primers és finit, i arribar a una contradicció. A part d'aquesta subtilesa, la idea de la demostració d'Euclides és vàlida, tot i que se sol substituir el concepte de mínim comú múltiple pel de producte, que en el cas de nombres primers és equivalent.

Per començar la demostració, suposem que el conjunt de nombres primers és finit, i que d'aquests primers P és el més gran. Construïm llavors el nombre (2·3·5·7·11·...·P) + 1, és a dir el producte de tots els nombres primers més u. Aquest nombre no és divisible per 2, ni per 3, ni per 5, ni, en definitiva, per cap nombre primer, ja que en tots els casos la divisió dona 1 com a resta. Per tant, només pot ser que (2·3·5·7·11·...·P) + 1 sigui primer o que sigui divisible per un altre nombre primer que està entre P i (2·3·5·7·11·...·P) + 1; en qualsevol dels dos casos hem trobat un nombre primer més gran que P, contradient la suposició inicial i, per tant, demostrant el teorema.

Propietats miniatura|Il·lustració que demostra que 11 és un nombre primer mentre que 12 no ho és. 2 és l'únic nombre primer parell, atès que qualsevol altre nombre parell més gran de dos és divisible entre 2. Per tant, l'expressió nombre primer senar, vol dir nombre primer més gran que 2.