Número primo

Archiu:Prime number Cuisenaire rods 7.png

Número primo

Archiu:Primencomposite0100.svg

Número natural de zero a cent. Els número primo estan marcats en roig.

Archiu:Prime num le 400.png

La distribució dels número primo (traços blaus) fins al 400

En matemàtiques, un número primo és un número natural major a 1 que té únicament dos divisores positius distints: ell mateix i el 1. Pel contrari, els número compuesto són els número natural que tenen algun divisor natural a banda de sí mateixos i de l'1, i, per lo tant, poden factorizarse. El número 1, per conveni, no es considera ni primer ni compost.

Els 168 número primo menors que 1000 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, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991 i 997 Plantilla:OEIS.

El primer número primo a partir del número mil és el 1009, despuix de dèu mil és el Plantilla:Nts, a partir de cent mil és el Plantilla:Nts i immediatament despuix d'un milló és el Plantilla:Nts.

La propietat de ser número primo es denomina primalidad.

En la teoria algebraica de números, els número primo es denominen números racionals cosins per a distinguir-los dels números gaussianos primers. La primalidad no depén del sistema de numeració, pero sí de l'anell a on s'estudia la primalidad. Dos és primer racional; no obstant té factors com a sancer gaussiano: 2 = (1+i)*(1-i).

L'estudi dels número primo és una part important de la teoria de números, branca de les matemàtiques que tracta les propietats, bàsicament aritmètiques, dels número entero.

Els número primo estan presents en algunes conjectura centenàries tals com la hipòtesis de Riemann i la conjectura de Goldbach, resolta per Harald Helfgott en la seua forma dèbil.

La distribució dels número primo és un assunt reiteratiu d'investigació en la teoria de números: si es consideren números aisladamente, els cosins semblaren estar distribuïts de modo provabilístic, pero la distribució «global» dels número primo s'ajusta a lleis ben definides.

Història

L'Orient prehelénico

Archiu:Os d'Ishango caps block 5

Image del os de Ishango expost en el Real Institut Belga de Ciències Naturals.

Les muescas presents en l'os de Ishango, que data de fa més de Plantilla:Nts anys (anterior per tant a l'aparició de l'escritura) i que va ser trobat per l'arqueòlec Jean de Heinzelin de Braucourt, semblen aïllar quatre número primo: 11, 13, 17 i 19. Alguns arqueòlecs interpreten este fet com la prova del coneiximent dels número primo. En tot, existixen molt poques troballes que permeten discernir els coneiximents que tenia realment l'home d'aquella época.

Numeroses tablillas d'argila cuita atribuïdes a les civilisacions que es varen ser succeint en Mesopotamia a lo llarc de el II mileni a. C. mostren la resolució de problemes aritmètics i atesten els coneiximents de l'época. Els càlculs requerien conéixer els inversos dels naturals, que també s'han trobat en tablillas. En el sistema sexagesimal que ampraven els babilonios per a escriure els números, els inversos dels divisores de potències de 60 (números regulars) es calculen fàcilment; per eixemple, dividir entre 24 equival a multiplicar per 150 (2·60+30) i córrer la menge sexagesimal dos llocs. El coneiximent matemàtic dels babilonios necessitava una sòlida comprensió de la multiplicació, la divisió i la factorización dels naturals.

En les matemàtiques egipcíaques, el càlcul de fracciones requeria coneiximents sobre les operacions, la divisió de naturals i la factorización. Els egipcíacs solament operaven en les cridades fraccions egipcíaques, suma de fraccions unitàries, és dir, aquelles el numerador de les quals és 1, com $\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\dots$, per lo que les fraccions de numerador distint d'1 s'escrivien com sumixca d'inversos de naturals, a ser possible sense repetició $(\frac{2}{3}=\frac{1}{2}+\frac{1}{6}$ en lloc de $\frac{1}{3}+\frac{1}{3})$. És per això que, en certa manera, tenien que conéixer o intuir els número primo.

Antiga Grècia

Archiu:Oxyrhynchus papyrus with Euclid's Elements.jpg

Un fragment dels Elements de Euclides trobat en Oxirrinco

La primera prova indiscutible del coneiximent dels número primo es remonta a al voltant de l'any 300 a. C. i es troba en els Elements d'Euclides (toms VII a IX). Euclides definix els número primo, demostra que hi ha infinits d'ells, definix el màxim comú divisor i el mínim comú múltiple i proporciona un método per a determinar-los que hui en dia es coneix com l'algoritme de Euclides. Els Elements contenen aixina mateix el teorema fonamental de l'aritmètica i la manera de construir un número perfecte a partir d'un número primo de Mersenne.

La garbell de Eratóstenes, atribuïda a Eratóstenes de Cirene, és un método senzill que permet trobar número primo. Hui en dia, empero, els majors número primo que es troben en l'ajuda d'ordenadors ampren atres algoritmes més ràpits i complexos.

Des de l'época de la Renaixença

Archiu:Pierre de Fermat.jpg

Pierre de Fermat

Despuix de les matemàtiques gregues va haver pocs alvanços en l'estudi dels número primo fins al sigle xvii. En 1640 Pierre de Fermat va establir (encara que sense demostració) el menuda teorema de Fermat, posteriorment demostrat per Leibniz i Euler. És possible que molt abans es coneguera un cas especial de dit teorema en China.

