Cuáles son los número primos

Un número primo es un número entero superior a 1 que admite exactamente dos divisores: 1 y él mismo. Los números primos menores que 100 son:

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

Nótese el hecho de que todos los números naturales son divisibles entre ellos mismos y entre la unidad. Pero los que no son primeros, además, también son divisibles entre otros números.

El número primo más pequeño es el 2 y, de hecho, es el único número primo que es también par , ya que cualquier par mayor es múltiplo de dos.

El teorema fundamental de la aritmética establece que cualquier entero positivo superior a 1 puede representarse siempre como un producto de números primos, y esta representación (factorización) es única.

los numeros primos

El teorema de Euclides prueba que existen infinitos números primos. Además se sabe que no hay límite para la distancia entre dos primeros consecutivos, esto es, dado un número N, se pueden encontrar dos números primos a y b tales que entre a y b no hay otros números primos y que la diferencia entre a y b es superior a N .

Todavía no se ha podido probar, pero se conjetura que existen infinitos números primos de la forma p 1 = p 2 + 2 (siendo p 1 y p 2 primeros) o primeros gemelos. Sí se ha probado que los únicos primeros trillizos (primeros de la forma p 1 = p 2 + 2 y p 2 = p 3 + 2) son 3 , 5 y 7.

Hay numerosos algoritmos para encontrar números primos. Lo más sencillo sería intentar dividir cada número por todos los inferiores o iguales a su raíz cuadrada, pero es muy poco eficiente porque requiere muchas divisiones innecesarias; por ejemplo, una vez probado el dos, no es necesario probar todos los números pares, que sabemos que serán divisibles por dos. Una extensión de esta idea es el tamiz de Eratóstenes.

Historia

El hueso de Ishango , data de hace más de 20.000 años (antes de la aparición de la escritura). Lo encontró el arqueólogo Jean de Heinzelin de Braucourt. Presenta unas muescas que parecen representar cuatro números primos: 11, 13, 17 y 19.

Algunos arqueólogos interpretan este hecho como una prueba de que quien las hizo conocía los números primos . Con todo, existen muy pocos hallazgos que permitan entender los conocimientos que tenía realmente el hombre de aquella época.

Numerosas tablillas de arcilla seca atribuidas a las civilizaciones que se fueron sucediendo en Mesopotamia a lo largo del II milenio aC muestran la resolución de problemas aritméticos y acrediten los conocimientos de la época. Para calcular divisiones necesitaban conocer el inverso de los naturales , se han encontrado tablillas con estas tablas de inversos. En el sistema sexagesimal que empleaban los babilonios para escribir los números, los inversos de los divisores de potencias de 60 se calculan fácilmente, por ejemplo, dividir entre 24 equivale a multiplicar por 150 {\ Displaystyle 2 \ cdot 60 ^ {1} +30 \ cdot 60 ^ {0}} Y desplazar la coma sexagesimal dos lugares (ya que {\ Displaystyle 24 \ cdot {\ frac {2 \ cdot 60 ^ {1} +30 \ cdot 60 ^ {0}} {60 ^ {2}}} = 1}. Para conocerlo había una sólida comprensión de la multiplicación , la división y la factorización de los enteros .

En las matemáticas egipcias , el cálculo de fracciones requería conocimientos sobre las operaciones, la división de naturales y la factorización.

Los egipcios sólo operaban con las llamadas fracciones unitarias, es decir, las que tenían numerador igual a 1 {\ Displaystyle {\ tfrac {1} {2}}, {\ tfrac {1} {3}}, {\ tfrac {1} {4}}, {\ tfrac {1} {5}}, \ dots}. Las fracciones de numerador distinto de 1 escribían como suma de inversos de naturales, si podía ser sin repetición {\ Displaystyle {\ tfrac {1} {2}} + {\ tfrac {1} {6}}} en vez de {\ Displaystyle {\ tfrac {1} {3}} + {\ tfrac {1} {3}})}.

Para ello seguramente había que tener una tabla de los primeros números primos.

La primera prueba indiscutible del conocimiento de los números primos se remonta alrededor del año 300 aC y se encuentra en los Elementos de Euclides (volúmenes VII a IX).

Euclides define los números primos, demuestra que hay infinitos, define el máximo común divisor y el mínimo común múltiplo y proporciona los algoritmos para determinar de que hoy se conocen como algoritmo de Euclides.

Los Elementos contienen también el teorema fundamental de la aritmética y la forma de construir un número perfecto a partir de un número primo de Mersenne.

El criba o tamiz de Eratóstenes , atribuido a Eratóstenes de Cirene , es un método sencillo que permite encontrar números primos.

cuales son los numeros primos

Pierre de Fermat

Después de la época de la Grecia antigua, no hubo muchos avances en el estudio de los números primos hasta el siglo XVII. El 1640 Pierre de Fermat enunció sin demostrarlo el pequeño teorema de Fermat, más adelante el demostraron Leibniz y Euler . Puede que mucho antes ya se conociera un caso especial de este teorema en China.

Fermat enunció la conjetura de que todos los números de la forma {\ Displaystyle 2 ^ {2 ^ {n}} + 1} son primos (por eso estos números se denominan números de Fermat ) y verificó la hipótesis hasta n = 4 (es decir, 2 16  + 1).

Pero Euler demostró que el siguiente número de Fermat (2 32  + 1) es compuesto (uno de sus factores primos es 641). De hecho, hasta la fecha no se ha encontrado ningún otro número primo de Fermat aparte de los que ya conocía Fermat.

El monje francés Marin Mersenne investigó los números primos de la forma 2 p  – 1, con p primo. En su honor, hoy se denominan números de Mersenne .

Los trabajos de Euler en teoría de números contienen muchos resultados referentes a los números primos. Demostró que la serie infinita{\ Displaystyle {\ tfrac {1} {2}} + {\ tfrac {1} {3}} + {\ tfrac {1} {5}} + {\ tfrac {1} {7}} + \ dots}(lasuma de los inversos de los números primos ) es divergente.

