La propiedá de ser primu denominarprimalidá.Dacuando fálase denúmberu primu impar pa referise a cualquier númberu primu mayor que 2, yá que este ye l'únicu númberu primu par.Dacuando se denota elconxuntu de tolos númberos primos por.Na teoría alxebraica de númberos, a los númberos primos conózse-yos como númberosracionales primos pa estremalos de los númberos gaussianos primos.[3]
La distribución de los númberos primos ye una tema recurrente d'investigación na teoría de númberos: si considérense númberos individuales, los primos paecen tar distribuyíos aleatoriamente, pero la distribución global» de los númberos primos sigue lleis bien definíes.
Les mozquetes presentes nelgüesu d'Ishango, que data de hai más de 20.000 años (anterior por tanto a l'apaición de laescritura) y que foi topáu pol arqueóloguJean de Heinzelin de Braucourt,[5] paecen aisllar cuatro números primos: 11, 13, 17 y 19. Dellos arqueólogos interpreten esti fechu como la prueba de la conocencia de los númberos primos. Con tou, esisten bien pocos afayos que dexen discernir les conocencies que tenía realmente l'home d'aquella dómina.[6]
Numberoses tablillas de magre secu atribuyíes a lescivilizaciones que se fueron asocediendo enMesopotamia a lo llargo del II mileniu e.C. amuesen la resolución de problemes aritméticos y atestigüen les conocencies de la dómina. Los cálculos riquíen conocer losinversos de los naturales, que tamién se toparon en tablillas.[7]Nelsistema sexaxesimal qu'emplegaben losbabilonios pa escribir los númberos, los inversos de los divisores de potencies de 60 (númberos regulares) calcúlense fácilmente; por casu, estremar ente 24 equival a multiplicar por 150 (2·60+30) y correr la coma sexaxesimal dos llugares. La conocencia matemática de los babilonios precisaba una sólida comprensión de la multiplicación, la división y lafactorización de los naturales.
Nesmatemátiques exipcies, el cálculu defracciones riquía conocencies sobre les operaciones, la división de naturales y la factorización. Los exipcios namái operaben coles llamaesfracciones exipcies, suma defracciones unitaries, esto ye, aquelles que'l so numberador ye 1, como, polo que les fracciones de numberador distintu de 1 escribíense como suma d'inversos de naturales, a ser posible ensin repetición en llugar de.[8] Ye por ello que, en cierta manera, teníen que conocer o albidrar los númberos primos.[9]
Lapeñerada de Eratóstenes, atribuyida aEratóstenes de Cirene, ye un métodu senciellu que dexa atopar númberos primos. Anguaño, sicasí, los mayores númberos primos que s'atopen cola ayuda d'ordenadores empleguen otros algoritmos más rápidos y complexos.
Dempués de les matemátiques griegues, hubo poques meyores nel estudiu de los númberos primos hasta'l sieglu XVII. En1640Pierre de Fermat estableció (anque ensin demostración) elpequeñu teorema de Fermat, darréu demostráu porLeibniz yEuler. Ye posible que muncho primero se conociera un casu especial de dichu teorema en China.
Fermat conxeturó que tolos númberos de la forma 22n+1 yeren primos (por cuenta de lo cual conocer comonúmberos de Fermat) y verificó esta propiedá hastan = 4 (esto ye, 216+1). Sicasí, el númberu de Fermat 232+1 ye compuestu (unu de los sos factores primos ye 641), como demostró Euler. Ello ye que hasta los nuesos díes nun se conoz nengún númberu de Fermat que sía primu amás de los que yá conocía'l mesmu Fermat.
El monxu francésMarin Mersenne investigó los númberos primos de la forma 2p−1, conp primu. Nel so honor, conocer comonúmberos de Mersenne.
Nel trabayu de Euler en teoría de númberos atopen munchos resultancies que concernen a los númberos primos. Demostró ladiverxencia de laserie, y en 1747 demostró que tolosnúmberos perfectos pares son de la forma 2p-1(2p - 1), onde'l segundu factor ye un númberu primu de Mersenne. Créese que nun esisten númberos perfectos impares, pero inda ye una cuestión abierta.
A empiezos del sieglu XIX, Legendre y Gauss conxeturaron de forma independiente que, cuandon tiende a infinitu, el númberu de primos menores o iguales quen ye asintótico a, onde ln(n) ye'lllogaritmu natural den. Les idees queBernhard Riemann afiguró nun trabayu de 1859 sobre lafunción zeta describieron el camín que conduciría a la demostración delteorema de los númberos primos.Hadamard yDe la Vallée-Poussin, cada unu por separáu, dieron forma a esti esquema y consiguieron demostrar el teorema en 1896.
Anguaño nun se comprueba la primalidá d'un númberu pordivisiones socesives, siquier non si'l númberu ye relativamente grande.
Mientres el sieglu XIX desenvolviéronse algoritmos pa saber si un númberu ye primu o non factorizando dafechu'l númberu siguiente (p+1) o l'anterior (p-1). Dientro del primer casu atópase'ltest de Lucas-Lehmer, desenvueltu a partir de 1856. Dientro del segundu casu atópase'ltest de Pépin pa los númberos de Fermat (1877). El casu xeneral de test de primalidá cuando'l númberu darréu anterior atópase dafechu factorizado denominartest de Lucas.
Darréu atopáronse algoritmos de primalidá con solo llograr una factorización parcial de p+1 o p-1. Exemplos d'estos algoritmos son eltest de Proth (desenvueltu alredor de 1878) y eltest de Pocklington (1914). Nestos algoritmos ríquese que'l productu de los factores primos conocíos de p-1 sía mayor que'l raigañu cuadráu dep. Más apocayá, en 1975, Brillhart, Lehmer y Selfridge desenvolvieron eltest BLS de primalidá que solo rique que dichu productu sía mayor que'l raigañu cúbicu dep. El meyor métodu conocíu d'esta clase ye'ltest de Konyagin y Pomerance del añu 1997, que rique que dichu productu sía mayor quep3/10.[10][11]
A partir de la década de 1970 dellos investigadores afayaron algoritmos pa determinar si cualquier númberu ye primu o non con complexidá subexponencial, lo que dexa realizar tests en númberos de miles de díxitos, anque son muncho más lentos que los métodos anteriores. Exemplos d'estos algoritmos son eltest APRT-CL (desenvueltu en 1979 por Adleman, Pomerance y Rumely, con meyores introducíes por Cohen y Lenstra en 1984), onde s'usen los factores de pm-1, onde l'esponente m depende del tamañu del númberu que la so primalidá deseyar verificar, eltest de primalidá por curves elíptiques (desenvueltu en 1986 por S. Goldwasser, J. Kilian y ameyoráu por A. O. L. Atkin), qu'apurre un certificáu consistente nuna serie de númberos que dexa dempués confirmar rápido si'l númberu ye primu o non. El desenvolvimientu más recién ye'ltest de primalidá AKS (2002), que magar la so complexidá ye polinómica, pa los númberos que puede remanar la teunoloxía actual ye'l más lentu de los trés.
Mientres enforma tiempu, pensábase que l'aplicación de los númberos primos yera bien llindada fora de lamatemática pura.[12][13] Esto camudó nosaños 1970 col desenvolvimientu de lacriptografía de clave pública, na que los númberos primos formaben la base de los primeros algoritmos, tales como l'algoritmuRSA.
Dende 1951, el mayor númberu primu conocíu siempres foi afayáu cola ayuda d'ordenadores. La busca de númberos primos cada vez mayores amenó interés inclusive fora de la comunidá matemática. Nos últimos años ganaron popularidá proyeutos decomputación distribuyida tales como'lGIMPS, mientres los matemáticos siguen investigando les propiedaes de los númberos primos.
La cuestión alrodiu de si'l númberu 1 debe o nun considerase primu ta basada na convención. Dambes postures tienen les sos ventayes y los sos inconvenientes. Ello ye que hasta'l sieglu XIX, los matemáticos n'el so mayoría considerar primu. Munchos trabayos matemáticos siguen siendo válidos a pesar de considerar el 1 como un númberu primu, como, por casu, el deStern y Zeisel. La llista deDerrick Norman Lehmer de númberos primos hasta'l 10.006.721, reimpresa hasta l'añu 1956[14] empezaba col 1 como primer númberu primu.[15]
Anguaño, la comunidá matemática inclinar por nun considerar al 1 na llista de los númberos primos. Esta convención, por casu, dexa una formulación bien económica delteorema fundamental de l'aritmética: «tou númberu natural tien una representaciónúnica como productu de factores primos, salvo l'orde».[16][17] Amás, los númberos primos tienen numberoses propiedaes de les qu'escarez el 1, tales como la rellación del númberu col valor correspondiente de lafunción φ de Euler o lafunción divisor.[18] Cabo tamién la igualdá pa tou enteru positivu,, lo que dexaría dicir que tien factores.[19]
Esta ilustración amuesa que'l 11 ye un númberu primu, pero'l 12 nun lo ye.
Elteorema fundamental de l'aritmética establez que tou númberu natural tien una representación única como productu de factores primos, salvo l'orde. Un mesmu factor primu puede apaecer delles vegaes. El 1 represéntase entós como unproductu vacíu.
Puede considerase que los númberos primos son los lladriyos» colos que se constrúi cualquier númberu natural. Por casu, puede escribise el númberu 23.244 como productu de 2²·3·13·149, y cualesquier otra factorización del 23.244 como productu de númberos primos va ser idéntica sacante pol orde de los factores.
La importancia d'esti teorema ye una de les razones pa escluyir el 1 del conxuntu de los númberos primos. Si almitiera'l 1 como númberu primu, l'enunciáu del teorema riquiría aclaraciones adicionales.
A partir d'esta unicidá na factorización en factores primos desenvuélvense otros conceutos bien utilizaos en matemátiques, tales como'lmínimu común múltiplu, elmáximu común divisor y lacoprimalidá de dos o más númberos. Asina, *Elmínimu común múltiplu de dos o más númberos ye'l menor de los múltiplos comunes de toos ellos. Pa calculalo, descompónense los númberos en factores primos y tómense los factores comunes y non comunes col so máximu esponente. Por casu, el mínimu común múltiplu de 10=2·5 y 12=2²·3 ye 60=2²·3·5.
Elmáximu común divisor de dos o más númberos ye'l mayor de los divisores comunes de toos ellos. Ye igual al productu de los factores comunes col so mínimu esponente. Nel exemplu anterior, el máximu común divisor de 10 y 12 ye 2.
Finalmente, dos o más númberos soncoprimos, o primos ente sigo, si nun tienen nengún factor primu común; esto ye, si'l so máximu común divisor ye 1. Un númberu primu ye, asina, coprimo con cualquier númberu natural que nun sía múltiplu d'él mesmu.
Na so escritura nelsistema de numberación decimal, tolos númberos primos, salvo'l 2 y el 5, tien como'l guarismu de les unidaes unu d'estos: 1, 3, 7 o 9. Polo xeneral, en cualquier sistema de numberación, tolos númberos primos salvu un númberu finito acaben nuna cifra que yecoprima cola base.
De lo anterior deduzse que tolos númberos primos salvu'l 2 son de la forma4n + 1 o bien 4n + 3. Igualmente, tolos númberos primos salvu'l 2 y el 3 son de la forma 6n + 1 o 6n - 1.
Pequeñu teorema de Fermat: Sip ye primu ya ye dalgún númberu natural distintu de 1, entósap -a ye divisible porp.
Sip ye primu distintu de 2 y 5, siempres ye unnúmberu periódicu na so representación decimal, de periodup−1 o un divisor dep−1. Esto puédese deducir direutamente a partir del pequeñu teorema de Fermat. espresáu en baseq (en llugar d'en base 10) tien propiedaes similares, siempres quep nun sía un factor primu deq.
Teorema de Wilson: Un númberu naturaln > 1 ye primusi y solu si elfactorial (n - 1)! + 1 ye divisible porn. Coles mesmes, un númberu naturaln > 4 ye compuestu si y solu si (n - 1)! ye divisible porn.
Lacarauterística de too cuerpu ye, o bien cero, o bien un númberu primu.
Primer teorema de Sylow: SiG ye ungrupu finito,p primu ypn ye la mayor potencia dep qu'estrema'lorde deG. Entós, esiste un subgrupu deG d'ordepn.
Teorema de Cauchy: SiG ye un grupu finito yp ye un númberu primu qu'estrema al orde deG, entósG contién un elementu d'ordep.
El valor de lafunción zeta de Riemann en cada puntu delplanu complexu dase como una continuación meromorfa d'una función definida por un productu sobre'l conxuntu de tolos primos pa Re(s) > 1:
Na rexón onde ye converxente, esti productu indexado polos númberos primos puede calculase, llográndose diversos valores, dalgunos d'ellos importantes en teoría de númberos. Los dos primeros son:
Polo xeneral ye un númberu racional cuandon ye un númberu enteru positivu par.
L'aniellu ye uncuerpu si y solu sip ye primu. Equivalentemente:p ye primu si y solu siφ(p) =p − 1.
Sip > 1, elpolinomiuxp-1+xp-2+ ··· + 1 yeirreducible sobre si y solu sip ye primu.
Un númberu naturaln ye primu si y solu si'ln-ésimopolinomiu de Chebyshov de la primer especie Tn(x), estremáu entex, ye irreducible en. Amás, Tn(x) ≡ xn si y solu sin ye primu.
Non tou númberu primu ye un númberu gaussiano primu; tal el casu de 2, que como enteru gaussiano almite la descomposición don de la norma de ye 2, polo tanto nun ye unidá en Z[i].
Los númberos primos de la forma son igual a la suma de dos cuadraos perfectos; polo que nun son númberos gaussianos primos. En cuantes que los númberos primos de la forma sí son númberos gaussianos primos.
Tou númberu racional primu ye un númberu gaussiano enteru, ensin ser necesariamente númberu gaussiano primu.[20]
Dellos exemplos de funciones multiplicatives son lafunción φ de Euler, qu'a cadan acomuña'l númberu d'enteros positivos menores y coprimos conn, y les funcionesτ yσ, qu'a cadan acomuñen respeutivamente el númberu de divisores den y la suma de toos ellos. El valor d'estes funciones nespotencies de númberos primos ye:,
,:..
Gracies a la propiedá que les define, les funciones aritmétiques pueden calculase fácilmente a partir del valor que tomen nes potencies de númberos primos. Ello ye que dau un númberu naturaln de factorización
tiense que:
colo que se recondució'l problema de calcularf(n) al de calcularf sobre les potencies de los númberos primos qu'estremenn, valores que son xeneralmente más fáciles de llograr por aciu una fórmula xeneral. Por casu, pa conocer el valor de la función φ sobren=450=2·3²·5² basta con calcular
.
Carauterístiques del conxuntu de los númberos primos
Esisten infinitos númberos primos. Euclides realizó la primerademostración alredor del añu300e.C. nel llibru IX de la so obraElementos[21] Una adautación común d'esta demostración orixinal sigue asina: Tómase un conxuntu arbitrariu pero finito de númberos primosp1,p2,p3, ···,pn, y considérase el productu de toos ellos más unu,. Esti númberu ye obviamente mayor que 1 y distintu de tolos primospi de la llista. El númberuq puede ser primu o compuestu. Si ye primu vamos tener un númberu primu que nun ta nel conxuntu orixinal. Si, otra manera, ye compuestu, entós va esistir dalgún factorp qu'estreme aq. Suponiendo quep ye dalgunu de lospi, deduzse entós quep estrema a la diferencia, pero nengún númberu primu estrema a 1, esto ye, llegóse a un absurdu por suponer quep ta nel conxuntu orixinal. La consecuencia ye que'l conxuntu que s'escoyó nun ye refechu, yá que esisten númberos primos que nun pertenecen a él, y esto ye independiente del conxuntu finito que se tome.
Poro, el conxuntu de los númberos primos ye infinitu.
Si tómase como conxuntu'l de losn primeros númberos primos, entós, ondepn# ye lo que se llamaprimorial depn. Un númberu primu de la formapn# +1 denominarnúmberu primu d'Euclides n'honor al matemáticu griegu. Tamién puede ellaborase una demostración similar a la d'Euclides tomando'l productu d'un númberu dau de númberos primosmenos unu, el llugar del productu d'esos númberos primosmás unu. Nesi sentíu, denominarnúmberu primu primorial a un númberu primu de la formapn# ± 1.
Non tolos númberos de la formapn# +1 son primos. Nesti casu, como se sigue de la demostración anterior, tolos factores primos tendrán de ser mayores quen. Por casu: 2·3·5·7·11·13+1=30031=59·509
Otros matemáticos demostraron lainfinitud de los númberos primos con diversos métodos procedentes d'árees de les matemátiques tales como alálxebra conmutativa y latopoloxía.[22]Dalgunes d'estes demostraciones basar nel usu desocesiones infinites cola propiedá de que cada unu de los sos términos ye coprimo con tolos demás, polo que se crea unabiyección ente los términos de la socesión y un subconxuntu (infinitu) del conxuntu de los primos.
Una socesión que cumple dicha propiedá ye lasocesión d'Euclides-Mullin, que deriva de la demostración euclídea de la infinitud de los númberos primos, yá que cada unu de los sos términos defínese como'l factor primu más pequeñu d'unu más el productu de tolos términos anteriores. Lasocesión de Sylvester definir de forma similar, yá que cada unu de los sos términos ye igual a unu más el productu de tolos anteriores. Anque los términos d'esta última socesión nun son necesariamente toos primos, cada unu d'ellos ye coprimo con tolos demás, polo que puede escoyese cualesquier de los sos factores primos, por casu, el menor d'ellos, y el conxuntu resultante va ser un conxuntu infinitu que los sos términos son toos primos.
Otros enunciaos qu'impliquen la infinitud de los númberos primos
Una resultancia entá más fuerte, y qu'implica direutamente la infinitud de los númberos primos, foi afayáu por Euler nel sieglu XVIII. Establez que laserie yediverxente. Unu de losteoremes de Mertens concreta más, estableciendo que:[23]onde la espresiónO(1) indica qu'esi términu ta acutáu ente -C yC pan mayor quen0, onde los valores deC yn0 nun tán especificaos.[24]
Sin ye un númberu natural mayor que 3, entós siempres esiste un númberu primup tal quen <p < 2n- 2.
Una manera más débil pero elegante de formulalo ye que, sin ye un númberu natural mayor que 1, entós siempres esiste un númberu primup tal quen <p < 2n. Esto supón que, nunaprogresión xeométrica de primer términu enteru mayor que 3 y razón igual a 2, ente cada términu de la progresión y el siguiente, tiense siquier un númberu primu.
Comparanza ente les funcionesπ(n) (azul),n / lnn (verde) y Li(n) (colloráu); puede vese que l'aproximamientu de π(n) con Li(n) ye meyor que la qu'hai con
Una vegada demostráu la infinitud de los númberos primos, cabo preguntar cómo se distribúin los primos ente los númberos naturales, esto ye, qué frecuentes son y ónde s'espera atopar eln-ésimo númberu primu. Esti estudiu empecipiarGauss yLegendre de forma independiente a finales delsieglu XVIII, pal cual introducieron lafunción enumerativa de los númberos primos π(n), y conxeturaron que'l so valor fora aproximao:.[25]
L'enfotu de demostrar esta conxetura tomó tol sieglu XIX. Les primeres resultancies fueron llograos ente 1848 y 1859 porChebyshov, quien demostró utilizando métodos puramentearitméticos la esistencia de dos constantesA yB tales que:pan abondo grande. Consiguió demostrar que, si esistía la llende del cociente d'aquelles espresiones, este tenía de ser 1.
En 1899 De la Vallée-Poussin demostró que l'error que se comete averando d'esta forma ye:pa una constante positivaa y pa cada enterum. Esta resultancia foi llixeramente ameyoráu a lo llargo de los años. Per otra parte, en 1901Von Koch amosó que si lahipótesis de Riemann yera cierta, teníase la siguiente estimación, más precisa:[26]
Una forma equivalente al teorema de los númberos primos ye que pn, eln-ésimo númberu primu, queda bien averáu pornln(n). N'efeutu,pn ye puramente mayor qu'esti valor.
Amestáu a la distribución de los númberos primos atópase l'estudiu de losintervalos ente dos primos consecutivos. Esti intervalu, cola única salvedá del qu'hai ente'l 2 y el 3, ten de ser siempres igual o mayor que 2, yá que ente dos númberos primos consecutivos siquier hai un númberu par y por tanto compuestu. Si dos númberos primos tienen por diferencia 2, dizse que sonximielgos, y cola salvedá del "triplete" formáu polos númberos 3, 5 y 7, los númberos ximielgos preséntense siempres de dos en dos. Esto tamién ye bono de demostrar: ente tres números impares consecutivos mayores que 3 siempres hai unu que ye múltiplu de 3, y por tanto compuestu. Los primeros pares de númberos primos ximielgos son (3,5), (5,7), (11, 13), (17, 19) y (29, 31).
Per otra parte, la diferencia ente primos consecutivos pue ser tan grande como se quiera: dau un númberu naturaln, se denota porn! el sofactorial, esto ye, el productu de tolos númberos naturales entendíos ente 1 yn. Los númberos
son toos compuestos: si 2 ≤i ≤n+1, entós (n+1)!+i ye divisible entei, por tanto, ye compuestu. La socesión, qu'entienden enteros consecutivos, nun contién nengún númberu primu. Por casu, sin=5, estos valores correspuenden a:
El siguiente valor, 6!+7=727, ye primu.[27] De toes formes, el menor númberu primu que falta del siguiente enn ye xeneralmente enforma menor que'l factorial, por casu, el casu más pequeñu de dos primos consecutivos separaos d'ocho unidaes ye (89, 97), ente que 8! ye igual a 40.320.
La socesión de les diferencies ente primos consecutivos[28] foi profusamente estudiada en matemátiques, y alredor d'esti conceutu estableciéronse munchesconxetures que permanecen ensin resolver.
La distribución de tolos númberos primos entendíos ente 1 y 76.800, d'esquierda a derecha y de riba abaxo. Cada pixel representa un númberu. Los píxeles negros representen númberos primos; los blancos representen númberos non primos.Imaxe con 2310 columnes que caltién múltiplos de 2, 3, 5, 7 y 11 nes columnes respeutives. Como cabo esperar, los númberos primos van cayer en columnes concretes si los númberos tán ordenaos d'esquierda a derecha y l'anchu ye un múltiplu d'un númberu primu. Sicasí, los númberos primos tamién queden distribuyíos de manera ordenada en construcciones espirales como laespiral de Ulam, yá que tienden a concentrase en delles diagonales concretes y non n'otres.
El modeláu de la distribución de los númberos primos ye una tema d'investigación recurrente ente los teóricos de númberos. La primalidá d'un númberu concretu ye (hasta agora) impredicible a pesar de qu'esisten lleis, como'lteorema de los númberos primos y elpostuláu de Bertrand, que gobiernen la so distribución a gran escala.Leonhard Euler comentó:
Hasta'l día de güei, los matemáticos intentaron en devanéu atopar dalgún orde na socesión de los númberos primos, y tenemos motivos pa creer que ye un misteriu nel que la mente enxamás va enfusar.[29]
Hai dos fechos sobre la distribución de los númberos primos de los qu'espero convence-yos de forma tan incontestable que van quedar permanentemente grabaos nos sos corazones. El primeru ye que, a pesar de la so definición simple y del papel que desempeñen como lladriyos colos que se constrúin los númberos naturales, los númberos primos crecen como meruxes ente los númberos naturales, y nun paecen obedecer nenguna otra llei que la del azar, y naide puede predicir ónde va brotar el siguiente. El segundu fechu ye entá más estelante, yá que diz xustu lo contrario: que los númberos primos amuesen una regularidá ablucante, qu'hai lleis que gobiernen el so comportamientu, y qu'obedecen estes lleis con precisión casi militar.[30]
Lapeñerada de Eratóstenes ye una manera senciella de topar tolos númberos primos menores o iguales qu'un númberu dau. Basar n'iguar una llista de tolos númberos naturales dende'l 2 hasta esi númberu y tachar repetidamente los múltiplos de los númberos primos yá descubiertos. Lapeñerada de Atkin, más moderna, tien una mayor complexidá, pero si optimízase apropiadamente tamién ye más rápida. Tamién esiste una reciénpeñerada de Sundaram que xenera namái númberos compuestos, siendo los primos los númberos faltantes.
Na práutica, lo que se desea ye determinar si un númberu dau ye primu ensin tener qu'iguar una llista de númberos primos. Un métodu pa determinar la primalidá d'un númberu ye ladivisión per tentativa, que consiste n'estremar socesivamente esi númberu ente los númberos primos menores o iguales al so raigañu cuadráu. Si dalguna de les divisiones ye exacta, entós el númberu nun ye primu; en casu contrariu, ye primu. Por casu, daun menor o igual que 120, pa determinar la so primalidá basta comprobar si ye divisible ente 2, 3, 5 y 7, una y bones el siguiente númberu primu, 11, yá ye mayor que √120. Ye'l test de primalidá más senciellu, y rápido pierde la so utilidá a la de comprobar la primalidá de númberos grandes, una y bones el númberu de factores posibles crez demasiáu rápido a midida que crez el númberu potencialmente primu.
N'efeutu, el númberu de númberos primos menores quen ye aproximao:.D'esta forma, pa determinar la primalidá den, el mayor factor primu que se precisa nun ye mayor que √n, dexando'l númberu de candidatos a factor primu en cerca de:.Esta espresión crez cada vez más amodo en función den, pero, como losn grandes son d'interés, el númberu de candidatos tamién se fai grande: por casu, pan = 1020 tiénense 450 millones de candidatos.
Coles mesmes, esisten otros munchos tests de primalidá deterministes que se basen en propiedaes que caractericen a los númberos primos, pero la so utilidá computacional depende enforma del test usáu. Por casu, podría emplegase elteorema de Wilson pa calcular la primalidá d'un númberu, pero tien l'inconveniente de riquir el cálculu d'unfactorial, una operación computacionalmente prohibitiva cuando se remanen númberos grandes. Equí ente en xuegu'ltiempu d'execución del algoritmu emplegáu, que s'espresa nanotación de Landau. Pa poder determinar la primalidá de númberos cada vez más grandes (de miles de cifres) búsquense aquellos algoritmos que'l so tiempu d'execución creza lo más amodo posible, a ser posible, que pueda espresase como unpolinomiu. Magar eltest de primalidá AKS cumple con esta condición, pal rangu de númberos que s'usa na práutica esti algoritmu ye desaxeradamente lentu.
Per otra parte, de cutiu basta con tener una respuesta más rápida con una altaprobabilidá (anque non segura) de ser cierta. Puede comprobase rápido la primalidá d'un númberu relativamente grande por aciutests de primalidá probabilísticos. Estos tests suelen tomar un númberu aleatoriu llamáu «testigu» ya introducilu nuna fórmula xunto col númberu potencialmente primun. Dempués de delles iteraciones, resuélvese quen ye «definitivamente compuestu» o bien «probablemente primu». Estos últimos númberos pueden ser primos o bienpseudoprimos (númberos compuestos que pasen el test de primalidá). Dalgunos d'estos tests nun son perfectos: puede haber númberos compuestos que'l test considere «probablemente primos» independientemente del testigu utilizáu. Esos númberos reciben el nome de pseudoprimos absolutos pa esi test. Por casu, losnúmberos de Carmichael son númberos compuestos, pero'ltest de Fermat evaluar como probablemente primos. Sicasí, los tests probabilísticos más utilizaos, como'ltest de Miller-Rabin o'l obsoletotest de Solovay-Strassen, superáu pol anterior, nun tienen esti inconveniente, entá siendo igualmente tests probabilísticos.
Dellos tests probabilísticos podríen pasar a ser determinísticos y dellos tests pueden ameyorar el so tiempu d'execución si verifíquense delles hipótesis matemátiques. Por casu, si verifícase lahipótesis xeneralizada de Riemann, puede emplegase una versión determinística del test de Miller-Rabin, y eltest de primalidá por curves elíptiques podría ameyorar notablemente'l so tiempu d'execución si verificárense delles hipótesis de teoría analítica de númberos.
Un algoritmu de factorización ye unalgoritmu que dixebra unu a unu los factores primos d'un númberu. Los algoritmos de factorización pueden funcionar tamién a manera de tests de primalidá, pero polo xeneral tienen un tiempu d'execución menos ventaxosu. Por casu, puede modificar l'algoritmu de división per tentativa de forma que nun se detenga cuando se llogre una división exacta, sinón que siga realizando nueves divisiones, y non sobre'l númberu orixinal, sinón sobre'l cociente llográu. Dempués de la división por tentativa, los métodos más antiguos que se conocen son elmétodu de Fermat, que se basa nes diferencies entecuadraos y que ye especialmente eficaz cuandon ye'l productu de dos númberos primos próximos ente sigo, y elmétodu de Euler, que se basa na representación den comosuma de dos cuadraos de dos formes distintes.
Más apocayá, ellaboráronse algoritmos basaos nuna gran variedá de téuniques, como lesfracciones continues o lescurves elíptiques, anque dalgunos son meyores de métodos anteriores (lapeñerada cuadrática, por casu, basar nuna meyora del métodu de Fermat y tien complexidá computacional subexponencial sobre'l númberu de cifres den). Otros, como'lmétodu rho de Pollard, son probabilísticos, y nun garanticen topar los divisores d'un númberu compuestu.
Lo que ye güei, l'algoritmu determinístico más rápidu d'usu xeneral ye'lxeneral number field sieve, que tamién tien complexidá computacional subexponencial sobre'l númberu de cifres den.[31] Propúnxose un algoritmu que'l so tiempu d'execución ye polinómico sobre'l númberu de cifres den (elalgoritmu de Shor), pero rique ser executáu nunordenador cuánticu, yá que'l so simulación nun ordenador normal rique un tiempu esponencial. Nun se conocen algoritmos pa factorizar nun ordenador tradicional en tiempu polinómico y tampoco se demostró qu'esto sía imposible.
A lo llargo de la historia, buscáronse numberosesfórmules pa xenerar los númberos primos. El nivel más altu d'esixencia pa una fórmula asina sería qu'acomuñara a cada númberu naturaln eln-ésimo númberu primu. De forma más indulxente, puede pidise una funciónf inyectiva qu'acomuñe a cada númberu naturaln un númberu primu de tala forma que cada unu de los valores tomaos apaeza solo una vegada.
Amás, esíxese que la función pueda aplicase, efectiva y conducentemente, na práutica.[32] Por casu, elteorema de Wilson asegura quep ye un númberu primu si y solu si (p-1)!≡-1 (modp). Otru exemplu: la función f(n) = 2 + ( 2(n!) mod (n+1)) xenera tolos númberos primos, solo los númberos primos, y solo el valor 2 tómase más d'una vegada. Sicasí, dambes fórmules basar nel cálculu d'un factorial, lo que les fai computacionalmente invidables.
Na busca d'estes funciones, investigar, notablemente, les funciones polinómiques. Cabo sorrayar que nengún polinomiu, entá en delles variables, devuelve solu valores primos.[33] Por casu, el polinomiu nuna variablef(n) =n² +n + 41, estudiada por Leonardo Euler, devuelve valores primos pan = 0,…, 39, sicasí pa n= 40, resulta un númberu compuestu.[34] Si'l términu constante val cero, entós el polinomiu ye múltiplu den, polo que'l polinomiu ye compuestu pa valores compuestos den. En casu contrariu, sic ye'l términu constante, entósf(cn) ye múltiplu dec, polo que si'l polinomiu nun ye constante, necesariamente tendrá d'incluyir valores compuestos.
Sicasí, hai polinomios en delles variables que los sos valores positivos (cuando les variables percuerren númberos naturales) son precisamente númberos primos. Un exemplu, ye esti polinomiu descubiertu por Jones, Sato, Wada y Wiens en 1976:[33]
Al igual qu'asocede coles fórmules con factoriales, esti polinomiu nun ye práuticu de calcular, yá que, anque los valores positivos que toma son toos primos, práuticamente nun devuelve otra cosa que valores negativos cuando se faen variar les variablesa az de 0 a infinitu.
Otru enfoque al problema d'atopar una función que solo xenere númberos primos vien dau a partir delteorema de Mills, qu'indica qu'esiste una constante θ tal que:
ye siempres un númberu primu, onde ye lafunción trío.[35] Inda nun se conoz nenguna fórmula pa calcular la constante de Mills, y los aproximamientos que s'empleguen na actualidá basar na socesión de los asina llamaos númberos primos de Mills (los númberos primos xeneraos por aciu esta fórmula), que nun pueden ser llograos rigorosamente, sinón solo de manera probabilística, suponiendo cierta lahipótesis de Riemann.
De mayor interés son otres fórmules que, anque non solo xeneren númberos primos, son más rápides d'implementar, sobremanera si esiste un algoritmu especializáu que dexe calcular rápido la primalidá de los valores que van tomando. A partir d'estes fórmules llógrense subconxuntos relativamente pequeños del conxuntu de los númberos primos, que suelen recibir un nome coleutivu.
Losnúmberos primos primoriales, direutamente rellacionaos cola demostración euclidiana de la infinitud de los númberos primos, son los de la formap =n#±1 pa dalgún númberu naturaln, onden# ye igual al productu 2·3·5·7·11·… de tolos primos ≤n. Coles mesmes, un númberu primu dizseprimu factorial si ye de la forman!±1. Los primeros primos factoriales son:
n!−1 ye primu pan = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, …[36]
n!+1 ye primu pan = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, …[37]
Construcción d'unpentágonu regular. 5 ye un númberu primu de Fermat.
Losnúmberos de Fermat, amestaos a la construcción depolígonos regulares conregla y compás, son los númberos de la forma, conn natural. Los únicos númberos primos de Fermat que se conocen hasta la fecha son los cinco que yá conocía'l mesmu Fermat, correspondientes an = 0, 1, 2, 3 y 4, ente que pa valores den ente 5 y 32 estos númberos son compuestos.[38]
Pa determinar la so primalidá, esiste un test especializáu que'l sotiempu d'execución ye polinómico: eltest de Pépin. Sicasí, los mesmos númberos de Fermat crecen tan rápido que solo se lo pudo aplicar pa valores den pequeños. En 1999 aplicar pan = 24. Pa determinar el calter d'otros númberos de Fermat mayores utilízase'lmétodu de divisiones socesives y de esa manera a fecha de xunu de 2009 conócense 241 númberos de Fermat compuestos, anque na mayoría de los casos desconoza'l so factorización completa.[38]
Losnúmberos de Mersenne son los de forma Mp = 2p – 1, ondep ye primu.[39] Los mayores númberos primos conocíos son xeneralmente d'esta forma, yá que esiste un test de primalidá bien eficaz, eltest de Lucas-Lehmer, pa determinar si un númberu de Mersenne ye primu o non.
Anguaño, el mayor númberu primu que se conoz yeM77 232 917 = 277 232 917 - 1, que tien 23 249 425 cifres nel sistema decimal. Trátase cronológicamente del 50ᵘ númberu primu de Mersenne conocíu y el so descubrimientu anunció'l 3 de xineru de 2018[40] gracies al proyeutu decomputación distribuyida «Great Internet Mersenne Prime Search» (GIMPS).
Esisten lliteralmente decenes deapellíos que pueden añader al conceutu denúmberu primu pa referise a un subconxuntu que cumple dalguna propiedá concreta. Por casu, losnúmberos primos pitagóricos son los que pueden espresase na forma 4n+1. Dichu d'otra forma, tratar de los númberos primos que'l so restu al estremalos ente 4 ye 1. Otru exemplu ye'l de losnúmberos primos de Wieferich, que son aquellos númberos primosp tales quep2 estrema a 2p-1 - 1.
Dalgunes d'estes propiedaes referir a una rellación concreta con otru númberu primu:
Númberu primu de Sophie Germain: daup primu, ye de Sophie Germain si 2p + 1 tamién ye primu. Una socesión de númberosp1,p2,p3,··· ,pn toos ellos primos, tales quepi+1=2pi+1 pa toui ∈ {1,2,···,n-1 }, denominarcadena (completa) de Cunningham de primera especie, y cumple por definición que cada unu de los términos, salvo'l postreru, ye un númberu primu de Sophie Germain. Créese que pa toun natural esisten infinites cadenes de Cunningham de llargorn,[41] anque hasta la fecha naide apurrió prueba de que dicha afirmación sía cierta.
Tamién se-yos da nomes especiales a delles clases de primos que dependen de la base de numberación emplegada o de la forma d'escribir los díxitos, y non d'una fórmula matemática. Ye'l casu de losnúmberossomirp (primos al aviesu), que son aquellos númberos primos tales que'l númberu llográu al invertir l'orde de les sos cifres tamién ye primu. Tamién ye'l casu de losnúmberos primos repunit, que son aquellos númberos primos que son concatenación d'unos. Si, en llugar de considerase'lsistema de numberación decimal considérase'lbinariu, llógrase otru conxuntu distintu de númberos primos repunit que, amás, coincide col de los númberos primos de Mersenne. Finalmente, losnúmberos primos triádicos son aquellos númberos que son primos,capicúes y simétricos respectu d'una recta horizontal.
El que se-y dea un nome a una clase de númberos primos con una definición precisa nun significa que se conoza dalgún númberu primu que sía d'esa clase. Por casu, nun se conoz hasta'l momentu nengúnnúmberu primu de Wall-Sun-Sun, pero la so relevancia anicia en qu'en 1992, antes de la demostración de Wiles delúltimu teorema de Fermat, afayóse que la falsedá del teorema pa un númberu primup dadu implicaba quep yera un númberu primu de Wall-Sun-Sun. Esto fizo que, mientres un tiempu, la busca de númberos primos d'esta clase fuera tamién la busca d'un contraejemplo del postreru teorema de Fermat.[44]
Esisten numberoses entrugues abiertes alrodiu de los númberos primos. Munches d'elles son problemes bien antiguos, y una de les más significatives ye la hipótesis de Riemann, delles vegaes mentada nesti artículu como una conxetura que, de ser cierta, dexaría conocer numberoses resultancies relevantes en diversos campos de les matemátiques.
Pa entender la hipótesis de Riemann, una conxetura enunciada en1859 pero que, hasta la fecha (2026), sigue ensin resolvese, ye necesariu entender lafunción zeta de Riemann. Sía unnúmberu complexu conparte real mayor que 1. Entós,
La segunda igualdá ye una consecuencia delteorema fundamental de l'aritmética, y amuesa que la función zeta ta íntimamente rellacionada colos númberos primos.
Esisten dos tipos de ceros de la función zeta, esto ye, valoress pa los cualos ζ(s) = 0: lostriviales, que sons=-2,s=-4,s=-6, etc. (los enteros pares negativos) y losnon triviales, que son aquellos ceros que nun s'atopen na exa real. Lo qu'indica la hipótesis de Riemann ye que la parte real de tolos ceros non triviales ye igual a 1/2.
La veracidá de la hipótesis implica una fonda conexón colos númberos primos, n'esencia, nel casu de verificase, diz que los númberos primos tán distribuyíos de la forma más regular posible. Dende un puntu de vista físicu», dizgrosso modo que les irregularidaes na distribución de los númberos primos solo vienen de ruíu aleatorio. Dende un puntu de vista matemáticu, diz que la distribución asintótica de los númberos primos (según elteorema de los númberos primos, la proporción de primos menores quen ye) tamién ye cierta pa intervalos enforma menores, con un error d'aproximao'l raigañu cuadráu den (pa intervalos próximos an). Ta llargamente estendíu na comunidá matemática que la hipótesis sía cierta. En concretu, la presunción más simple ye que los númberos primos nun tendríen de tener irregularidaes significatives na so distribución ensin una bona razón.[45]
Tamién hai numberoses conxetures que s'ocupen de determinaes propiedaes de la distribución de los númberos primos. Asina, laconxetura de los númberos primos ximielgos enuncia qu'hai infinitosnúmberos primos ximielgos, que son pares de primos que la so estrema ye de 2. Laconxetura de Polignac ye una versión más xeneral y más fuerte de l'anterior, yá que enuncia que, pa cada enteru positivun, hai infinitos pares de primos consecutivos que difieren en 2n. De la mesma, una versión más débil de la conxetura de Polignac diz que tounúmberu par ye la diferencia de dos númberos primos.
Coles mesmes, conxetúrase la infinidá de los primos de la forman2 + 1. Según laconxetura de Brocard, ente los cuadraos de primos consecutivos mayores que 2 esisten siempres siquier cuatro números primos. Laconxetura de Legendre establez que, pa cadan natural, esiste un númberu primu enten2 y (n+1)2. Finalmente, laconxetura de Cramér, que la so veracidá implicaría la de Legendre, diz que:
Otres conxetures rellacionen dellespropiedad aditivas de los númberos colos númberos primos. Asina, laconxetura de Goldbach diz que tou númberu par mayor que 2 puede escribise como suma de dos númberos primos, anque tamién esiste unaversión más débil de la mesma conxetura según la cual tou númberu impar mayor que 5 puede escribise como suma de tres números primos. El matemáticuchinuChen Jingrun demostró, en 1966, que n'efeutu, tou númberu par abondo grande puede espresase como suma de dos primos o como la suma d'un primu y de un númberu que ye'l productu de dos primos. ("semi-primu").[48]
Considérense por casu losenteros gaussianos, esto ye, losnúmberos complexos de la formaa+bi cona,b ∈. Este ye un dominiu d'integridá, y los sos elementos primos son losprimos gaussianos. Hai de solliñar que'l 2non ye un primu gaussiano, porque almiti factorización como productu de los primos gaussianos (1+i) y (1-i). Sicasí, l'elementu 3 sí ye primu nos enteros gaussianos, pero nun lu ye n'otru dominiu enteru. Polo xeneral, los primos racionales (esto ye, los elementos primos del aniellu) de la forma 4k+3 son primos gaussianos, pero nun lu son aquellos de la forma 4k+1.
Un problema central en teoría alxebraica de númberos ye la manera en que se factorizan los ideales primos cuando se ven sometíos a una estensión de cuerpos. Nel exemplu de los enteros gaussianos, (2) seramifica en potencia d'un primu (yá que y xeneren el mesmu ideal primu), los ideales primos de la forma soninertes (caltienen la so primalidá) y los de la forma pasen a ser productu de dos ideales primos distintos.
En teoría alxebraica de númberos surde otra xeneralización más. Dau uncuerpu, reciben el nome devaloraciones sobre determinaes funciones de en. Caúna d'estes valoraciones xenera unatopoloxía sobre, y dizse que dos valoraciones sonequivalentes si xeneren la mesma topoloxía. Unprimu de ye unaclase d'equivalencia de valoraciones. Con esta definición, los primos del cuerpu de losnúmberos racionales queden representaos pola funciónvalor absolutu según polesvaloracionesp-ádicas sobre pa cada númberu primup.
Enteoría de nuedos, unnuedu primu ye unnuedu non trivial que nun se puede descomponer en dos nuedos más pequeños. De forma más precisa, tratar d'un nuedu que nun se puede escribir comosuma conexa de dos nuedos non triviales.
En1949Horst Schubert demostró un teorema de factorización análogu al teorema fundamental de l'aritmética, qu'asegura que cada nuedu puede llograse de forma única como suma conexa de nuedos primos.[51] Por esti motivu, los nuedos primos desempeñen un papel central na teoría de nuedos: una clasificación de los nuedos foi dende finales del sieglu XIX la tema central de la teoría.
Nel estudiu de los númberos complexos, allegar al conceutu de «primos relativos» pa definirraigaños primitivos de la unidá .[52] Si n ye un númberu primu toes los raigaños enésimos de 1 son raigaños primitivos, salvo'l raigañu 1.
Na definición d'uncuerpu finito, esíxese que'l númberu d'elementos d'un aniellu sía enteru primu. En tal casu, esaniciando'l cero, cada elementu tien inversu multiplicativu y llógrase la estructura d'un cuerpu.[53]
Na definición d'un polígonu estrelláu den llaos, pa tomar los puntos dem enm, esíxese quem sía menor quen/2 y primu conn.[54]
Al definir elrepresentante canónicu d'un númberu racional, usando clases d'equivalencia de pares ordenaos de númberos enteros, necesariamente, el par ordenáu definente tien qu'arreyar dos enteros primos relativos. A fortiori, a lo menos unu d'ellos, un primu absolutu.[55]
L'algoritmu RSA basar nel llogru de laclave pública por aciu la multiplicación de dos númberos grandes (mayores que 10100) que sían primos. La seguridá d'estialgoritmu anicia en que nun se conocen maneres rápides de factorizar un númberu grande nos sos factores primos utilizandoordenadores tradicionales.
Los númberos primos influyeron en numberosos artistes y escritores. El compositor francésOlivier Messiaen valir d'ellos pa crear música non métrica. N'obres tales comoLa Nativité du Seigneur (1935) oQuatre études de rythme (1949-50) emplega simultáneamente motivos que la so duración ye un númberu primu pa crear ritmos impredicibles. Según Messiaen, esta forma de componer foi «inspirada polos movimientos de la naturaleza, movimientos de duraciones llibres y desiguales».[56]
Na so novela de ciencia ficciónContact, darréuafecha al cine,Carl Sagan suxer que los númberos primos podríen ser emplegaos pa comunicase con intelixencies estraterrestres, una idea que desenvolviera de manera informal col astrónomu estauxunidenseFrank Drake en 1975.[57]
Na novelaPopCo deScarlett Thomas, la güela de Alice Butler trabaya na demostración de lahipótesis de Riemann. El llibru ilustra una tabla de los mil primeros númberos primos.[58]
L'escritor grieguApostolos Doxiadis, escribióEl tíu Petros y la conxetura de Goldbach, que narra cómo un ficticiu matemática maravía de principios de sieglu XX somorguiar nel mundu de les matemátiques d'una forma apasionante. Tratando de resolver unu de los problemes más difíciles y entá non resueltos de la matemática «La Conxetura de Goldbach», la cual reza: «Tou númberu par puede espresase como la suma de dos númberos primos».
↑Hans Riesel,Prime Numbers and Computer Methods for Factorization. New York: Springer (1994): 36 (n'inglés)
↑Richard K. Guy & John Horton Conway,The Book of Numbers. New York: Springer (1996): 129 - 130 (n'inglés)
↑Gowers, T(2002).Mathematics: A Very Short Introduction.Oxford University Press,páx. 118.ISBN 0-19-285361-9.«La esclusión aparentemente arbitraria del 1 de la definición de númberu primu … nun espresa nenguna conocencia fonda sobre los númberos: trátase a cencielles d'un conveniu útil, adoptáu por que solo haya una manera de factorizar cualquier númberu nos sos factores primos»
↑Nicholas Anderson, Andrew J. Havens, Brian Hydefrost, Sean Murphy y Steve Sarasin.«Prime Numbers and the Riemann Hypothesis»páxs.6.Archiváu dende l'orixinal, el 15 de xunu de 2010.Consultáu'l 7 de xunu de 2009.
↑The On-Line Encyclopedia of Integer Sequences!.«A000979. Wagstaff primes.».Archiváu dende l'orixinal, el 18 de xunu de 2010.Consultáu'l 23 d'abril de 2010.
Sobre l'artículu de Manindra Agrawal et al. PRIMES IS IN P, onde afirmen: "We present a deterministic polynomial-time algorithm that determines whether an input numbern is prime or composite"mathmistakes