Fermat conjeturó que tots els números de la forma 2²ⁿ+1 eren primers (per la qual cosa li'ls coneix com números de Fermat) i va verificar esta propietat fins a n = 4 (és dir, 2¹⁶ + 1). No obstant, el número de Fermat 2³² + 1 és compost (un dels seus factors primers és 641), com va demostrar Euler. De fet, fins als nostres dies no es coneix cap número de Fermat que siga primer a banda dels que ya coneixia el propi Fermat.

El monge francés Marin Mersenne va investigar els número primo de la forma 2^p − 1, en p primer. En el seu honor, li'ls coneix com números de Mersenne.

En el treball de Euler en teoria de números es troben molts resultats que concernixen als número primo. Va demostrar la divergència de la série $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\dots$, i en 1747 va demostrar que tots els número perfecte parells són de la forma 2^p-1(2^p - 1), a on el segon factor és un número primo de Mersenne. Es creu que no existixen número perfecte impars, pero encara és una qüestió oberta.

Al començament del sigle xix, Legendre i Gauss conjeturaron de forma independent que, quan n tendix a infinit, el número de cosins menors o iguals que n és asintòtic a $\frac{n}{\ln (n)}$, a on ln(n) és el logaritmo natural de n. Les idees que Bernhard Riemann va plasmar en un treball de 1859 sobre la funció zeta varen descriure el camí que conduiria a la demostració del teorema dels número primo. Hadamard i De la Vallée-Poussin, cada u per separat, varen donar forma a este esquema i varen conseguir demostrar la teorema en 1896.

Actualment no es comprova la primalidad d'un número per divisions successives, a lo manco no si el número és relativament gran.

Durant el sigle xix es varen desenrollar algoritmes per a saber si un número és primer o no factorizando completament el número següent (p+1) o l'anterior (p-1). Dins del primer cas es troba el test de Lucas-Lehmer, desenrollat a partir de 1856. Dins del segon cas es troba el test de Pépin per als números de Fermat (1877). El cas general de test de primalidad quan el número immediatament anterior es troba completament factorizado es denomina test de Lucas.

Posteriorment es varen trobar algoritmes de primalidad en solament obtindre una factorización parcial de p+1 o p-1. Eixemples d'estos algoritmes són el test de Proth (desenrollat al voltant de 1878) i el test de Pocklington (1914). En estos algoritmes es requerix que el producte dels factors primers coneguts de p-1 siga major que la raïl quadrada de p. Més recentment, en 1975, Brillhart, Lehmer i Selfridge varen desenrollar el test de primalidad BLS que solament requerix que dit producte siga major que la raïl cúbica de p. El millor método conegut d'esta classe és el test de Koniaguin i Pomerance de l'any 1997, que requerix que dit producte siga major que p^3/10.

A partir de la década de 1970 varis investigadors varen descobrir algoritmes per a determinar si qualsevol número és primer o no en complexitat subexponencial, lo que permet realisar tests en números de mils de dígits, encara que són molt més llents que els métodos anteriors. Eixemples d'estos algoritmes són el test APRT-CL (desenrollat en 1979 per Adleman, Pomerance i Rumely, en millores introduïdes per Cohen i Lenstra en 1984), a on s'usen els factors de p^m-1, a on l'exponent m depén del tamany del número que la seua primalidad es desija verificar, el test de primalidad per curves elíptiques (desenrollat en 1986 per S. Goldwasser, J. Kilian i millorat per A. O. L. Atkin), que entrega un certificat consistent en una série de números que permet despuix confirmar ràpidament si el número és primer o no. El desenroll més recent és el test de primalidad AKS (2002), que si ben la seua complexitat és polinòmica, per als números que pot manejar la tecnologia actual és el més llent dels tres.

Durant molt temps, es pensava que l'aplicació dels número primo era molt llimitada fòra de la matemàtica pura. Açò va canviar en els anys 1970 en el desenroll de la criptografia de clau pública, en la que els número primo formaven la base dels primers algoritmes, tals com l'algoritme RSA.

Des de 1951, el major número primo conegut sempre ha segut descobert en l'ajuda d'ordenadors. La busca d'número primo cada volta majors ha suscitat interés inclús fòra de la comunitat matemàtica. En els últims anys han guanyat popularitat proyectes de computació distribuïda tals com el GIMPS, mentres els matemàtics seguixen investigant les propietats dels número primo.

El número 1 no es considera primer

La qüestió sobre si el número 1 deu o no considerar-se primer està basada en la convenció. Abdós postures tenen les seues ventages i els seus inconvenients. De fet, fins al sigle xix, els matemàtics en la seua majoria ho consideraven primer. Molts treballs matemàtics seguixen sent vàlits a pesar de considerar l'1 com un número primo, com, per eixemple, el de Stern i Zeisel. La llista de Derrick Norman Lehmer d'número primo fins al 10.006.721, reimpresa fins a l'any 1956, escomençava en l'1 com a primer número primo.

Actualment, la comunitat matemàtica s'inclina per no considerar a l'1 en la llista dels número primo. Esta convenció, per eixemple, permet una formulació molt econòmica del teorema fonamental de l'aritmètica: «tot número natural té una representació única com a producte de factors primers, llevat l'orde». Ademés, els número primo tenen numeroses propietats de les que carix l'1, tals com la relació del número en el valor corresponent de la funció φ de Euler o la funció divisor. Cap també l'igualtat per a tot $n$ sancer positiu, $1=1^n$, lo que permetria dir que té $n$ factors.

Propietats dels número primo

Teorema fonamental de l'aritmètica

Artícul principal → Teorema fonamental de l'aritmètica.

Archiu:Prime rectangles.png

Esta ilustració mostra que l'11 és un número primo, pero el 12 no ho és.

El teorema fonamental de l'aritmètica establix que tot número natural té una representació única com a producte de factors primers, llevat l'orde. Un mateix factor primer pot aparéixer vàries voltes. L'1 es representa llavors com un producte buit.

Es pot considerar que els número primo són les «rajoles» en els que es construïx qualsevol número natural. Per eixemple, es pot escriure el número 23.244 com a producte de 2²·3·13·149, i qualsevol atra factorización del 23.244 com a producte d'número primo serà idèntica llevat per l'orde dels factors.

L'importància d'esta teorema és una de les raons per a excloure l'1 del conjunt dels número primo. Si s'admetera l'1 com a número primo, l'enunciat de la teorema requeriria aclariments adicionals.

A partir d'esta unicitat en la factorización en factors primers es desenrollen atres conceptes molt utilisats en matemàtiques, tals com el mínim comú múltiple, el màxim comú divisor i la coprimalidad de dos o més números. Aixina,

• El mínim comú múltiple de dos o més números és el menor dels múltiples comuns de tots ells. Per a calcular-ho, es descomponen els números en factors primers i es prenen els factors comuns i no comuns en el seu màxim exponent. Per eixemple, el mínim comú múltiple de 10=2·5 i 12=2²·3 és 60=2²·3·5.
• El màxim comú divisor de dos o més números és el major dels divisores comuns de tots ells. És igual al producte dels factors comuns en el seu mínim exponent. En l'eixemple anterior, el màxim comú divisor de 10 i 12 és 2.
• Finalment, dos o més números són coprimos, o cosins entre sí, si no tenen cap factor primer comú; és dir, si el seu màxim comú divisor és 1. Un número primo és, aixina, coprimo en qualsevol número natural que no siga múltiple d'ell mateixa.

Atres propietats

• En la seua escritura en el sistema de numeració decimal, tots els número primo, llevat el 2 i el 5, té com el guarisme de les unitats un d'estos: 1, 3, 7 o 9. En general, en qualsevol sistema de numeració, tots els número primo llevat un número finito acaben en una sifra que és coprima en la base.
• De lo anterior es deduïx que tots els número primo llevat el 2 són de la forma 4n + 1 o be 4n + 3. Igualment, tots els número primo llevat el 2 i el 3 són de la forma 6n + 1 o 6n - 1.

• En la progressió aritmètica 3, 7, 11, 15, 19, 23, 27, 31, …, hi ha una cantitat infinita d'número primo de la forma 4n-1, n natural.
• En la progressió aritmètica 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, …, hi ha una cantitat infinita d'número primo de la forma 6k+1, k natural.
• Lema de Euclides: Si p és un número primo i divisor del producte de número entero ab, llavors p és divisor de a o de b.
• Menuda teorema de Fermat: Si p és primer i a és algun número natural diferent d'1, llavors a^p - a és divisible per p.
• Si un número p no dividix al número m, llavors (p; m) =1
• Si p és primer distint de 2 i 5, $\frac{1}{p}$ sempre és un número periòdic en la seua representació decimal, de periodo p − 1 o un divisor de p − 1. Açò es pot deduir directament a partir de la chicoteta teorema de Fermat. $\frac{1}{p}$ expressat en base q (en lloc d'en base 10) té propietats similars, sempre que p no siga un factor primer de q.
• Teorema de Wilson: Un número natural n > 1 és primer si i solament si el factorial (n - 1)! + 1 és divisible per n. Aixina mateix, un número natural n > 4 és compost si i solament si (n - 1)! és divisible per n.
• La característica de tot cos és, o be zero, o be un número primo.
• Primera teorema de Sylow: Si G és un grup finito, p primer i pⁿ és la major potència de p que dividix l'orde de G. Llavors, existix un subgrup de G d'orde pⁿ.
• Teorema de Cauchy: Si G és un grup finito i p és un número primo que dividix a l'orde de G, llavors G conté un element d'orde p.
• La constant de Copeland-Erdős 0,235711131719232931374143…, obtinguda per concatenació dels número primo en el sistema decimal, és un número irracional.
• El valor de la funció zeta de Riemann en cada punt del pla complex es dona com una continuació meromorfa d'una funció definida per un producte sobre el conjunt de tots els cosins per a Re(s) > 1:

$\zeta (s)=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n^s}=\prod _p\frac{1}{1-p^{-s}}.$

En la regió a on és convergent, este producte indexat pels número primo es pot calcular, obtenint-se diversos valors, alguns d'ells importants en teoria de números. Els dos primers són:

$\prod _p\frac{1}{1-p^{-1}}=\mathrm{\infty }$ (corresponent a la série harmònica, relacionat en l'infinitud d'número primo).

$\prod _p\frac{1}{1-p^{-2}}=\frac{{\pi }^2}{6}$ (corresponent al problema de Basilea).

En general $\frac{1}{{\pi }^n}\prod _p\frac{1}{1-p^{-n}}$ és un número racional quan n és un número entero positiu parell.

• l'anell $\mathbb{Z}/p\mathbb{Z}$ és un cos si i solament si p és primer. Equivalentemente: p és primer si i solament si φ(p) = p − 1.
• Si p > 1, el polinomi x ^p-1+x ^p-2+ ··· + 1 és irreducible sobre $\mathbb{Z}/p\mathbb{Z}$ si i solament si p és primer.
• Un número natural n és primer si i solament si el n-ésimo polinomi de Chebyshov de la primera espècie T_n(x), dividit entre x, és $2=i(1-i{)}^2$ irreducible en $\mathbb{Z}[x]$. Ademés, T_n(x) ≡ xⁿ si i solament si n és primer.
• No tot número primo és un número gaussiano primer; tal el cas de 2, que com a sancer gaussiano admet la descomposició $2=i(1-i{)}^2$ dò de la norma de $1-i$ és 2, per lo tant no és unitat en Z[i].
• Els número primo de la forma $4n+1$ són igual a la suma de dos quadrats perfectes; per lo que no són números gaussianos cosins. Mentres que els número primo de la forma $4n+3$ sí són números gaussianos cosins.

• Tot número racional primer és un número gaussiano sancer, sense ser necessàriament número gaussiano primer.

Número primo i funcions aritmètiques

Les funcions aritmètiques, és dir, funcions reals o complexes, definides sobre un conjunt d'número natural, eixerciten un paper crucial en la teoria de números. Les més importants són les funcions multiplicativas, que són aquelles funciones f en les quals, per a cada parell de números coprimos (a,b) es té

$f(ab)=f(a)f(b)$.

Alguns eixemples de funcions multiplicativas són la funció φ de Euler, que a cada n associa el número de sancers positius menors i coprimos en n, i les funcions τ i σ, que a cada n associen respectivament el número de divisores de n i la suma de tots ells. El valor d'estes funcions en les potències d'número primo és

$\mathrm{\phi }(p^m)=p^m-p^{m-1}$,

$\mathrm{\tau }(p^m)=m+1$,

$\mathrm{\sigma }(p^m)=1+p^2+p^3+\cdots +p^m$.

Gràcies a la propietat que les definix, les funcions aritmètiques poden calcular-se fàcilment a partir del valor que prenen en les potències d'número primo. De fet, donat un número natural n d'factorización

$n=p_1^{q_1}\cdots p_a^{q_a}$

es té que

$f(n)=f(p_1^{q_1})\cdots f(p_a^{q_a})$

en lo que s'ha reconduït el problema de calcular f(n) al de calcular f sobre les potències dels número primo que dividixen n, valors que són generalment més fàcils d'obtindre per mig d'una fòrmula general. Per eixemple, per a conéixer el valor de la funció φ sobre n=450=2·3²·5² n'hi ha prou en calcular

$\mathrm{\phi }(450)=\mathrm{\phi }(2)\cdot \mathrm{\phi }(3^2)\cdot \mathrm{\phi }(5^2)=(2-1)\cdot (9-3)\cdot (25-5)=120$.

Característiques del conjunt dels número primo

Infinitud dels número primo

Vore també: Infinitud dels número primo

Existixen infinits número primo. Euclides va realisar la primera demostració al voltant de l'any 300 a. C. en el llibre IX de la seua obra Elements. Una adaptació comuna d'esta demostració original seguix aixina: Es pren un conjunt arbitrari pero finito d'número primo p₁, p₂, p₃, ···, p_n, i es considera el producte de tots ells més un, $q=p_1\times p_2\times p_3\dots \times p_n+1$. Este número és òbviament major que 1 i distint de tots els primers p_i de la llista. El número q pot ser primer o compost. Si és primer tindrem un número primo que no està en el conjunt original. Si, pel contrari, és compost, llavors existirà algun factor p que dividixca a q. Suponent que p és algun dels p_i, es deduïx llavors que p dividix a la diferència $q-p_1\times p_2\times p_3\dots \times p_n=1$, pero cap número primo dividix a 1, és dir, s'ha aplegat a un absurt per supondre que p està en el conjunt original. La conseqüència és que el conjunt que es va triar no és exhaustiu, ya que existixen número primo que no pertanyen a ell, i açò és independent del conjunt finito que es prenga.

Per tant, el conjunt dels número primo és infinit.

Si es pren com a conjunt el dels n primers número primo, llavors $q=p_1\times p_2\times p_3\dots \times p_n+1=p_n\mathrm{♯}+1$, a on p_n# és lo que es diu primorial de p_n. Un número primo de la forma p_n# +1 es denomina número primo de Euclides en honor al matemàtic grec. També es pot elaborar una demostració similar a la de Euclides prenent el producte d'un número donat d'número primo menys un, el lloc del producte d'eixos número primo més un. En eixe sentit, es denomina número primo primorial a un número primo de la forma p_n# ± 1.

No tots els números de la forma p_n# +1 són primers. En este cas, com se seguix de la demostració anterior, tots els factors primers deuran ser majors que n. Per eixemple: 2·3·5·7·11·13+1=30031=59·509

Atres matemàtics han demostrat l'infinitud dels número primo en diversos métodos procedents d'àrees de les matemàtiques tals com al àlgebra conmutativa i la topología. (Vore demostració de Furstenberg de la infinitud dels número primo).

Algunes d'estes demostracions es basen en l'us de successions infinites en la propietat de que cada u dels seus térmens és coprimo en tots els demés, per lo que es crea una biyección entre els térmens de la successió i un subconjunt (infinit) del conjunt dels cosins.

Una successió que complix dita propietat és la successió de Euclides-Mullin, que deriva de la demostració euclídea de la infinitud dels número primo, ya que cada u dels seus térmens es definix com el factor primer més chicotet d'un més el producte de tots els térmens anteriors. La successió de Sylvester es definix de forma similar, ya que cada u dels seus térmens és igual a un més el producte de tots els anteriors. Encara que els térmens d'esta última successió no són necessàriament tots primers, cada u d'ells és coprimo en tots els demés, per lo que es pot triar qualsevol dels seus factors primers, per eixemple, el menor d'ells, i el conjunt resultant serà un conjunt infinit els térmens del qual són tots primers.

Atres enunciats que impliquen la infinitud dels número primo

Un resultat encara més fort, i que implica directament la infinitud dels número primo, va ser descobert per Euler en el sigle xviii. Establix que la serie $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\dots$ és divergent. Un dels teoremes de Mertens concreta més, establint que

$\sum _{p\le n}\frac{1}{p}=\ln \ln n+O(1)$

a on l'expressió O(1) indica que eixe terme està acotat entre -C i C per a n major que n₀, a on els valors de C i n₀ no estan especificats.

Un atre resultat és el teorema de Dirichlet, que diu aixina:

En tota progressió aritmètica an = a + n·q, a on els sancers positius a, q ≥ 1 són cosins entre sí, existixen infinits térmens que són primers.

El postulat de Bertrand enuncia aixina:

Si n és un número natural major que 3, llavors sempre existix un número primo p tal que n < p < 2n- 2.

Una manera més dèbil pero elegant de formular-ho és que, si n és un número natural major que 1, llavors sempre existix un número primo p tal que n < p < 2n. Açò supon que, en una progressió geomètrica de primer terme sancer major que 3 i raó igual a 2, entre cada terme de la progressió i el següent, es té a lo manco un número primo.

Freqüència dels número primo

Vore també: Teorema dels número primo

$n$	$\pi (n)$	$\pi (n)-\frac{n}{\ln n}$	$\mathrm{L}\mathrm{i}(n)-\pi (n)$	$\frac{n}{\pi (n)}$
10	4	−0,3	2,2	2,500
102	25	3,3	5,1	4,000
103	168	23	10	5,952
104	1.229	143	17	8,137
105	9.592	906	38	10,425
106	78.498	6.116	130	12,740
107	664.579	44.158	339	15,047
108	5.761.455	332.774	754	17,357
109	50.847.534	2.592.592	1.701	19,667
1010	455.052.511	20.758.029	3.104	21,975
1011	4.118.054.813	169.923.159	11.586	24,283
…	…	…	…	…

Archiu:PrimeNumberTheorem.png

Comparació entre les funcions π(n) (blava), n / ln n (verda) i Li(n) (roig); es pot vore que l'aproximació de π(n) en Li(n) és millor que la que hi ha en $\frac{n}{\ln n}$

Una volta demostrat la infinitud dels número primo, cal preguntar-se cóm es distribuïxen els cosins entre els número natural, és dir, cuán freqüents són i on s'espera trobar el n-ésimo número primo. Este estudi ho varen iniciar Gauss i Legendre de forma independent a finals del sigle xviii, per al qual varen introduir la funció enumerativa dels número primo π(n), i conjeturaron que el seu valor anara aproximadament

$\pi (n)\sim \frac{n}{\ln n}$.

L'encabotament de demostrar esta conjectura va comprendre tot el sigle xix. Els primers resultats varen ser obtinguts entre 1848 i 1859 per Chebyshov, qui va demostrar utilisant métodos purament aritmètics l'existència de dos constants A i B tals que

$A\le \frac{\pi (n)}{\frac{n}{\ln n}}\le B$

per a n suficientment gran. Va conseguir demostrar que, si existia el llímit del cocient d'aquelles expressions, est devia ser 1.

Hadamard i De la Vallée-Poussin varen elaborar una demostració en 1896, independentment l'u de l'atre, usant métodos similars, basats en l'us de la funció zeta de Riemann, que havia segut introduïda per Bernhard Riemann en 1859. Va caldre esperar fins a 1949 per a trobar una demostració que usara sol métodos elementals (és dir, sense usar l'anàlisis complex). Esta demostració va ser ideada per Selberg i Erdős. Actualment, es coneix la teorema com teorema dels número primo.