En 1747 demostró que todos los números perfectos pares son de la forma {\ Displaystyle 2 ^ {p-1} (2 ^ {p} -1) \}, Donde el segundo factor es un número primo de Mersenne.

A comienzos del siglo XIX , Legendre y Gauss van conjeturar de forma independiente que, cuando n tiende a infinito, la cantidad de números primos menores o iguales que , donde es el logaritmo natural de n.

Las ideas que Riemann expresó en un trabajo de 1859 sobre la función zeta abrieron un camino que conduciría a la demostración del teorema de los números primos.

Hadamard y De Valle-Poussin , cada uno por separado, dieron forma a este esquema y lograron demostrar el teorema en 1896.

Actualmente, en el caso de números grandes, para comprobar si un número es primo, no se hace por divisiones sucesivas . Muchos matemáticos han desarrolladotests de primalidad, a menudo restringidos a categorías específicas de números primos.

Algunos ejemplos son el test de Pépin para los números de Fermat (1877), el teorema de Proth (~ 1878), la prueba de Lucas-Lehmer para números de Mersenne (a partir de 1856) y el test de Lucas -Lehmer generalizado.

También existen algoritmos para números arbitrarios (es decir, sin necesidad de que pertenezcan a una determinada categoría), pero son mucho más lentos, como es el caso del test APRT-cl , el test de primalidad por curvas elípticas y el AKS .

Durante mucho tiempo, se pensaba que la aplicación de los números primos era muy limitada fuera de la matemática pura . Esto cambió en los años 1970 con el desarrollo de la criptografía de clave pública , en la que los números primos eran la base de los primeros algoritmos como el algoritmo RSA .

Desde el 1951, el número primo más grande conocido siempre ha sido descubierto con la ayuda de ordenadores. La búsqueda de números primos cada vez mayores ha suscitado interés incluso fuera de la comunidad matemática. En los últimos años han ganado popularidad proyectos de computación distribuida tales como el GIMPS .

Definición de número primo

Un número primo es un número natural que tiene dos y sólo dos divisores naturales distintos, el 1 y él mismo.

Hasta el siglo XIX , los matemáticos mayoritariamente consideraban que el 1 era primero, entendiéndose que la definición de número primo consistía en la divisibilidad entre 1 y él mismo pero que no requería un número mínimo de divisores diferentes.

Muchos trabajos matemáticos siguen siendo válidos a pesar de considerar el 1 como un número primo, por ejemplo el trabajo de Stern y Zeisel. La lista de Derrick Norman Lehmer de números primos hasta el 10006721, reimpresa hasta 1956 comenzaba con el 1 como primer número primo.

El cambio de nomenclatura se produjo porque que fuera válido el siguiente enunciado del teorema fundamental de la aritmética : «todo número natural tiene una representación única como producto de factores primos, salvo el orden ».

Además, los números primos tienen muchas propiedades que no tiene el 1, tales como la relación del número con el valor correspondiente de la función de Euler o la función suma de divisores.

Demostración de la infinitud de los números primos 

La primera demostración de la infinitud de los números primos la proporcionó Euclides en el libro IX de los Elementos . En la matemática moderna, a menudo se ha distorsionado la demostración y se ha considerado un ejemplo clásico de demostración indirecta (no constructiva), pero la demostración original es constructiva.

Euclides no dice explícitamente que existen infinitos números primos, el enunciado que demuestra es que «los números primos son más que cualquier cantidad dada de números primos» y la demostración consiste en construir un número primo que no es ninguno de los dados.

La demostración de los Elementos comienza con una cantidad finita dada de números primos. Se construye m el mínimo común múltiplo de estos primeros, y se considera el número m + 1 .

Este número puede ser primero o no serlo. Si lo es, entonces ya ha encontrado un primer más de los que había al principio. Si no lo es, entonces debe tener como divisor un número primo.

Este primero no es ninguno de los números primos con los que se había comenzado, ya que si lo fuera entonces sería divisor tanto m como de m + 1 , y en consecuencia sería divisor de 1 , lo cual es absurdo.

Así pues, también en este caso se ha encontrado un primer diferente de los del comienzo. Por tanto, la demostración concluye, «los números primos son más que cualquier cantidad dada de números primos».

El enunciado moderno, que «existen infinitos números primos», se debe demostrar indirectamente, por reducción al absurdo . Es de suponer que el conjunto de todos los números primos es finito, y llegar a una contradicción. Aparte de esta sutileza, la idea de la demostración de Euclides es válida, aunque se suele sustituir el concepto de mínimo común múltiplo por el de producto, que en el caso de números primos es equivalente.

Para empezar la demostración, supongamos que el conjunto de números primos es finito, y que de estos primeros P es el más grande. Construimos entonces el número (2 · 3 · 5 · 7 · 11 · … · P ) + 1, es decir el producto de todos los números primos más uno.

Este número no es divisible por 2, ni por 3, ni por 5, ni, en definitiva, por ningún número primo, ya que en todos los casos la división da 1 como resto. Por lo tanto sólo puede ser que (2 · 3 · 5 · 7 · 11 · … · P ) + 1 sea primero o que sea divisible por otro número primo que está entre P y (2 · 3 · 5 · 7 · 11 · … · P ) + 1; en cualquiera de los dos casos hemos encontrado un número primo mayor que P , contradiciendo la suposición inicial y, por tanto, demostrando el teorema.

