Nombre primer

Un nombre primer és un nombre enter superior a 1 que admet exactament dos divisors: 1 i ell mateix.^[1][2] 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 entre 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 p₁ = p₂ + 2 (sent p₁ i p₂ primers) o primers bessons. Sí que s'ha provat que els únics primers trigèmins (primers de la forma p₁ = 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 sabem 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.