El mateix Gauss va introduir una estimació més precisa, utilisant la funció logaritmo integral:

$\pi (n)\approx \mathrm{L}\mathrm{i}(n)=\underset{2}{\overset{n}{\int }}\frac{1}{\ln x}\mathrm{d}x$.

En 1899 De la Vallée-Poussin va demostrar que l'error que es comet aproximant $\pi (n)$ d'esta forma és

$\pi (n)-\mathrm{L}\mathrm{i}(n)=O\left(n{\mathrm{e}}^{-a\sqrt{\ln n}}\right)=O\left(\frac{n}{(\ln n{)}^m}\right)$

per a una constant positiva a i per a cada sancer m. Este resultat va ser llaugerament millorat a lo llarc dels anys. Per una atra part, en 1901 Von Koch va mostrar que si la hipòtesis de Riemann era certa, es tenia la següent estimació, més precisa:

$|\pi (n)-\mathrm{L}\mathrm{i}(n)|=O(\sqrt{n}\ln n).$

Una forma equivalent a la teorema dels número primo és que p_n, el n-ésimo número primo, queda ben aproximat per nln(n). En efecte, p_n és estrictament major que este valor.

Diferència entre dos cosins consecutius

Artícul principal → Diferència entre dos número primo consecutius.

Lligat a la distribució dels número primo es troba l'estudi dels intervals entre dos cosins consecutius. Este interval, en l'única salvetat del que hi ha entre el 2 i el 3, deu ser sempre igual o major que 2, ya que entre dos número primo consecutius a lo manco hi ha un número par i per tant compost. Si dos número primo tenen per diferència 2, es diu que són bessons, i en la salvetat del «triplet» format pels números 3, 5 i 7, els números bessons es presenten sempre de dos en dos. Açò també és fàcil de demostrar: entre tres número impar consecutius majors que 3 sempre hi ha un que és múltiple de 3, i per tant compost. Els primers parells d'número primo bessons són (3,5), (5,7), (11, 13), (17, 19) i (29, 31).