Propiedades 

  • 2 es el único número primo par, dado que cualquier otro número par mayor de dos es divisible entre 2. Por tanto, la expresión número primo impar , significa número primo mayor que 2.
  • Todos los números primos excepto 2 y 5, escritos en base 10 , terminan en 1, 3, 7 o 9, ya que los que terminan en 0, 2, 4, 6 u 8 son múltiplos de 2 y los que terminan en 0 o 5 son múltiplos de 5. en general en cualquier base todos los números primos salvo un número finito terminan con una cifra que es un número coprimo con la base.
  • Todos los números primos mayores de 3 son de la forma 6 n  – 1 o 6 n  + 1, porque todos los demás números son divisibles entre 2 o 3.
  • Generalizando embargo, todos los números primos mayores que q son de forma q # · n  +  m , donde 0 < m < q , y m no tiene ningún factor primo ≤ q . ( Q # oprimporial de q es el producto de todos los números primos menores o iguales que q ).
  • Si p es un número primo y p es un divisor de ab , entonces p es un divisor de a o p es un divisor de b (o de ambos). Esta afirmación se conoce con el nombre delema de Euclides y se utiliza para demostrar la unicidad de la descomposición en factores primos .
  • El anillo Z / n Z es un cuerpo si y sólo si n es primo. Equivalentemente: n es primo si y só si φ ( n ) = n – 1.
  • Si p es un número primo distinto de 2 y 5,{\ Displaystyle {\ tfrac {1} {p}}}{\ Displaystyle {\ tfrac {1} {p}}}es siempre un número decimal periódico , de periodo p  – 1 o un divisor de p  – 1. Esto se deduce directamente a partir del pequeño teorema de Fermat .{\ Displaystyle {\ tfrac {1} {p}}}{\ Displaystyle {\ tfrac {1} {p}}}expresado en base q (en vez de base 10) se obtienen propiedades similares, siempre que p no sea un factor primo de q .
  • La característica de cualquier cuerpo es, o bien cero, o bien un número primo.
  • La constante de Copeland-Erdős ,235711131719232931374143 …, obtenida por concatenación de los números primos consecutivos expresados en base 10, es un número irracional .

Teoremas relativos a los números primos 

Teorema fundamental de la aritmética 

El teorema fundamental de la aritmética afirma que

 Todo número natural superior a 1 se puede escribir, de forma única como producto de números primos .

El teorema contiene dos afirmaciones, la primera es que todo número se puede escribir como producto de números primos (esto es trivial porque si no, él mismo es un número primo y por tanto cumple la afirmación como producto trivial de un único factor), la segunda es la más interesante y consiste en el hecho de que no se pueden encontrar dos productos diferentes (excepto el orden en que se presenten los factores).

Su demostración es inmediata a partir del lema de Euclides que dice que: si un número primo p es divisor del producto a * b y no es divisor de a entonces es divisor de b .

Teorema de Tchebychev

El postulado de Bertrand , llamado también teorema de Tchebychev , afirma que si n es un número natural superior o igual a 1, entonces siempre existe por cabizbajo un número primo p tal que

James Joseph Sylvester el generalizó con la proposición siguiente: el producto de k enteros consecutivos superiores a k es divisible por un número primo mayor que k .

Pequeño teorema de Fermat 

El Pequeño Teorema de Fermat , obtenido por Pierre de Fermat , afirma que si p es un número primo, por cualquier número natural a se cumple que numeros primos.

En caso de que se conozca un número a para el que no se cumpla la afirmación del teorema, este teorema permite afirmar que un número no es un número primo sin necesidad de conocer su descomposición en factores primos.

Esta observación se utiliza en algunos tests de primalidad para aumentar la probabilidad de que un números sea primero (o garantizar que no lo es) a base de ir probando diferentes números a escogidos al azar.

Los números de Carmichael también cumplen la condición impuesta por el teorema sin ser números primos.

Teorema de Wilson

El teorema de Wilson establece que, el número natural p es primo si y sólo si ,

esto es, si y sólo si, {\ Displaystyle (p-1)! + 1}es divisible entre p .

Teorema de la progresión aritmética

El teorema de la progresión aritmética , se enuncia de la siguiente manera:

Para todos los naturales no nulos n y m primos entre ellos , la progresión aritmética , Contiene una infinidad de números primos .

Clases de números primos 

Números primos de Mersenne 

Un número primo de Mersenne es un número primo que es igual a una potencia de 2 menos 1. Por ejemplo, 3 = 4-1 = 2 2 – 1 es un primo de Mersenne, al igual que 7 = 8-1 = 2 3 – 1. En cambio, 15 = 16-1 = 24 – 1, por ejemplo, no es primo.

En general, pues, los números primos de Mersenne son números primos de la forma:

M n = 2 n – 1.

Los números primos más grandes que se conocen son generalmente de esta forma, ya que existe un test de primalidad muy eficaz, el test de Lucas-Lehmer , para determinar si un número de Mersenne es primo o no.

Actualmente, el número primo más grande que se conoce es M 43112609 = 2 43112609 -1, que tiene 12.978.189 cifras en escribirlo en base diez.

Se trata cronológicamente del 45º número primo de Mersenne conocido y su descubrimiento se anunció el 23 de agosto de 2008 gracias al proyecto de computación distribuida ” Great Internet Mersenne Prime Search » (GIMPS). El 46º número primo de Mersenne fue descubierto dos semanas después, pero es más pequeño que el 45.

Actualmente no se sabe si hay un número infinito de números primos de Mersenne, pero se tiene la sospecha de que la respuesta es afirmativa y, de hecho, es una parte del contenido de la conjetura de Lenstra-Pomerance-Wagstaff .

Números primos de Sophie Germain 

Un número primo de Sophie Germain es aquel número primo p tal que 2 p + 1 también es primo.

Actualmente el número primo de Sophie Germain más grande que se conoce es 48047305725 · 2 172,403mo – 1, un número de 51,910 dígitos obtenido en enero de 2007. No se sabe si hay infinitos números primos de Germain .

Una sucesión de números , Todos ellos primeros, tales que para todo , Se llama cadena (completa) de Cunningham de primera especie , y cumple por definición que cada uno de sus términos, salvo el último, es un número primo de Sophie Germain.