Per una atra part, la diferència entre cosins consecutius pot ser tan gran com es vullga. La demostració és relativament senzilla:

Siga un número natural $n$. Llavors, tots els números de la forma

$(n+1)!+i$

són número compuesto si $2\le i\le n+1$, puix $1<i<(n+1)+i$ i $\frac{(n+1)!+i}{i}=(i-1)!\cdot (i+1)(i+2)\mathrm{...}(n)(n+1)+1\in \mathbb{N}$.

Es pot construir aixina una llista en $n$ número compuesto, i ya que $n$ és un número natural arbitrari, llavors l'interval pot fer-se tan gran com es desige.

Per eixemple, si es requerix construir un interval de cinc números consecutius a on cap siga un número primo, es fa $n=5$. Estos valors corresponen a:

$6!+2=722=2\cdot 361$

$6!+3=723=3\cdot 241$

$6!+4=724=4\cdot 181$

$6!+5=725=5\cdot 145$

$6!+6=726=6\cdot 121$

El següent valor, 6!+7=727, és primer. De totes formes, el menor número primo que dista del següent en n és generalment molt menor que el factorial, per eixemple, el cas més chicotet de dos cosins consecutius separats de huit unitats és (89, 97), mentres que 8! és igual a 40.320.

La successió de les diferències entre cosins consecutius ha segut profusamente estudiada en matemàtiques, i al voltant d'este concepte s'han establit moltes conjectura que permaneixen sense resoldre.

Conclusió

Archiu:PrimeNumbersSmall.png

La distribució de tots els número primo compresos entre 1 i Plantilla:Nts, d'esquerra a dreta i de dalt avall. Cada pixel representa un número. Els píxels negres representen número primo; els blancs representen números no primers.

Archiu:Primenumbers2310inv.png

Image en 2310 columnes que conserva múltiples de 2, 3, 5, 7 i 11 en les columnes respectives. Com cal esperar, els número primo cauran en columnes concretes si els números estan ordenats d'esquerra a dreta i l'ample és un múltiple d'un número primo. No obstant, els número primo també queden distribuïts de manera ordenada en construccions espirals com l'espiral de Ulam, ya que tendixen a concentrar-se en algunes diagonals concretes i no en unes atres.

La modelació de la distribució dels número primo és un tema d'investigació recurrent entre els teòrics de números. La primalidad d'un número concret és (fins ara) impredictible a pesar de que existixen lleis, com el teorema dels número primo i el postulat de Bertrand, que governen la seua distribució a gran escala. Leonhard Euler va comentar:

En una conferència de 1975, el matemàtic germà-nortamericà Don Zagier va comentar:

Trobar número primo

Tests de primalidad

Artícul principal → Test de primalidad.

Archiu:Sieve of Eratosthenes animation.gif

La garbell de Eratóstenes va ser concebuda per Eratóstenes de Cirene, un matemàtic grec de el sigle iii a. C. És un algoritme senzill que permet trobar tots els número primo menors o iguals que un número donat.

La garbell de Eratóstenes és una manera senzilla de trobar tots els número primo menors o iguals que un número donat. Es basa en confeccionar una llista de tots els número natural des del 2 fins a eixe número i tachar repetidament els múltiples dels número primo ya descoberts. La garbell de Atkin, més moderna, té una major complexitat, pero si s'optimisa apropiadament també és més ràpida. També existix una recent garbell de Sundaram que genera únicament número compuesto, sent els cosins els números faltantes.

En la pràctica, lo que es desija és determinar si un número donat és primer sense tindre que confeccionar una llista d'número primo. Un método per a determinar la primalidad d'un número és la divisió per tentativa, que consistix en dividir successivament eixe número entre els número primo menors o iguals a la seua raïl quadrada. Si alguna de les divisions és exacta, llavors el número no és primer; en cas contrari, és primer. Per eixemple, donat n menor o igual que 120, per a determinar la seua primalidad basta comprovar si és divisible entre 2, 3, 5 i 7, ya que el següent número primo, 11, ya és major que √120. És el test de primalidad més senzill, i ràpidament pert la seua utilitat a l'hora de comprovar la primalidad de números grans, ya que el número de factors possibles creix massa ràpit a mida que creix el número potencialment primer.

En efecte, el número d'número primo menors que n és aproximadament

$\frac{n}{\ln n-1}$.

D'esta forma, per a determinar la primalidad de n, el major factor primer que es necessita no és major que Plantilla:Raïl, deixant el número de candidats a factor primer en prop de

$\frac{\sqrt{n}}{\ln \sqrt{n}-1}$.

Esta expressió creix cada volta més llentament en funció de n, pero, com els n grans són d'interés, el número de candidats també es fa gran: per eixemple, per a n = 10²⁰ es tenen 450 millons de candidats.

Aixina mateix, existixen molts atres tests de primalidad determinista que es basen en propietats que caracterisen als número primo, pero la seua utilitat computacional depén molt del test usat. Per eixemple, es podria amprar el teorema de Wilson per a calcular la primalidad d'un número, pero té l'inconvenient de requerir el càlcul d'un factorial, una operació computacionalment prohibitiva quan es manegen números grans. Ací entra en joc el temps d'eixecució de l'algoritme amprat, que s'expressa en la notació de Landau. Per a poder determinar la primalidad de números cada volta més grans (de mils de sifres) es busquen aquells algoritmes el temps dels quals d'eixecució creixca lo més llentament possible, a ser possible, que es puga expressar com un polinomi. Si ben el test de primalidad AKS complix en esta condició, per al ranc de números que s'usa en la pràctica este algoritme és extremadament llent.

Per una atra part, a sovint n'hi ha prou en tindre una resposta més ràpida en una alta provabilitat (encara que no segura) de ser certa. Es pot comprovar ràpidament la primalidad d'un número relativament gran per mig de tests de primalidad provabilístics. Estos tests solen prendre un número aleatori cridat "testic" i introduir-ho en una fòrmula junt en el número potencialment primer n. Despuix de vàries iteraciones, es resol que n és "definitivament compost" o be "provablement primer". Estos últims números poden ser primers o ben pseudoprimos (número compuesto que passen el test de primalidad). Alguns d'estos tests no són perfectes: pot haver número compuesto que el test considere "provablement primers" independentment del testic utilisat. Eixos números reben el nom de pseudoprimos absoluts per a eixe test. Per eixemple, els números de Carmichael són número compuesto, pero el test de Fermat els evalua com provablement primers. No obstant, els tests provabilístics més utilisats, com el test de Miller-Rabin o l'obsolet test de Solovay-Strassen, superat per l'anterior, no tenen este inconvenient, encara sent igualment tests provabilístics.

Alguns tests provabilístics podrien passar a ser determinísticos i alguns tests poden millorar el seu temps d'eixecució si es verifiquen algunes hipòtesis matemàtiques. Per eixemple, si es verifica la hipòtesis generalisada de Riemann, es pot amprar una versió determinística del test de Miller-Rabin, i el test de primalidad per curves elíptiques podria millorar notablement el seu temps d'eixecució si es verificaren algunes hipòtesis de teoria analítica de números.

Algoritmes d'factorización

Un algoritme d'factorización és un algoritme que separa un a un els factors primers d'un número. Els algoritmes d'factorización poden funcionar també a modo de tests de primalidad, pero en general tenen un temps d'eixecució menys ventajós. Per eixemple, es pot modificar l'algoritme de divisió per tentativa de manera que no es detinga quan s'obtinga una divisió exacta, sino que seguixca realisant noves divisions, i no sobre el número original, sino sobre el cocient obtingut. Despuix de la divisió per tentativa, els métodos més antics que es coneixen són el método de Fermat, que es basa en les diferències entre quadrats i que és especialment eficaç quan n és el producte de dos número primo pròxims entre sí, i el método de Euler, que es basa en la representació de n com sumixca de dos quadrats de dos formes distintes.

Més recentment, s'han elaborat algoritmes basats en una gran varietat de tècniques, com les fraccions contínues o les curves elíptiques, encara que alguns són millores de métodos anteriors (la garbell quadràtic, per eixemple, es basa en una millora del método de Fermat i posseïx complexitat computacional subexponencial sobre el número de sifres de n). Uns atres, com el método rho de Pollard, són provabilístics, i no garantisen trobar els divisores d'un número compuesto.