Se cree que para todo n natural existen infinitas cadenas de Cunningham de longitud n , aunque no se conoce ningún método directo para generar dichas cadenas.

Números primos gemelos

Los números primos gemelos son aquellas parejas de números primos que difieren en 2. Es decir, p y q (con p < q ) son primos gemelos si q = p + 2. Excepto por el caso del 2 y el 3, esta es la mínima diferencia que puede haber entre dos primeros.

No se sabe si existen infinitos números primos gemelos.

Se ha demostrado que la pareja n , n + 2 son números primos gemelos si y sólo si :

Los números primos gemelos más grandes conocidos son la pareja 2003663613 · 2 195000 -1 y 2003663613 · 2 195000 +1, que tiene 58.711 dígitos. Fueron descubiertos en 2007 por Vautier, McKibbon, Gribenko et al .

Antes eran, la pareja 100314512544015 · 2 171960 -1 y 100314512544015 · 2 171960 +1, que tiene 51.780 dígitos y fue descubierto en el 2006 por los matemáticos húngaros: Zoltán Jara, Gabor Farkas, Timea Csajbok, Janos Kasza y Antal Jara.

Números primos de Fermat 

Un número de Fermat , es un número natural de la forma:

donde n es natural. Los números primos de Fermat son números de Fermat que a la vez son primos.

Se puede demostrar que cualquier número primo de la forma 2 n + 1 debe ser un número de Fermat. Los únicos números primos de Fermat conocidos son F0, F1, F2, F3, y F4.

Conjeturas sobre los números primos 

Hay muchas cuestiones abiertas relativas a los números primos, por ejemplo:

  • La conjetura de Goldbach : Todo número natural par igual o superior a 4 se puede escribir como suma de dos números primos.
  • La conjetura de De Polignac : todo número natural par se puede escribir como diferencia de dos números primos consecutivos y además hay un número infinito de maneras.
  • Conjetura de los números primos gemelos : Hay una infinidad de números primos gemelos.
  • Toda sucesión de Fibonacci contiene infinitos números primos.
  • Hay infinitos números primos de Fermat .
  • Hay infinitos números primos de la forma n 2 + 1
  • La conjetura de Legendre afirma que siempre existe un número primo entre n 2 y ( n + 1) 2 . Esta conjetura no demostrada está relacionada con la hipótesis de Riemann que tampoco está demostrada.

Obtención de números primos

Hay una serie de problemas relacionados con la obtención de números primos. A pesar de ser diferentes, están íntimamente relacionados entre sí:

  1. Encontrar todos los números primos menores que uno dado.
  2. Dado un número, saber si es o no un número primo.
  3. Encontrar un número primo mayor que uno dado o mayor que uno dado y más pequeño que otro.
  4. Dado un número compuesto, encontrar un factor.
  5. Dado un número encontrar su descomposición en factores primos.

Para resolver el problema primero hay que saber si cada uno de los números es o no primero, es decir resolver el problema 2 para cada caso. Un algoritmo que resuelve este problema es el criba de Eratóstenes .

Una forma de resolver el problema 2 es probar si es divisible o no entre todos los números menores que su raíz cuadrada. Para hacer esto hay algoritmos que usan una lista de todos los números primos menores que uno dado (solución del problema 1).

A veces no es necesario saber con absoluta certeza si un número es primo o no, para algunas aplicaciones prácticas basta con tener una probabilidad muy grande de que lo sea.

Los tests de primalidad buscan saber si un número no es primero con certeza y si lo es tener una probabvilitat muy grande. En el extremo, cuando la probabilidad es del 100% (entonces son demostraciones de primalidad) resuelven exactamente el problema 2.

El problema 3 es de gran interés en criptografía. Una forma de hacerlo es elegir un número al azar dentro del intervalo, aplicarle un test de primalidad y si falla probar otro hasta que se encuentra uno.

Aunque parezca poco práctico este método funciona bastante bien porque hay bastantes números primos y aunque se trate de números muy grandes la cantidad de pruebas que hay que hacer es aceptable. Otra forma sería tener fórmulas que dieran números primos .

Los problemas 4 y 5 son prácticamente lo mismo. Aplicando repetidamente un método para resolver el problema 4 se resuelve el 5. Esto lo hacen los algoritmos de factorización . Tenga en cuenta que todo algoritmo de factorización, si falla, es una demostración de primalidad.

tabla numeros primos

El criba de Eratóstenes obtenido porEratóstenes de Cirene , un matemático griego delsiglo III aC es un algoritmo sencillo que permite encontrar todos los números primos menores o iguales que uno dado.

Criba de Erastòstenes

El criba de Eratóstenes es una manera sencilla de encontrar todos los números primos menores o iguales que un número dado. Se basa en escribir una lista de todos los números naturales desde el 2 hasta el número y tachar repetidamente los múltiplos de los números primos ya descubiertos.

El criba de Atkin, más moderno, tiene una mayor complejidad, pero si se optimiza apropiadamente también es más rápido.

Test de primalidad 

Un método para determinar la primalidad de un número es la factorización por prueba de divisiones , que consiste en dividir sucesivamente este número entre los números primos menores o iguales a su raíz cuadrada.

Si alguna de las divisiones es exacta, entonces el número no es primo; en caso contrario, es primero. Por ejemplo, dado n menor o igual que 120, para determinar si es primero basta con comprobar si es divisible entre 2, 3, 5 y 7, ya que el siguiente número primo, 11, ya es mayor que .

Es el test de primalidad más sencillo. Si el número no tiene factores pequeños el algoritmo no es práctico. Por regla general se utiliza este procedimiento sólo para encontrar factores hasta un cierto límite, entonces se habla de prueba de divisiones incompleta.

De todos modos, es una paso previo para muchos otros tests de primalidad, y si se trata de números elegidos al azar permite descartar muchos con muy poco tiempo de cálculo.