Hui per hui, l'algoritme determinístico més ràpit d'us general és la garbell general del cos de números (GNFS per les sigles del seu nom en anglés: General number field sieve), que també posseïx complexitat computacional subexponencial sobre el número de sifres de n. S'ha propost un algoritme el temps del qual d'eixecució és polinòmic sobre el número de sifres de n (l'algoritme de Shor), pero requerix ser eixecutat en un ordenador quàntic, ya que la seua simulació en un ordenador normal requerix un temps exponencial. No es coneixen algoritmes per a factorizar en una computadora tradicional en temps polinòmic i tampoc es va demostrar que açò siga impossible.

Fòrmules que solament generaren número primo

Vore també: Fòrmula dels número primo

A lo llarc de l'història, s'han buscat numeroses fòrmules per a generar els número primo. El nivell més alt d'exigència per a una fòrmula aixina seria que associara a cada número natural n el n-ésimo número primo. De forma més indulgent, es pot demanar una funció f inyectiva que associe a cada número natural n un número primo de tal forma que cada u dels valors presos aparega solament una volta.

Ademés, s'exigix que la funció es puga aplicar, efectiva i eficaçment, en la pràctica. Per eixemple, el teorema de Wilson assegura que p és un número primo si i solament si (p-1)!≡-1 (mod p). Un atre eixemple: la funció f(n) = 2 + ( 2(n!) mod (n+1)) genera tots els número primo, solament els número primo, i solament el valor 2 es pren més d'una volta. No obstant, abdós fòrmules es basen en el càlcul d'un factorial, lo que les fa computacionalment inviables.

En la busca d'estes funcions, s'han investigat, notablement, les funcions polinòmiques. cal subrallar que cap polinomi, encara en vàries variables, torna sol valors primers. Per eixemple, el polinomi en una variable f(n) = n² + n + 41, estudiada per Leonardo Euler, torna valors primers per a n = 0, …, 39, no obstant per a n= 40, resulta $40^2+40+41=41^2$ un número compuesto. Si el terme constant val zero, llavors el polinomi és múltiple de n, per lo que el polinomi és compost per a valors composts de n. En cas contrari, si c és el terme constant, llavors f(cn) és múltiple de c, per lo que si el polinomi no és constant, necessàriament deurà incloure valors composts.

No obstant, hi ha polinomis en vàries variables els valors positius de les quals (quan les variables recorren número natural) són precisament número primo. Un eixemple, és este polinomi descobert per Jones, Sato, Wada i Wiens en 1976:

$(1-(w\cdot z+h+j-q{)}^2-(2\cdot n+p+q+z-e{)}^2-(a^2\cdot y^2-y^2+1-x^2{)}^2\dots$

$-(e^3\cdot (e+2)\cdot (a+1{)}^2+1-o^2{)}^2-(16\cdot (k+1{)}^3\cdot (k+2)\cdot (n+1{)}^2+1-f^2{)}^2\dots$

$-(((a+u^2\cdot (u^2-a){)}^2-1)\cdot (n+4\cdot d\cdot y{)}^2+1-(x+c\cdot u{)}^2{)}^2-(a\cdot i+k+1-l-i{)}^2\dots$

$-((g\cdot k+2\cdot g+k+1)\cdot (h+j)+h-z{)}^2-(16\cdot r^2\cdot y^4\cdot (a^2-1)+1-u^2{)}^2\dots$

$-(p-m+l\cdot (a-n-1)+b\cdot (2\cdot a\cdot n+2\cdot a-n^2-2\cdot n-2){)}^2-(z-p\cdot m+p\cdot l\cdot a-p^{2}l+t\cdot (2\cdot a\cdot p-p^2-1){)}^2\dots$

$-(q-x+y\cdot (a-p-1)+s\cdot (2\cdot a\cdot p+2\cdot a-p^2-2\cdot p-2){)}^2-(a^2\cdot l^2-l^2+1-m^2{)}^2-(n+l+v-y{)}^2)\cdot (k+2)$

De la mateixa manera que ocorre en les fòrmules en factorials, este polinomi no és pràctic de calcular, ya que, encara que els valors positius que pren són tots primers, pràcticament no torna una atra cosa que valors negatius quan es fan variar les variables a a z de 0 a infinit.

Un atre enfocament al problema de trobar una funció que solament genere número primo ve dau a partir del teorema de Mills, que indica que existix una constant θ tal que

$\lfloor {\theta }^{3^n}\rfloor$

és sempre un número primo, a on $\lfloor \rfloor$ és la funció chafe. Encara no es coneix cap fòrmula per a calcular la constant de Mills, i les aproximacions que s'ampren en l'actualitat es basa en la successió dels aixina cridats número primo de Mills (els número primo generats per mig d'esta fòrmula), que no poden ser obtinguts rigorosament, sino solament de manera provabilística, suponent certa la hipòtesis de Riemann.

Classes d'número primo

De major interés són atres fòrmules que, encara que no solament generen número primo, són més ràpides d'implementar, sobretot si existix un algoritme especialisat que permeta calcular ràpidament la primalidad dels valors que van prenent. A partir d'estes fòrmules s'obtenen subconjunts relativament menuts del conjunt dels número primo, que solen rebre un nom colectiu.

Primers primoriales i cosins factorials

Vore també: Número primo primorial i número primo factorial

Els número primo primoriales, directament relacionats en la demostració euclidiana de la infinitud dels número primo, són els de la forma p = n# ± 1 per a algun número natural n, a on n# és igual al producte 2 · 3 · 5 · 7 · 11 · … de tots els cosins ≤ n. Aixina mateix, un número primo es diu cosí factorial si és de la forma n! ± 1. Els primers cosins factorials són:

n! − 1 és primer per a n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, …

n! + 1 és primer per a n = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, …

Número primo de Fermat

Vore també: Número de Fermat

Archiu:Pentagon construct.gif

Construcció d'un pentàgon regular. 5 és un número primo de Fermat.

Els números de Fermat, lligats a la construcció de polígons regulars en regla i compàs, són els números de la forma $F_n=2^{2^n}+1$, en n natural. Els únics número primo de Fermat que es coneixen fins a la data són els cinc que ya coneixia el propi Fermat, corresponents a n = 0, 1, 2, 3 i 4, mentres que per a valors de n entre 5 i 32 estos números són composts.

Per a determinar el seu primalidad, existix un test especialisat que el seu temps d'eixecució és polinòmic: el test de Pépin. No obstant, els propis números de Fermat creixen tan ràpidament que solament li l'ha pogut aplicar per a valors de n menuts. En 1999 li'l va aplicar per a n = 24. Per a determinar el caràcter d'atres números de Fermat majors s'utilisa el método de divisions successives i d'eixa manera a data de juny de 2009 es coneixen 241 números de Fermat composts, encara que en la majoria dels casos es desconega la seua factorización completa.

Número primo de Mersenne

Vore també: Número primo de Mersenne

Els números de Mersenne són els de forma M_p = 2^p – 1, a on p és primer. Els majors número primo coneguts són generalment d'esta forma, ya que existix un test de primalidad molt eficaç, el test de Lucas-Lehmer, per a determinar si un número de Mersenne és primer o no.

Actualment, el major número primo que es coneix és M_136.279.841 = 2^136.279.841 - 1, que té 41 024 320 sifres en el sistema decimal. Es tracta cronològicament de el ORD número primo de Mersenne conegut i el seu descobriment es va anunciar el 21 d'octubre de 2024 gràcies al proyecte de computació distribuïda «Great Internet Mersenne Prime Search» (GIMPS).

Atres classes d'número primo

Existixen lliteralment decenes de llinages que es poden afegir al concepte de número primo per a referir-se a un subconjunt que complix alguna propietat concreta. Per eixemple, els número primo pitagórico són els que es poden expressar en la forma 4n+1. Dit d'una atra forma, es tracta dels número primo el restant dels quals en dividir-los entre 4 és 1. Un atre eixemple és el dels número primo de Wieferich, que són aquells número primo p tals que p² dividix a 2^p-1 - 1.

Algunes d'estes propietats es referixen a una relació concreta en un atre número primo:

• Número primo bessons: p i p+2 lo són si són els dos cosins.
• Número primo de Sophie Germain: donat p primer, és de Sophie Germain si 2p + 1 també és primer. Una successió de números p₁,p₂,p₃,··· ,p_n tots ells primers, tals que p_i+1=2p_i+1 per a tot i ∈ {1,2,···,n-1 }, es denomina cadena (completa) de Cunningham de primera espècie, i complix per definició que cada u dels térmens, llevat l'últim, és un número primo de Sophie Germain. Es creu que para tot n natural existixen infinites cadenes de Cunningham de llongitut n, encara que fins a la data ningú ha proporcionat prova de que dita afirmació siga certa.
• Número primo de Wagstaff: p ho és si $p=\frac{2^q+1}{3}$, a on q és un atre número primo.

També se'ls dona noms especials a algunes classes de cosins que depenen de la base de numeració amprada o de la forma d'escriure els dígits, i no d'una fòrmula matemàtica. És el cas dels números somirp (cosins al revés), que són aquells número primo tals que el número obtingut en invertir l'orde de les seues sifres també és primer. També és el cas dels número primo repunit, que són aquells número primo que són concatenació d'uns. Si, en lloc de considerar-se el sistema de numeració decimal es considera el binario, s'obté un atre conjunt distint d'número primo repunit que, ademés, coincidix en el dels número primo de Mersenne. Finalment, els número primo triádicos són aquells números que són primers, capicúas i simètrics respecte d'una recta horisontal.

El que se li done un nom a una classe d'número primo en una definició precisa no significa que es conega algun número primo que siga d'eixa classe. Per eixemple, no es coneix fins al moment cap número primo de Wall-Sun-Sun, pero la seua rellevància radica que en 1992, abans de la demostració de Wiles del última teorema de Fermat, es va descobrir que la falsetat de la teorema per a un número primo p donat implicava que p era un número primo de Wall-Sun-Sun. Açò va fer que, durant un temps, la busca d'número primo d'esta classe fora també la busca d'un contraeixemple de l'última teorema de Fermat.

Quadre resum

Classes d'número primo

Per fòrmula    • Fermat (22n + 1) • Mersenne (2p − 1) • Mersenne doble (22p-1 - 1) • Wagstaff (2p + 1)/3 • Proth (k·2n + 1) • Factorial (n! ± 1) • Primorial (pn# ± 1) • Euclides (pn# + 1) • Pitagórico (4n + 1) • Pierpont (2m·3n + 1) • Cuártico (x4 + i4) • Solinas (2m ± 2n ± 1) • Cullen (n·2n + 1) • Woodall (n·2n - 1) • Cúbic (x3 - i3)/(x - i) • Leyland (xi + ix) • Thabit (3·2n - 1) • Williams ((b-1)·bn - 1) • Mills (⌊A3n⌋)

En séries de sancers    • Fibonacci • Lucas • Pell • Newman-Shanks-Williams • Perrin • Particions • Bell • Motzkin

Per les seues propietats    • Wieferich (parell) • Wall-Sun-Sun • Wolstenholme • Wilson • De la sòrt • Afortunat • Ramanujan • Pillai • Regular • Fort • Stern • Supersingular (curva elíptica) • Supersingular (teoria moonshine) • Bo • Superprimo • Higgs • Altament cototiente

Base-depenent    • Palindrómico • Omirp • Repunit (10n - 1)/9 • Permutable • Circular • Truncable • Mínim • Delicat • Primitiu • Llarc • Únic • Feliç • Autonúmero • Smarandache-Wellin • Estrobogramático • Diédrico • Tetrádico

Per patrons d'aparició    • Bessons (p, p + 2) • Cadena bigemela (n - 1, n + 1, 2n - 1, 2n + 1, …) • Triplet (p, p + 2 or p + 4, p + 6) • Cuadruplete (p, p + 2, p + 6, p + 8) • k-tupla • Cosí primer (p, p + 4) • Sexy (p, p + 6) • Chen • Sophie Germain/segur (p, 2p + 1) • Cunningham (p, 2p ± 1, 4p ± 3, 8p ± 7, ...) • Progressió aritmètica (p + a·n, n = 0, 1, 2, 3, ...) • Equilibrat (p - n, p, p + n consecutius)

Per tamany    • Megaprimo (1.000.000+ dígits) • Major conegut

Número complejo    • Eisenstein • Gaussiano

Número compuesto    • Números pseudoprimos (• Català) • Elíptic • Euler • Euler-Jacobi • Fermat • Frobenius • Lucas • Somer-Lucas • (Fort) • Carmichael • Casi primer • Semiprimo • Interprimo • Perniciós

Atres tipos    • Provable primer • Número primo de grau industrial • Número illegal • Fòrmula dels número primo • Diferència entre dos número primo consecutius

Conjectura

Existixen numeroses preguntes obertes sobre els número primo. Moltes d'elles són problemes ben antics, i una de les més significatives és l'hipòtesis de Riemann, vàries voltes mencionada en este artícul com una conjectura que, de ser certa, permetria conéixer numerosos resultats rellevants en diversos camps de les matemàtiques.

Hipòtesis de Riemann

Vore també: Hipòtesis de Riemann

Per a entendre l'hipòtesis de Riemann, una conjectura enunciada en 1859 pero que, fins a la data (2026), seguix sense resoldre's, és necessari entendre la funció zeta de Riemann. Siga $s$ un número complejo en part real major que 1. Llavors,

La segona igualtat és una conseqüència del teorema fonamental de l'aritmètica, i mostra que la funció zeta està íntimament relacionada en els número primo.

Existixen dos tipos de zeros de la funció zeta, és dir, valores s per als quals ζ(s) = 0: els trivials, que són s=-2, s=-4, s=-6, etc., (els sancers parells negatius) i els no trivials, que són aquells zeros que no es troben en l'eix real. Lo que indica l'hipòtesis de Riemann és que la part real de tots els zeros no trivials és igual a 1/2.

La veracitat de l'hipòtesis implica una profunda conexió en els número primo, en essència, en el cas de verificar-se, diu que els número primo estan distribuïts de la forma més regular possible. Des d'un punt de vista «físic», diu grosso modo que les irregularitats en la distribució dels número primo solament procedixen de soroll aleatori. Des d'un punt de vista matemàtic, diu que la distribució asintòtica dels número primo (segons el teorema dels número primo, la proporció de cosins menors que n és $\frac{1}{\ln (n)}$) també és certa per a intervals molt menors, en un error d'aproximadament la raïl quadrada de n (per a intervals pròxims a n). Està àmpliament estés en la comunitat matemàtica que l'hipòtesis siga certa. En concret, la presunció més simple és que els número primo no deurien tindre irregularitats significatives en la seua distribució sense una bona raó.

Atres conjectura

Infinitud de certs tipos d'número primo

Moltes conjectura tracten sobre si hi ha infinits número primo d'una determinada forma. Aixina, es conjectura que hi ha infinits número primo de Fibonacci i infinits primers de Mersenne, pero solament un número finito de primers de Fermat. No se sap si hi ha infinits número primo de Euclides.

Distribució dels número primo

També hi ha numeroses conjectura que s'ocupen de determinades propietats de la distribució dels número primo. Aixina, la conjectura dels número primo bessons enuncia que hi ha infinits número primo bessons, que són parells de primers la diferència dels quals és de 2. La conjectura de Polignac és una versió més general i més forta de l'anterior, ya que enuncia que, per a cada sancer positiu n, hi ha infinits parells de cosins consecutius que diferixen en 2n. A la seua volta, una versió més dèbil de la conjectura de Polignac diu que tot número par és la diferència de dos número primo.

Aixina mateix, es conjectura l'infinitat dels cosins de la forma n² + 1. Segons la conjectura de Brocard, entre els quadrats de cosins consecutius majors que 2 existixen sempre a lo manco quatre número primo. La conjectura de Legendre establix que, per a cada n natural, existix un número primo entre n² i (n+1)². Finalment, la conjectura de Cramér, la veracitat de la qual implicaria la de Legendre, diu que:

Teoria aditiva de números

Atres conjectura relacionen algunes propietats aditivas dels números en els número primo. Aixina, la conjectura de Goldbach diu que tot número par major que 2 es pot escriure com sumixca de dos número primo, encara que també existix una versió més dèbil de la mateixa conjectura segons la qual tot número impar major que 5 es pot escriure com sumixca de tres número primo. El matemàtic chinenc Chen Jingrun va demostrar, en 1966, que en efecte, tot número par suficientment gran pot expressar-se com sumixca de dos cosins o com la suma d'un primer i d'un número que és el producte de dos cosins. ("semi-primer").

Els quatre problemes de Landau

En 1912, Landau va establir en el Quint Congrés Internacional de Matemàtics de Cambridge una llista de quatre dels problemes ya mencionats sobre número primo, que es coneixen com els problemes de Landau. Cap d'ells està resolt fins a la data. Es tracta de la conjectura de Goldbach, la dels número primo bessons, la de Legendre i la dels cosins de la forma n² + 1.

Generalisació del concepte d'número primo

El concepte d'número primo és tan important que s'ha vist generalisat de vàries maneres en diverses branques de les matemàtiques.

Elements primers en un anell

Archiu:Gaussian primes.svg

Representació dels primers gaussianos de norma menor o igual a 500. Els cosins gaussianos són, per definició, els sancers gaussianos que són primers.

Es poden definir els elements primers i els elements irreducibles en qualsevol domini d'integritat. En qualsevol domini d'factorización única, com per eixemple, l'anell $\mathbb{Z}$ dels sancers, el conjunt d'elements primers equival al conjunt dels elements irreducibles, que en $\mathbb{Z}$ és {…, −11, −7, −5, −3, −2, 2, 3, 5, 7, 11, …}.

Consideren-se per eixemple els sancers gaussianos $\mathbb{Z}[i]$, és dir, els número complejo de la forma a+bi en a, b ∈ $\mathbb{Z}$. Est és un domini d'integritat, i els seus elements primers són els primers gaussianos. cal destacar que el 2 no és un primer gaussiano, perque admet factorización com a producte dels cosins gaussianos (1+i) i (1-i). No obstant, l'element 3 sí és primer en els sancers gaussianos, pero no ho és en un atre domini sancer. En general, els cosins racionals (és dir, els elements primers de l'anell $\mathbb{Z}$) de la forma 4k+3 són primers gaussianos, pero no ho són aquells de la forma 4k+1.

Ideals cosins

En teoria d'anells, un ideal I és un subconjunt d'un anell A tal que

• si i, j ∈ I, llavors la suma i + j pertany a I
• i si x ∈ A, i ∈ I, llavors els productes a × i, i × a pertanyen a I.

Un ideal primer es definix llavors com un ideal que complix també que:

• per a qualsevol parell d'elements a, b de l'anell A tals que el seu producte a × b pertany a I, llavors, a lo manco un dels dos elements, a o b, està en I.
• I no és l'anell A sancer.

Els ideals cosins són una ferramenta rellevant en àlgebra conmutativa, teoria algebraica de números i geometria algebraica. Els ideals cosins de l'anell de sancers són els ideals (0), (2), (3), (5), (7), (11), …

Un problema central en teoria algebraica de números és la manera en que es factorizan els ideals cosins quan es veuen somesos una extensió de cossos. En l'eixemple dels sancers gaussianos, (2) es ramifica en potència d'un primer (ya que $1+i$ i $1-i$ generen el mateix ideal primer), els ideals cosins de la forma $4k+3$ són inertes (mantenen la seua primalidad) i els de la forma $4k+1$ passen a ser producte de dos ideals cosins distints.

Cosins en teoria de la valoració

En teoria algebraica de números sorgix una atra generalisació més. Donat un cos $𝕂$, reben el nom de valoracions sobre $𝕂$ determinades funcions de $𝕂$ en $ℝ$. Cada una d'estes valoracions genera una topología sobre $𝕂$, i es diu que dos valoracions són equivalents si generen la mateixa topología. Un cosí de $𝕂$ és una classe d'equivalència de valoracions. En esta definició, els cosins del cos $\mathbb{Q}$ dels número racional queden representats per la funció valor absolut aixina com per les valoracions p-ádicas sobre $\mathbb{Q}$ per a cada número primo p.

Nucs primers

Trefoil	Figure-8 knot	Cinquefoil	Archiu:PrimeKnot-5-2.png
Alguns nucs primers.

En teoria de nucs, un nuc primer és un nuc no trivial que no es pot descompondre en dos nucs més menuts. De forma més precisa, es tracta d'un nuc que no es pot escriure com suma conexa de dos nucs no trivials.

En 1949 Horst Schubert va demostrar una teorema d'factorización anàlec a la teorema fonamental de l'aritmètica, que assegura que cada nuc es pot obtindre de forma única com a suma conexa de nucs primers. Per este motiu, els nucs primers eixerciten un paper central en la teoria de nucs: una classificació dels nucs ha segut des de finals del sigle xix el tema central de la teoria.

Aplicacions en la matemàtica

• En l'estudi dels número complejo, s'acodix al concepte de "cosins relatius" per a definir raïls primitives de l'unitat . Si n és un número primo totes les raïls enèsimes d'1 són raïls primitives, llevat la raïl 1.

• En la definició d'un cos finito, s'exigix que el número d'elements d'un anell siga sancer primer. En tal cas, eliminant el zero, cada element té invers multiplicativo i s'obté l'estructura d'un cos.

• En la definició d'un polígon estrelat de n costats, per a prendre els punts de m en m, s'exigix que m siga menor que n/2 i primer en n.

• En definir el representant canònic d'un número racional, usant classes d'equivalència de parells ordenats d'número entero, necessàriament, el parell ordenat definente té que involucrar dos sancers cosins relatius. A fortiori, per lo manco un d'ells, un cosí absolut.

Aplicacions en la computació

Artícul principal → Algoritme RSA.

l'algoritme RSA es basa en l'obtenció de la clau pública per mig de la multiplicació de dos números grans (majors que 10¹⁰⁰) que siguen primers. La seguritat d'este algoritme radica que no es coneixen maneres ràpides de factorizar un número gran en els seus factors primers utilisant computadores tradicionals.

Número primo en l'art i la lliteratura

• Els número primo han influït en numerosos artistes i escritors. El compositor francés Olivier Messiaen es va valdre d'ells per a crear música no mètrica. En obres tals com La Nativité du Seigneur (1935) o Quatre Études de rythme (1949-50) ampra simultàneament motius la duració dels quals és un número primo per a crear ritmes impredictibles. Segons Messiaen, esta forma de compondre va ser «inspirada pels moviments de la naturalea, moviments de duració lliures i desiguals».

• En la novela escrita en 1968 2001: Una Odissea Espacial, Arthur C. Clarke menciona que el monolit d'orige extraterrestre té la proporció del quadrat dels primers tres número primo: 1,4,9.

• En la seua novela de ciència ficció Contact, posteriorment adaptada al cine, Carl Sagan sugerix que els número primo podrien ser amprats per a comunicar-se en inteligències extraterrestres, una idea que havia desenrollat de manera informal en l'astrònom nortamericà Frank Drake en 1975.

• El curiós incident del gos a mijanit, de Mark Haddon, que descriu en primera persona la vida d'un jove autiste molt dotat en matemàtiques i càlcul mental, utilisa únicament els número primo per a numerar els capítuls.

• En la novela PopCo de Scarlett Thomas, la yaya d'Alice Butler treballa en la demostració de la hipòtesis de Riemann. El llibre ilustra una taula dels mil primers número primo.

• La soletat dels número primo, novela escrita per Paolo Giordano, va guanyar el premi Strega en 2008.

• També són moltes les películes que reflectixen la fascinació popular cap als misteris dels número primo i la criptografia, per eixemple, Cube, Sneakers, L'amor té dos cares i Una ment maravellosa. Esta última es basa en la biografia del matemàtic i premi Nobel John Forbes Nash, escrita per Sylvia Nasar.

• L'escritor grec Apostolos Doxiadis, va escriure El tio Petros i la conjectura de Goldbach, que narra cóm un fictici matemàtic prodigi de principis del sigle xx se sumergix en el món de les matemàtiques d'una forma apassionant, tractant de resoldre un dels problemes més difícils i encara no resolts de la matemàtica, la conjectura de Goldbach, la qual resa: «Tot número par pot expressar-se com la suma de dos número primo».

Vore també

• [[Archiu:{{#switch:Matemàtica|20px|Vore el portal sobre Matemàtica]] Portal:Matemàtica. Contingut relacionat en Matemàtica.

Enllaços externs

• Calculador en llínea de factors primers, per www.mathstools.com
• The Prime Pages [3] archivat en Wayback Machine.
• Sobre l'artícul de Manindra Agrawal et al. PRIMES IS IN P, en a on afirmen: "We present a deterministic polynomial-clave algorithm that determines whether an input number n is prime or composite" mathmistakes
• Algoritmes eficients per a calcular número primo, per Steve Litt
• ¿És este número primo?