Para un n aleatorio, existe un 50% de oportunidades de que 2 sea un factor de n , y 33% de oportunidades de que 3 sea un factor, y así sucesivamente. Se puede demostrar que un 88% de todos los naturales tienen un factor inferior a 100, y que un 91% tienen un factor inferior a 1000.

Para aplicaciones de criptografía no es aplicable este método para factorizar números porque el números compuestos que se hacen sevir ya se eligen de forma que sus factores sean mayores.

Hay muchos otros tests de primalidad determinísticos que se basan en propiedades que caracterizan a los números primos, pero su utilidad computacional depende mucho del test utilizado.

Por ejemplo, se podría emplear el teorema de Wilson para calcular la primalidad de un número, pero tiene el inconveniente de requerir el cálculo de un factorial , una operación computacionalmente prohibitiva cuando se manejan números grandes. Aquí entra en juego el tiempo de ejecución del algoritmo utilizado, que se expresa en la notación de Landau.

Para poder determinar la primalidad de números cada vez más grandes (de miles de cifras) se buscan algoritmos tales que su tiempo de ejecución crezca lo más lentamente posible, si es posible, que se pueda expresar como un tiempo polinómico . Uno de los tests determinísticos más rápidos es el test de primalidad AKS .

A menudo basta con tener una respuesta más rápida con una alta probabilidad (aunque no segura) de ser cierta. Se puede comprobar rápidamente la primalidad de un número relativamente grande mediantetests de primalidad probabilísticos.

Estos tests suelen coger un número aleatorio llamado “testigo” e introducirlo en una fórmula conjuntamente con el número potencialmente primer n . Después de varias iteraciones, se resuelve que n es “con certeza compuesto” o “probablemente primero”.

Algunos de estos tests no son perfectos: puede haber números compuestos que el test considere “probablemente primeros” independientemente del testigo utilizado. Estos números reciben el nombre de pseudoprimers para este test.

Por ejemplo, los números de Carmichael son números compuestos, pero el test de Fermat los evalúa como probablemente primeros. Sin embargo, los tests probabilísticos más utilizados, como el test de Miller-Rabin o el test de Solovay-Strassen , no tienen este inconveniente.

Algunos tests probabilísticos podrían ser deterministas y otros pueden mejorar el tiempo de ejecución si se cumplen algunas hipótesis matemáticas.

Por ejemplo, si se confirmara la hipótesis generalizada de Riemann, se puede usar una versión determinista del test de Miller-Rabin, y el test de primalidad por curvas elípticas podría mejorar notablemente el tiempo de ejecución si se confirmaran algunas hipótesis de teoría analítica de números.

Fórmulas que generan números primos

A lo largo de la historia, se han buscado numerosas fórmulas para generar los números primos. El nivel más alto de exigencia sería que la fórmula asociara a cada número natural n el n -siendo número primo.

De forma más indulgente, se puede pedir una función f que asocie a cada número natural n un número primo de tal forma que cada uno de los valores obtenidos sólo aparezca una vez.

Además, se desea que la función se pueda calcular en la práctica. Por ejemplo, el teorema de Wilson asegura que p es un número primo si y sólo si .

Otro ejemplo: la función genera todos los números primos, sólo los números primos, y sólo el valor 2 aparece más de una vez. Sin embargo, ambas fórmulas se basan en el cálculo de un factorial, lo que las hace computacionalmente inviables.

En la búsqueda de estas funciones, se han investigado notablemente las funciones polinómicas. Se puede afirmar que ningún polinomio, incluso de varias variables, no toma sólo valores primeros para valores enteros de las variables.

Por ejemplo, el polinomio de una variable f ( n ) = n 2 – n +41 da valores primeros para n = 0 …, 40, 43, pero f (41) y f (42) son compuestos. Sin embargo, hay polinomios de varias variables los valores positivos de las cuales (cuando las variables recorren los números naturales) son precisamente los números primos. Un ejemplo es este polinomio descubierto por Jones, Sato, Wada y Wiens en 1976:

polinomio

Al igual que con las fórmulas con factoriales, emplear este polinomio no es práctico, ya que, aunque los valores positivos que toma son todos primeros, prácticamente no da otra cosa que valores negativos cuando se hacen variar las variables a a z de 0 a infinito.

Otro enfoque al problema de encontrar una función que sólo genere números primos viene dado a partir del teorema de Mills , que indica que existe una constante que  es siempre un número primo, donde es la función parte entera.

No se conoce ninguna fórmula para calcular la constante de Mills, y las aproximaciones que se emplean en la actualidad se basan en la sucesión de los llamados números primos de Mills (los números primos generados mediante esta fórmula), que no se pueden obtener rigurosamente sino sólo de manera probabilística, suponiendo cierta la hipótesis de Riemann .

Algoritmos de factorización 

Un algoritmo de factorización es el que resuelve el probelma de expresar un número como producto de sus factores primos. Si se tiene un algoritmo para encontrar un factor de un número, entonces el mismo algoritmo sirve para expresarlo como producto de sus factores primos.

Sólo hay que aplicar el mismo algoritmo repetidamente hasta que todos los factores sean números primos.

Tras la factorización por prueba de divisiones , los métodos más antiguos que se conocen son el método de Fermat , que se basa en las diferencias entre cuadrados y que es especialmente eficaz cuando n es el producto de dos números primos cercanos entre sí, y el método de Euler, que se basa en la representación de n como suma de dos cuadrados de dos formas diferentes.

Más recientemente, se han elaborado algoritmos basados en una gran variedad de técnicas, como las fracciones continuas o las curvas elípticas , algunos son mejoras de métodos anteriores como el criba cuadrática, por ejemplo, que se basa en una mejora del método de Fermat.

Otros, como el método rho de Pollard , son probabilísticos, y no garantizan encontrar los divisores de un número compuesto.

Actualmente el algoritmo determinista más rápido de uso general es el criba sobre el cuerpo de números generalizado , la complejidad computacional es exponencial sobre el número de cifras de n.

Se ha propuesto un algoritmo de tiempo de ejecución polinómico sobre el número de cifras de n (el Algoritmo de Shor ), pero hay que ejecutarlo en un ordenador cuántico , ya que su simulación en un ordenador normal requiere un tiempo exponencial.

Distribución

La espiral de Ulam .Empezando por el centro cada pixel representa un número natural, se ordenan en espiral, los pixels negros corresponden a los números primos.

Dado el hecho de que hay una infinidad de primeros, es natural buscar patrones o irregularidades en la distribución de los números primos. El problema de modelar la distribución de los números primos es un tema de investigación popular para teóricos de números.

La aparición de números primos individuales entre los números naturales es (por ahora) imprevisible, aunque hay leyes (como el teorema de los números primos y el postulado de Bertrand ) que gobiernan su distribución media.Leonhard Euler dijo:

«Los matemáticos han intentado en vano, hasta la fecha, de descubrir algún orden en la sucesión de los números primos, y tenemos razones para creer que es un misterio al que nunca penetrará la mente.»

En una clase en 1975, Don Zagier comentó:

«Hay dos hechos sobre la distribución de números primos de los que espero convenceros de manera tan abrumadora que quedarán grabados permanentemente en vuestros corazones. El primero es que, a pesar de su definición simple y su papel como los bloques constructivos de los números naturales, los números primos crecen como las malas hierbas entre los números naturales, parece que no obedezcan ningún otro ley del que la de la casualidad, y nadie puede pronosticar donde brotará el próximo. El segundo hecho es incluso más sorprendente, porque dice precisamente lo contrario: que los números primos exhiben una regularidad aturdidora, que hay leyes que gobiernan su comportamiento, y que obedecen estas leyes con precisión casi militar.»

Euler observó que la función

n 2 + n + 41

Da números primos para n ≤ 40 (pero no necesariamente para n mayor), un hecho notable que lleva a profundizar en la teoría algebraica de números , de forma más específica en los números de Heegner.

La espiral de Ulam representa todos los números naturales en una gráfica de tipo espiral. De forma sorprendente los números primos se agrupan en ciertas diagonales y no en otros.

La cantidad de números primos menores que un número dado

La función de recuento de números primos π ( n ) se define como la cantidad de números primos menores o iguales que n. Por ejemplo π (11) = 5, ya que hay cinco primeros menores o iguales que 11.

Se conocen algoritmos para calcular valores exactos de π (n) más rápidamente que contando cada primero hasta n. Valores tan grandes como π (10 20 ) se pueden calcular rápida y cuidadosamente con los ordenadores modernos.

Para valores mayores de n , más allá del alcance de los equipos modernos, el teorema de los números primos proporciona una estimación: π (n) es aproximadamente n / ln ( n ).

En otras palabras, a medida que n se hace muy grande, la probabilidad de que un número menor que n sea primero es inversamente proporcional al número de dígitos en n . Se conocen estimaciones incluso mejores; véase por ejemplo teorema de los números primos # La función de recuento de números primos en términos de la integral logarítmica.

Si n es un entero positivo mayor que 1, entonces hay siempre un número primo p con n < p <2 n (El postulado de Bertrand ).

Distancia entre números primos

Una sucesión de enteros consecutivos, ninguno de los cuales es primero, constituye un vacío entre números primos . Hay huecos entre primeros arbitrariamente largos: para cualquier número natural n mayor que 1, la sucesión.

n ! + 2, n ! + 3, …, n ! + n

es una sucesión de n – 1 naturales compuestos consecutivos, ya que

n ! + M = m · (1 · 2 · … · ( m – 1) · ( m + 1) … n + 1)

es compuesto por cualquier 2 ≤ m ≤ n . Por otra parte, los agujeros se hacen arbitrariamente pequeños en proporción a la cantidad de números primos: el cociente

( P y + 1 – p y ) / p y ,

donde p y denota el y ésimo número primo (es decir, p 1 = 2, p 2 = 3, etc.), tiende hacia cero cuando y tiende a infinito.

Aplicaciones

Durante mucho tiempo, la teoría de números en general, y el estudio de los números primos en particular, era visto como el ejemplo canónico de matemáticas puras, sin aplicaciones fuera del mismo interés de estudiar el tema.

En particular, teóricos de números como el matemático británico G. H. Hardy se Setien orgullosos de hacer un trabajo que no tenía absolutamente nada de importancia militar.

Sin embargo, esta visión quedaba desmenuzada en los años 1970, cuando se anunciaba públicamente que los números primos se podrían utilizar como la base para la creación de algoritmos de criptografía de clave pública.

Los números primos también se utilizan para construir las tablas hash y los generadores de números pseudoaleatorios .

Cuando se diseñan engranajes los números de dientes de las ruedas dentadas se procura elegir de forma que sean números primos o parejas de números primos entre ellos.

De esta manera cada diente de una de las ruedas entra en contacto el mismo número de veces con cada uno de los dientes de la otra rueda y el desgaste es uniforme.

Aritmética módulo un número primo p 

La aritmética modular es una modificación de la aritmética usual, basada en hacer todos los cálculos “módulo” un número fijado n . Todos los cálculos en aritmética modular tienen lugar en el conjunto finito

{0, 1, 2, …, n – 1}.

Calcular módulo n quiere decir que las sumas, las restas y las multiplicaciones se hacen normalmente, pero al terminar se toma como resultado el residuo de dividir entre n . Por ejemplo, sea n = 7.

Entonces, en aritmética módulo 7, la suma 3 + 5 es 1 en vez de 8, porque 8 dividido entre 7 da de residuo 1. De forma similar, 6 + 1 = 0 módulo 7, 2 – 5 = 4 módulo 7 (ya que -3 + 7 = 4) y 3 • 4 = 5 módulo 7 (12 tiene por residuo 5).

Las propiedades habituales de la suma y la multiplicación que cumplen los sistemas de números como los enteros o los racionales se siguen cumpliendo, por ejemplo

( A + b ) · c = a · c + b · c ( propiedad distributiva ).

Pero, en general, no es posible dividir en este sistema. Por ejemplo, para n = 6, la ecuación

3 · x = 2 (módulo 6),

No se puede resolver para obtener una solución x que sería el análogo a 2/3. Esto se puede ver estimando 3 • 0, …, 3 • 5 módulo 6 (no hay ningún resultado que sea 2). La característica distintiva de los números primos es la siguiente: la división es posible en aritmética modular si y sólo si n es un número primo. Para n = 7, la ecuación

3 · x = 2 (módulo 7)

Tiene una solución única, x = 3. De forma equivalente, n es un número primo si y sólo si todos los enteros m que satisfacen 2 ≤ m ≤ n – 1 son coprimos con n , es decir, su máximo común divisor es 1. utilizando la función Toti de Euler φ, n es un número primo si y sólo si φ ( n ) = n – 1.

El conjunto {0, 1, 2, …, n – 1}, con esta suma y esta multiplicación se denota Z / n Z para todo n . En términos de álgebra abstracta , es un anillo , para cualquier n , pero es un cuerpo finito si y sólo si n es un número primo.

Hay ciertos teoremas que se pueden obtener analizando Z / p Z de forma abstracta. Por ejemplo el pequeño teorema de Fermat , que establece que a p  –  a es divisible entre p para cualquier número a , se puede demostrar utilizando estos conceptos.

Una consecuencia de esto es el siguiente: si p es un número primo distinto de 2 y 5, 1/p es emplee un número decimal periódico, cuyo periodo esp – 1 o un divisor de p – 1 . 1 / p igualmente si se expresa en base q (en vez de base 10) se obtiene el mismo efecto, en caso de que p no sea un factor primo de q.

El teorema de Wilson dice que un entero p > 1 es primo si y sólo si el factorial ( p  – 1)! + 1 es divisible entre p . Recíprocamente, un entero n > 4 es compuesto si y sólo si ( n  – 1)! es divisible entre n .

Criptografía de clave pública

El algoritmo RSA se basa en la obtención de la clave pública mediante la multiplicación de dos números grandes (mayores que 10 de 100 ) que sean primeros.

La seguridad de este algoritmo radica en que no hay maneras rápidas de factorizar un número grande en sus factores primos utilizando ordenadores tradicionales . La computación cuántica podría proveer una solución a este problema de factorización.

Números primos en la naturaleza 

numeros primos naturaleza

No todas las estrellas de mar tienen 5 brazos, ni un número primo de brazos; por ejemplo, esta puede tener nueve o diez brazos.

Inevitablemente, algunos de los números que se dan en la naturaleza son primos. Hay, sin embargo, relativamente pocos ejemplos de números que aparecen en la naturaleza porque son primos.

Por ejemplo, la mayoría de las estrellas de mar tienen 5 brazos, y 5 es un número primo. Sin embargo, no hay ninguna prueba que sugiera que las estrellas de mar tienen 5 brazos porque 5 es un número primo.

De hecho, algunas estrellas de mar tienen un número de brazos diferente. La Echinaster luzonicus normalmente tiene seis, la Luidia senegalensis tiene nueve, y la Solaster endeca puede tener hasta veinte, de brazos.

El porqué la mayoría de estrellas de mar (y otros equinodermos ) tienen simetría pentagonal sigue siendo un misterio.

Un ejemplo del uso de números primos en la naturaleza es una estrategia evolutiva que usan las Cicadidae del género Magicicada. Estos insectos pasan la mayoría de sus vidas como larvas bajo tierra.

Sólo se transforman en pupas y entonces emergen de sus escondites después de 13 o 17 años, en este punto quieren, crían, y entonces mueren en unas cuantas semanas como máximo. Se cree que la razón de que los intervalos entre emergencias sea un número primo es porque esto hace muy difícil que los predadores al evolucionar se puedan especializar como predadores de Magicicadas.

Si las Magicicadas aparecieran a intervalos que no fueran números primos, por ejemplo cada 12 años, entonces los predadores que aparecieran cada 2, 3, 4, 6, o 12 años podrían asegurarse de encontrarlas.

Durante un período de 200 años, las poblaciones medias de predadores durante brotes hipotéticos de 14 y 15 años serían hasta un 2% más altas que para brotes de 13 o 17 años.

Aunque pequeño, esta ventaja parece haber sido suficiente para conducir la selección biológica a favor de un ciclo de vida de basado en un número primo para estos insectos.

Se especula de que los ceros de la función zeta de Riemann están conectados a los niveles de energía de sistemas cuánticos complejos.

Generalizaciones

El concepto de número primo se ha generalizado de diferentes maneras en diferentes ramas de las matemáticas. En general “primero” indica que es mínimo o que no se puede descomponer en componentes más pequeños.

Por ejemplo un cuerpo primero es el subcos más pequeño de un cuerpo F que contiene 0 y 1. A menudo se busca un segundo significado adicional a éste en utilizar la palabra primero , en el sentido de que un objeto se puede descomponer de forma única en sus componentes primos.

Elementos primeros en anillos 

El concepto de números primos da lugar a dos conceptos más generales que se aplican a elementos de cualquier anillo A , (una estructura algebraica donde se han definido la adición, la sustracción y la multiplicación): elementos primeros y elementos irreductibles.

Una elemento p de A se llama primero si no es una unidad (es di si no es su propio elemento inverso para la multiplicación) y se cumple la siguiente propiedad: dados x y y en A tales que p es un divisor del producto, entonces p es divisor como mínimo un factor ( x o y ).

Los elementos irreductibles son los que no se pueden escribir como producto de dos elementos del anillo que no sean unidades.

En general, esta es una condición más débil, pero para cualquier anillo factorial , como el anillo Z de los enteros, el conjunto de elementos primeros es igual al conjunto de elementos irreductibles, que para Z es {…, -11 , -7, -5, -3, -2, 2, 3, 5, 7, 11, …}.

Un ejemplo habitual son los números enteros de Gauss Z [ y ], es decir, el conjunto de números complejos de la forma a + bi con a y b en Z . Esto es un dominio de integridad , sus elementos primeros se conocen como números primos de Gauss.

No todos los primeros en Z son primos de Gauss: al anillo más grande Z [ y ], el número 2 se descompone en el producto de los dos primeros de Gauss (1 +  y ) y (1 –  y ).

Los números primos racionales (es decir los elementos primeros de Z ) de la forma 4 k  + 3 son primos de Gauss, mientras que los primeros racionales de la forma 4 k  + 1 no lo son. Los primeros de Gauss se pueden utilizar para demostrar la ley de reciprocidad cuadrática , mientras que los primeros de Eisenstein tienen un papel similar en la ley de reciprocidad cúbica .

Ideales primeros 

En teoría de anillos , el concepto de número se sustituye por el de ideal . Los ideales primeros son los que si el producto de dos elementos xy pertenece al ideal, entonces o bien x pertenece al ideal o bien ypertenece al ideal (o ambos), esto generaliza los elementos primeros en el sentido de que el ideal principal generado por un elemento primero es un ideal primero, son una herramienta importante y son objeto de estudio en álgebra conmutativa, teoría algebraica de números y geometría algebraica.

Los ideales primeros del anillo de los enteros son los ideales (0), (2), (3), (5), (7), (11), … El teorema fundamental de la aritmética se generaliza el teorema de Lasker -Noether que expresa cualquier ideal en un anillo conmutativo de Noether como la intersección de ideales primos , que es la generalización adecuada de las potencias de los números primos.

Los ideales primeros son los puntos de los objetos álgebra-geométricos , a través del concepto de espectro de un anillo. La geometría aritmética también se beneficia de este concepto, y hay muchos paralelismos entre la teoría de números y la geometría.

Por ejemplo, la descomposición en factores o ramificación de ideales primeros cuando se someten a una extensión de un cuerpo , es un problema básico en teoría algebraica de números que conlleva cierta similitud con la ramificación en geometría.

En el ejemplo de los enteros de Gauss, el (2) se ramifica en potencia de un primer (ya que 1 + y y 1 – ygeneran el mismo ideal primero), los ideales primos de la forma 4 k + 3 son inertes (mantienen su primalidad) y los de la forma 4 k + 1 pasan a ser producto de dos ideales primos distintos.

Teoría de grupos

En teoría de grupos , los grupos esporádicos se consideran el equivalente de los números primos. Se demuestra que un grupo simple finito puede ser: cíclico , alternado , uno de los 16 tipos de grupos simples finitos de Lie o uno de los 26 grupos esporádicos .

Primeros en teoría de la evaluación 

En teoría algebraica de números aparece otra generalización. Dado un cuerpo , Se toman las evaluaciones sobre , Determinadas funciones de en .

Cada una de estas evaluaciones genera unatopología sobre . Se dice que dos evaluaciones son equivalentes si generan la misma topología. Un primero de  es una clase de equivalencia de evaluaciones. Con esta definición, los primeros del cuerpo  los números racionales quedan representados por la función valor absoluto así como para las evaluaciones sobre  por cada número primo p.

Nudos primeros 

trefoilFigure-8 knotCinquefoilNudo primario 5-2
Algunos nudos primeros

En teoría de nudos , un nudo primero es un nudo no trivial que no se puede descomponer en dos nudos más pequeños. De forma más precisa, se trata de un nudo que no se puede escribir como suma conexa de dos nudos no triviales.

El año 1949 Horst Schubert demostró un teorema de factorización análogo al teorema fundamental de la aritmética, que asegura que cada nudo se puede obtener de forma única como suma conexa de nudos primeros.

Por este motivo, los nudos primeros tienen un papel fundamental en la teoría de nudos: una clasificación de los nudos ha sido el tema central de la teoría desde el siglo XIX.

Números primos en el arte y la literatura

Los números primos han influido en numerosos artistas y escritores. El compositor francés Olivier Messiaen se valió de ellos para crear música no métrica. En obras tales como La Natividad du Seigneur (1935) o Cuatro études de rythmé emplea simultáneamente motivos cuya duración es un número primo para crear ritmos impredecibles.

Según Messiaen, esta forma de componer fue «inspirada por los movimientos de la naturaleza, movimientos de duraciones libres y desiguales».

En su novela de ciencia ficción Contact , posteriormente adaptada al cine , Carl Sagan sugiere que los números primos se podrían emplear para comunicarse con inteligencias extraterrestres, una idea que había desarrollado de manera informal con el astrónomo norte -América Frank Drake el 1975.

El curioso incidente del perro a medianoche , que describe en primera persona la vida de un joven autista muy dotado en matemáticas y cálculo mental , usa sólo los números primos para numerar los capítulos.

En la novela PopCo de Scarlett Thomas , la abuela de Alice Butler trabaja en la demostración de la hipótesis de Riemann . El libro ilustra una tabla de los mil primeros números primos.

La Solitudine dei numeri primi , novela escrita por Paolo Giordano , ganó el premio Strega en 2008.

También hay muchas películas que reflejan la fascinación popular hacia los misterios de los números primos y la criptografía, por ejemplo, Cube , Sneakers , El amor tiene dos caras y Una mente maravillosa.

Esta última se basa en la biografía del matemático y premio Nobel John Forbes Nash , escrita por Sylvia Nasar

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *