Número primo
Definición
Un número primo (o primo ) es un número natural mayor que 1 que no se puede formar al multiplicar dos números naturales más pequeños. Un número natural mayor que 1 que no es primo se llama número compuesto. Por ejemplo, 5 es primo porque las únicas formas de escribirlo como un producto, 1 × 5 o 5 × 1 , involucran a 5. Sin embargo, 6 es compuesto porque es el producto de dos números ( 2 × 3 ) que son ambos menores que 6. Los primos son centrales en la teoría de números debido al teorema fundamental de la aritmética: cada número natural mayor que 1 es un primo en sí mismo o puede ser factorizado como un producto de primos que es único hasta su orden.
La propiedad de ser primo se llama primalidad. Un método simple pero lento para verificar la primalidad de un número dado , llamado división de prueba, prueba si es un múltiplo de cualquier número entero entre 2 y . Los algoritmos más rápidos incluyen la prueba de primalidad Miller-Rabin, que es rápida pero tiene una pequeña posibilidad de error, y la prueba de primalidad AKS, que siempre produce la respuesta correcta en tiempo polinomial pero es demasiado lenta para ser práctica. Métodos particularmente rápidos están disponibles para números de formularios especiales, como los números de Mersenne. A partir de enero de 2018, el número primo más grande conocido tiene 23,249,425 dígitos decimales.
Hay infinitos números primos, como lo demostró Euclides alrededor del año 300 aC Ninguna fórmula simple conocida separa los números primos de los números compuestos. Sin embargo, la distribución de números primos dentro de los números naturales en el tamaño grande se puede modelar estadísticamente. El primer resultado en esa dirección es el teorema del número primo, probado a fines del siglo XIX, que dice que la probabilidad de que un número elegido al azar sea primo es inversamente proporcional a su número de dígitos, es decir, a su logaritmo.
Varias preguntas históricas con respecto a los números primos aún no están resueltas. Estos incluyen la conjetura de Goldbach, que cada entero par mayor que 2 puede expresarse como la suma de dos números primos, y la conjetura principal doble, que hay infinitos pares de números primos que tienen un solo número par entre ellos. Tales preguntas estimularon el desarrollo de varias ramas de la teoría de números, centrándose en aspectos analíticos o algebraicos de los números. Primes se utiliza en varias rutinas en tecnología de la información, como la criptografía de clave pública, que se basa en la dificultad de factorizar grandes números en sus factores primos. En el álgebra abstracta, los objetos que se comportan de forma generalizada como los números primos incluyen elementos primos e ideales primarios.
Definición y ejemplos
Un número natural (1, 2, 3, 4, 5, 6, etc.) se denomina número primo (o primo ) si es mayor que 1 y no puede escribirse como un producto de dos números naturales que son más pequeños. que eso. Los números mayores que 1 que no son primos se llaman números compuestos. En otras palabras, es primordial si los elementos no se pueden dividir en grupos más pequeños de igual tamaño de más de un elemento, o si no es posible organizar los puntos en una cuadrícula rectangular que tiene más de un punto de ancho y más de un punto de altura . Por ejemplo, entre los números del 1 al 6, los números 2, 3 y 5 son los números primos, ya que no hay otros números que los dividan equitativamente (sin un resto). 1 no es primo, ya que está específicamente excluido en la definición. 4 = 2 × 2 y 6 = 2 × 3 son ambos compuestos.
Los divisores de un número natural son los números que se dividen de manera uniforme. Cada número natural tiene ambos 1 y sí mismo como un divisor. Si tiene otro divisor, no puede ser primo. Esta idea conduce a una definición diferente pero equivalente de los números primos: son los números con exactamente dos divisores positivos, 1 y el número en sí mismo. Otra forma de decir lo mismo es que un número es primo si es mayor que uno y si ninguno de los números se divide equitativamente.
Los primeros 25 números primos (todos los números primos menores de 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, 97 ( secuencia A000040 en el OEIS).
Ningún número par mayor a 2 es primo porque cualquier número puede ser expresado como el producto . Por lo tanto, cada número primo distinto de 2 es un número impar, y se llama primo impar . Del mismo modo, cuando se escribe en el sistema decimal habitual, todos los números primos mayores que 5 terminan en 1, 3, 7 o 9. Los números que terminan con otros dígitos son todos compuestos: números decimales que terminan en 0, 2, 4, 6 , o 8 son pares, y los números decimales que terminan en 0 o 5 son divisibles por 5.
El conjunto de todos los números primos se denota a veces por (una negrita mayúscula P) o por (una pizarra negrita mayúscula P).
Historia
El Papiro Matemático Rhind, de alrededor de 1550 aC, tiene expansiones de fracciones egipcias de diferentes formas para números primos y compuestos. Sin embargo, los primeros registros que sobreviven del estudio explícito de los números primos provienen de las matemáticas griegas antiguas. Los Elementos de Euclides (alrededor del año 300 aC) demuestran la infinitud de los primos y el teorema fundamental de la aritmética, y muestran cómo construir un número perfecto a partir de un primo de Mersenne. Otra invención griega, el Tamiz de Eratóstenes, todavía se usa para construir listas de primos. Alrededor del año 1000 DC, el matemático islámico Alhazen encontró el teorema de Wilson, caracterizando los números primos como los números que dividen equitativamente . Alhazen también conjeturó que todos los números incluso perfectos provienen de la construcción de Euclides usando primos de Mersenne, pero no pudo probarlo. Otro matemático islámico, Ibn al-Banna 'al-Marrakushi, observó que se puede acelerar el tamiz de Eratóstenes probando solo los divisores hasta la raíz cuadrada del número más grande que se probará. Fibonacci trajo las innovaciones de las matemáticas islámicas a Europa. Su libro Liber Abaci (1202) fue el primero en describir la división de prueba para probar la primalidad, nuevamente utilizando divisores solo hasta la raíz cuadrada.
En 1640, Pierre de Fermat declaró (sin pruebas) el pequeño teorema de Fermat (más tarde probado por Leibniz y Euler). Fermat también investigó la primalidad de los números de Fermat , y Marin Mersenne estudió los primos de Mersenne, los números primos de la forma consigo mismo un primo. Christian Goldbach formuló la conjetura de Goldbach, que cada número par es la suma de dos primos, en una carta de 1742 a Euler. Euler probó la conjetura de Alhazen (ahora el teorema de Euclid-Euler) de que todos los números perfectos incluso pueden construirse a partir de los primos de Mersenne. Introdujo métodos del análisis matemático a esta área en sus pruebas de la infinitud de los primos y la divergencia de la suma de los recíprocos de los primos . A comienzos del siglo XIX, Legendre y Gauss conjeturaron que tiende a infinito, el número de primos hasta es asintótico a , donde está el logaritmo natural de . Las ideas de Riemann en su artículo de 1859 sobre la función zeta bosquejó un esquema para probar esto. Aunque la hipótesis estrechamente relacionada de Riemann no ha sido probada, el bosquejo de Riemann fue completado en 1896 por Hadamard y de la Vallée Poussin, y el resultado ahora se conoce como el teorema del número primo. Otro resultado importante del siglo XIX fue el teorema de Dirichlet sobre progresiones aritméticas, que las progresiones aritméticas contienen infinitos primos.
Muchos matemáticos han trabajado en pruebas de primalidad para números más grandes que aquellos en los que la división de prueba es aplicable de manera práctica. Los métodos que están restringidos a formas numéricas específicas incluyen la prueba de Pépin para los números de Fermat (1877), el teorema de Proth (alrededor de 1878), la prueba de primalidad de Lucas-Lehmer (originada en 1856) y la prueba de primalidad de Lucas generalizada. Desde 1951, todos los números primos conocidos más grandes se han encontrado usando estas pruebas en computadoras. La búsqueda de primos cada vez más grandes ha generado interés fuera de los círculos matemáticos, a través de la Gran búsqueda de Internet Mersenne Prime y otros proyectos de computación distribuida. La idea de que los números primos tenían pocas aplicaciones fuera de las matemáticas puras se hizo añicos en la década de 1970 cuando se inventaron la criptografía de clave pública y el criptosistema RSA, utilizando como base los números primos. La mayor importancia práctica de la prueba y factorización computarizada de la primalidad condujo al desarrollo de métodos mejorados capaces de manejar un gran número de formas no restringidas. La teoría matemática de los números primos también avanzó con el teorema de Green-Tao (2004) sobre las largas progresiones aritméticas de los números primos, y la prueba de Yitang Zhang de 2013 de que existen infinitas brechas primarias de tamaño limitado.
Primalidad de uno
La mayoría de los primeros griegos ni siquiera consideraban 1 como un número, por lo que no podían considerar su primalidad. Algunos matemáticos de esta época también consideraron que los números primos eran una subdivisión de los números impares, por lo que tampoco consideraron que 2 era el primo. Sin embargo, Euclides y la mayoría de los otros matemáticos griegos consideraron 2 como primos. Los matemáticos medievales islámicos siguieron en gran medida a los griegos al ver 1 como no ser un número. En la Edad Media y el Renacimiento, los matemáticos comenzaron a tratar a 1 como un número, y algunos de ellos lo incluyeron como el primer número primo. A mediados del siglo XVIII, Christian Goldbach enumeró 1 como primo en su correspondencia con Leonhard Euler; sin embargo, el propio Euler no consideró que 1 fuera el primero. En el siglo XIX, muchos matemáticos todavía consideraban que 1 era el principal,
Si se cambiara la definición de un número primo para llamar a 1 un primo, muchas afirmaciones que involucren números primos necesitarían ser reformuladas de una manera más incómoda. Por ejemplo, el teorema fundamental de la aritmética tendría que reformularse en términos de factorizaciones en primos superiores a 1, ya que cada número tendría múltiples factorizaciones con diferentes números de copias de 1. De manera similar, el tamiz de Eratóstenes no funcionaría correctamente si manejó 1 como primo, porque eliminaría todos los múltiplos de 1 (es decir, todos los otros números) y solo daría el número 1. Algunas otras propiedades más técnicas de los números primos tampoco son válidas para el número 1: por ejemplo, las fórmulas para la función totient de Euler o para la función suma de divisores son diferentes para los números primos que para 1. A principios del siglo XX,
Propiedades elementales
Factorización única
Escribir un número como producto de números primos se llama factorización prima del número. Por ejemplo:
Los términos en el producto se llaman factores primos . El mismo factor primo puede ocurrir más de una vez; este ejemplo tiene dos copias del factor principal . Cuando un primo ocurre varias veces, la exponenciación se puede usar para agrupar varias copias del mismo número primo: por ejemplo, en la segunda forma de escribir el producto anterior, denota el cuadrado o el segundo poder de .
La importancia central de los números primos para la teoría de números y las matemáticas en general proviene del teorema fundamental de la aritmética . Este teorema establece que cada entero mayor que 1 puede escribirse como un producto de uno o más números primos. Más enérgicamente, este producto es único en el sentido de que dos factorizaciones principales del mismo número tendrán los mismos números de copias de los mismos números primos, aunque su orden puede diferir. Entonces, aunque hay muchas maneras diferentes de encontrar una factorización usando un algoritmo de factorización de enteros, todas deben producir el mismo resultado. Por lo tanto, los bonos pueden considerarse los "bloques de construcción básicos" de los números naturales.
Algunas pruebas de la singularidad de las factorizaciones primarias se basan en el lema de Euclides: si es un número primo y divide un producto de enteros y , a continuación, divide o divide (o ambos). Por el contrario, si un número tiene la propiedad de que cuando divide un producto siempre divide al menos un factor del producto, entonces debe ser primo.
Infinito
Hay infinitos números primos. Otra forma de decir esto es que la secuencia
- 2, 3, 5, 7, 11, 13, ...
de números primos nunca termina. Esta declaración se conoce como el teorema de Euclides en honor del matemático griego antiguo Euclides, ya que la primera prueba conocida de esta afirmación se le atribuye. Se conocen muchas más pruebas de la infinitud de primos, incluida una prueba analítica de Euler, la prueba de Goldbach basada en números de Fermat, la prueba de Furstenberg usando topología general y la elegante prueba de Kummer.
La demostración de Euclides muestra que cada lista finita de primos está incompleta. La idea clave es multiplicar juntos los primos en cualquier lista dada y agregar . Si la lista consta de los números primos , esto le da el número
Por el teorema fundamental, tiene una factorización prima
con uno o más factores primos. es uniformemente divisible por cada uno de estos factores, pero tiene un resto de uno cuando se divide por cualquiera de los números primos en la lista dada, por lo que ninguno de los factores primos de puede estar en la lista dada. Como no hay una lista finita de todos los primos, debe haber infinitos primos.
Los números formados al agregar uno a los productos de los números primos más pequeños se llaman números de Euclides. Los primeros cinco de ellos son primos, pero el sexto,
es un número compuesto
Fórmulas para primos
No se conoce una fórmula eficiente para los primos. Por ejemplo, no existe un polinomio no constante, incluso en varias variables, que solo toma valores primos. Sin embargo, existen numerosas expresiones que codifican todos los primos, o solo primos. Una posible fórmula se basa en el teorema de Wilson y genera el número 2 muchas veces y todos los demás primos exactamente una vez. También hay un conjunto de ecuaciones diofánticas en nueve variables y un parámetro con la siguiente propiedad: el parámetro es primordial si y solo si el sistema resultante de ecuaciones tiene una solución sobre los números naturales. Esto se puede usar para obtener una fórmula única con la propiedad de que todos sus valores positivos son primos.
Otros ejemplos de fórmulas generadoras de primos provienen del teorema de Mills y un teorema de Wright. Estos afirman que hay constantes reales y que
son primos para cualquier número natural en la primera fórmula, y cualquier número de exponentes en la segunda fórmula. Aquí representa la función de piso, el número entero más grande menor o igual al número en cuestión. Sin embargo, estos no son útiles para generar primos, ya que los primos se deben generar primero para calcular los valores de o .
Preguntas abiertas
Se han planteado muchas conjeturas que giran en torno a los primos. A menudo tienen una formulación elemental, muchas de estas conjeturas han resistido pruebas durante décadas: los cuatro problemas de Landau desde 1912 aún no están resueltos. Una de ellas es la conjetura de Goldbach, que afirma que cada entero par mayor a 2 se puede escribir como una suma de dos primos. A partir de 2014, esta conjetura se ha verificado para todos los números hasta . Se han comprobado afirmaciones más débiles que, por ejemplo, el teorema de Vinogradov dice que cada entero impar suficientemente grande se puede escribir como una suma de tres primos. El teorema de Chen dice que cada número par suficientemente grande se puede expresar como la suma de un primo y una semiprima, el producto de dos primos. Además, cualquier número par puede escribirse como la suma de seis números primos. La rama de la teoría de números que estudia tales cuestiones se llama teoría aditiva de números.
Otro tipo de problema se refiere a las brechas principales, las diferencias entre los primos consecutivos. La existencia de brechas primarias arbitrariamente grandes se puede ver al observar que la secuencia consiste en números compuestos, para cualquier número natural . Sin embargo, las brechas principales grandes ocurren mucho antes de lo que muestra este argumento. Por ejemplo, el primer espacio de cebado de longitud 8 está entre los números primos 89 y 97, mucho más pequeño que . Se conjetura que hay infinitos primos gemelos infinitos, pares de primos con diferencia 2; esta es la conjetura principal doble. La conjetura de Polignac afirma de manera más general que para cada entero positivo , hay infinitos pares de primos consecutivos que difieren por La conjetura de Andria, la conjetura de Brocard, la conjetura de Legendre y la conjetura de Oppermann sugieren que las brechas más grandes entre primos y a deben ser como máximo aproximadamente , un resultado que se sabe que sigue de la hipótesis de Riemann, mientras que la conjetura mucho más fuerte de Cramér establece la mayor tamaño de la brecha en . Los huecos primarios se pueden generalizar a primos -tuplos, patrones en las diferencias entre más de dos números primos. Su infinitud y densidad son el sujeto de la primera conjetura de Hardy-Littlewood, que puede ser motivada por la heurística de que los números primos se comportan de manera similar a una secuencia aleatoria de números con densidad dada por el teorema del número primo.
Propiedades analíticas
La teoría numérica analítica estudia la teoría numérica a través de la lente de funciones continuas, límites, series infinitas y las matemáticas relacionadas de infinito e infinitesimal.
Esta área de estudio comenzó con Leonhard Euler y su primer gran resultado, la solución al problema de Basilea. El problema requería el valor de la suma infinita que hoy se puede reconocer como el valor de la función zeta de Riemann. Esta función está estrechamente relacionada con los números primos y con uno de los problemas sin resolver más importantes en matemáticas, la hipótesis de Riemann. Euler mostró eso . El recíproco de este número ,, es la probabilidad límite de que dos números aleatorios seleccionados uniformemente de un rango grande sean relativamente primos (no tienen factores en común).
La distribución de números primos en el grande, como la pregunta de cuántos primos son más pequeños que un gran umbral dado, se describe mediante el teorema del número primo, pero no se conoce ninguna fórmula eficiente para el primer primo. El teorema de Dirichlet sobre las progresiones aritméticas, en su forma básica, afirma que los polinomios lineales
con enteros relativamente primos y toma infinitamente muchos valores primos. Las formas más fuertes del teorema establecen que la suma de los recíprocos de estos valores principales diverge, y que diferentes polinomios lineales con el mismo tienen aproximadamente las mismas proporciones de primos. Aunque se han formulado conjeturas sobre las proporciones de primos en polinomios de mayor grado, siguen sin probarse, y se desconoce si existe un polinomio cuadrático que (para argumentos enteros) sea primo infinitamente frecuente.
Prueba analítica del teorema de Euclides
La prueba de Euler de que hay infinitos primos considera las sumas de recíprocos de primos,
Euler demostró que, para cualquier número real arbitrario , existe un primo para el cual esta suma es mayor que . Esto muestra que hay infinitos primos, porque si hubiera infinitos primos, la suma alcanzaría su valor máximo en la prima mayor en lugar de crecer cada uno . La tasa de crecimiento de esta suma se describe más precisamente por el segundo teorema de Mertens. Para comparación, la suma
no crece hasta el infinito como va al infinito (ver el problema de Basilea). En este sentido, los números primos ocurren con más frecuencia que los cuadrados de los números naturales, aunque ambos conjuntos son infinitos. El teorema de Run establece que la suma de los recíprocos de primos gemelos,
es finito Debido al teorema de Brun, no es posible usar el método de Euler para resolver la conjetura de doble gemelo, que existen infinitos primos gemelos.
Número de primos por debajo de un límite dado
La función de recuento principal se define como la cantidad de primos no mayor que . Por ejemplo, dado que hay cinco números primos menores que o iguales a 11. Los métodos como el algoritmo de Meissel-Lehmer pueden calcular valores exactos de más rápido de lo que sería posible hacer una lista de cada primo . El teorema del número principal dice que es asintótico a , que se denota como
y significa que la proporción de a la fracción de la mano derecha se acerca a 1 a medida que crece hasta el infinito. Esto implica que la probabilidad de que un número elegido aleatoriamente menor que el primo sea (aproximadamente) inversamente proporcional al número de dígitos en . También implica que el primer número es proporcional ay, por lo tanto, que el tamaño promedio de un espacio principal es proporcional a . Una estimación más precisa para está dada por la integral logarítmica de desplazamiento
Progresiones aritméticas
Una progresión aritmética es una secuencia finita o infinita de números tal que los números consecutivos en la secuencia tienen la misma diferencia. Esta diferencia se llama el módulo de la progresión. Por ejemplo,
- 3, 12, 21, 30, 39, ...,
es una progresión aritmética infinita con módulo 9. En una progresión aritmética, todos los números tienen el mismo resto cuando se divide por el módulo; en este ejemplo, el resto es 3. Debido a que tanto el módulo 9 como el resto 3 son múltiplos de 3, también lo es cada elemento de la secuencia. Por lo tanto, esta progresión contiene solo un número primo, 3 en sí mismo. En general, la progresión infinita
puede tener más de un primo solo cuando el resto y el módulo son relativamente primos. Si son relativamente primos, el teorema de Dirichlet sobre las progresiones aritméticas afirma que la progresión contiene infinitos primos.
El teorema de Green-Tao muestra que hay progresiones aritméticas finitas arbitrariamente largas que consisten únicamente en primos.
Valores principales de polinomios cuadráticos
Euler notó que la función
produce números primos para , aunque los números compuestos aparecen entre sus valores posteriores. La búsqueda de una explicación para este fenómeno llevó a la teoría de números algebraicos profundos de los números de Heegner y al problema del número de clase. La conjetura de Hardy-Littlewood Fpredicts la densidad de primos entre los valores de polinomios cuadráticos con coeficientes enteros en términos de la integral logarítmica y los coeficientes polinomiales. No se ha demostrado que ningún polinomio cuadrático tome infinitamente muchos valores primos.
La espiral de Ulam organiza los números naturales en una cuadrícula bidimensional, en espiral en cuadrados concéntricos que rodean el origen con los números primos resaltados. Visualmente, los primos parecen agruparse en ciertas diagonales y no en otras, lo que sugiere que algunos polinomios cuadráticos toman valores primos con más frecuencia que otros.
Función Zeta y la hipótesis de Riemann
Una de las preguntas sin resolver más famosas en matemáticas, que data de 1859, y uno de los problemas del Premio Milenio, es la hipótesis de Riemann, que pregunta dónde se encuentran los ceros de la función zeta de Riemann . Esta función es una función analítica de los números complejos. Para números complejos con una parte real mayor que uno, es igual a una suma infinita sobre todos los enteros, y un producto infinito sobre los números primos,
Esta igualdad entre una suma y un producto, descubierta por Euler, se denomina producto de Euler. El producto Euler puede derivarse del teorema fundamental de la aritmética y muestra la estrecha conexión entre la función zeta y los números primos. Esto lleva a otra prueba de que hay infinitos primos: si solo hubiera un número finito de ellos, entonces la igualdad del producto suma también sería válida en , pero la suma divergiría (es la serie armónica ) mientras que el producto sería finito, una contradicción
La hipótesis de Riemann establece que los ceros de la función zeta son números negativos o números complejos con una parte real igual a 1/2. La prueba original del teorema del número primo se basó en una forma débil de esta hipótesis, que no hay ceros con una parte real igual a 1, aunque se han encontrado otras pruebas más elementales. La función de recuento principal se puede expresar mediante la fórmula explícita de Riemann como una suma en la que cada término proviene de uno de los ceros de la función zeta; el término principal de esta suma es la integral logarítmica, y los términos restantes hacen que la suma fluctúe arriba y abajo del término principal. En este sentido, los ceros controlan con qué regularidad se distribuyen los números primos. Si la hipótesis de Riemann es verdadera, estas fluctuaciones serán pequeñas, para intervalos cerca de un número ).
Álgebra abstracta
Aritmética modular y campos finitos
La aritmética modular modifica la aritmética habitual usando solo los números , para un número natural llamado módulo. Cualquier otro número natural se puede mapear en este sistema reemplazándolo por el resto después de la división por . Las sumas, diferencias y productos modulares se calculan realizando el mismo reemplazo por el resto en el resultado de la suma, diferencia o producto habitual de los enteros. La igualdad de los enteros corresponde a la congruencia en la aritmética modular: y son congruentes ( mod escrito ) cuando tienen el mismo resto después de la división por . Sin embargo, en este sistema de números, la división por todos los números distintos de cero es posible si y solo si el módulo es primo. Por ejemplo, con el número primo como módulo, división por es posible: porque borrar los denominadores al multiplicar ambos lados da la fórmula válida . Sin embargo, con el módulo compuesto , la división por es imposible. No hay una solución válida para : borrar denominadores multiplicando por causas el lado izquierdo para convertirse mientras que el lado derecho se convierte en o . En la terminología del álgebra abstracta, la capacidad de realizar división significa que el módulo aritmético modular un número primo forma un campo o, más específicamente, un campo finito, mientras que otros módulos solo dan un anillo pero no un campo.
Varios teoremas sobre primos se pueden formular usando aritmética modular. Por ejemplo, el pequeño teorema de Fermat establece que if (mod ), then (mod ). Sumar esto sobre todas las elecciones da la ecuación
válido siempre que sea primo La conjetura de Giuga dice que esta ecuación es también una condición suficiente para ser primo. El teorema de Wilson dice que un entero es primordial si y solo si el factorial es congruente con el mod . Para un número compuesto, esto no puede mantenerse, ya que uno de sus factores divide tanto n como , y así es imposible.
p -adic números
El orden -adic de un entero es el número de copias de en la factorización prima de . El mismo concepto se puede extender de números enteros a números racionales definiendo el orden -adic de una fracción a ser . El valor absoluto -adic de cualquier número racional se define entonces como . Multiplicar un número entero por su valor absoluto -adic cancela los factores de en su factorización, dejando solo los otros números primos. Así como la distancia entre dos números reales puede medirse por el valor absoluto de su distancia, la distancia entre dos números racionales puede medirse por su distancia -adica,
-adicional valor absoluto de su diferencia. Para esta definición de distancia, dos números están muy juntos (tienen una pequeña distancia) cuando su diferencia es divisible por una gran potencia de . De la misma manera que los números reales se pueden formar a partir de los números racionales y sus distancias, agregando valores límite adicionales para formar un campo completo, los números racionales con la distancia -adica se pueden extender a un campo completo diferente, el -adic números.
-adicional valor absoluto de su diferencia. Para esta definición de distancia, dos números están muy juntos (tienen una pequeña distancia) cuando su diferencia es divisible por una gran potencia de . De la misma manera que los números reales se pueden formar a partir de los números racionales y sus distancias, agregando valores límite adicionales para formar un campo completo, los números racionales con la distancia -adica se pueden extender a un campo completo diferente, el -adic números.
Esta imagen de un orden, valor absoluto y campo completo derivado de ellos se puede generalizar a campos de números algebraicos y sus valoraciones (ciertas asignaciones del grupo multiplicativo del campo a un grupo aditivo totalmente ordenado, también llamadas órdenes), valores absolutos ( ciertas asignaciones multiplicativas del campo a los números reales, también llamadas normas), y lugares (extensiones para completar campos en los que el campo dado es un conjunto denso, también llamado complementos). La extensión de los números racionales a los números reales, por ejemplo, es un lugar en el que la distancia entre los números es el valor absoluto habitual de su diferencia. El mapeo correspondiente a un grupo aditivo sería el logaritmo del valor absoluto, aunque esto no cumple todos los requisitos de una valoración. De acuerdo con el teorema de Ostrowski, -los números ávaros, con sus órdenes y valores absolutos, son las únicas valoraciones, valores absolutos y lugares en los números racionales. El principio local-global permite que ciertos problemas sobre los números racionales se resuelvan juntando soluciones de cada uno de sus lugares, nuevamente subrayando la importancia de los primos para la teoría de números.
Elementos principales en anillos
Un anillo conmutativo es una estructura algebraica donde se definen la suma, la resta y la multiplicación. Los enteros son un anillo, y los números primos en los enteros se han generalizado a anillos en dos formas diferentes, elementos primos y elementos irreducibles . Un elemento de un anillo se denomina primo si es distinto de cero, no tiene inversa multiplicativa (es decir, no es una unidad) y cumple el siguiente requisito: siempre que divide el producto de dos elementos de , también divide al menos uno de o . Un elemento es irreductible si no es ni una unidad ni el producto de otros dos elementos no-unidad. En el anillo de los enteros, los elementos primos e irreducibles forman el mismo conjunto,
En un anillo arbitrario, todos los elementos primos son irreductibles. Lo contrario no se cumple en general, pero sí para los dominios únicos de factorización.
El teorema fundamental de la aritmética continúa siendo válido (por definición) en dominios únicos de factorización. Un ejemplo de un dominio de este tipo es los enteros de Gauss , el anillo de los números complejos de la forma en que representa la unidad imaginaria y y son enteros arbitrarios. Sus elementos principales se conocen como primos Gaussianos. No todos los números que son primos entre los enteros permanecen primos en los enteros Gaussianos; por ejemplo, el número 2 se puede escribir como un producto de los dos números primos gaussianos y . Los primos racionales (los elementos primos en los enteros) congruentes con 3 mod 4 son primos gaussianos, pero los primos racionales congruentes con 1 mod 4 no lo son. Esto es una consecuencia del teorema de Fermat sobre sumas de dos cuadrados, que establece que un primer impar es expresable como la suma de dos cuadrados, y por lo tanto factorizable como , exactamente cuando es 1 mod 4.
![\ mathbb {Z} [i]](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffa94e9e2e6d9e5e5373d5fafb954b902743fde)
Prime ideales
No todos los anillos son un dominio único de factorización. Por ejemplo, en el anillo de números (para enteros y ) el número tiene dos factorizaciones , donde ninguno de los cuatro factores se puede reducir más, por lo que no tiene una factorización única. Para ampliar la factorización única a una clase de anillos más grande, la noción de un número puede reemplazarse con la de un ideal, un subconjunto de los elementos de un anillo que contiene todas las sumas de pares de sus elementos y todos los productos de su elementos con elementos de anillo. Prime ideales, que generalizan elementos primos en el sentido de que el ideal principal generado por un elemento principal es un ideal primordial, son una herramienta importante y un objeto de estudio en álgebra conmutativa, teoría de números algebraicos y geometría algebraica. Los ideales primarios del anillo de los enteros son los ideales (0), (2), (3), (5), (7), (11), ... El teorema fundamental de la aritmética se generaliza al teorema de Lasker-Noether, que expresa cada ideal en un anillo conmutativo noetheriano como una intersección de ideales primarios, que son las generalizaciones apropiadas de los poderes primos.
El espectro de un anillo es un espacio geométrico cuyos puntos son los ideales primordiales del anillo. La geometría aritmética también se beneficia de esta noción, y existen muchos conceptos tanto en geometría como en teoría de números. Por ejemplo, la factorización o ramificación de ideales primordiales cuando se eleva a un campo de extensión, un problema básico de la teoría de números algebraicos, guarda cierta semejanza con la ramificación en geometría. Estos conceptos incluso pueden ayudar con preguntas de teoría de números exclusivamente relacionadas con enteros. Por ejemplo, ideales primordiales en el anillo de enteros de campos numéricos cuadráticos se pueden usar para probar la reciprocidad cuadrática, una afirmación que se refiere a la existencia de números enteros enteros de módulo de raíz cuadrada. Los primeros intentos de probar el último teorema de Fermat llevaron a la introducción de Kummer de números primos regulares, números primos enteros conectados con la falla de la factorización única en los enteros ciclotónicos. La cuestión de cuántas número entero factor en un producto de múltiples ideales primos en un campo de números algebraicos números primos se dirige por el teorema de densidad de Chebotarev, que (cuando se aplica a los números enteros ciclotómicos) tiene el teorema de Dirichlet sobre primos en progresiones aritméticas como un caso especial.
Teoría de grupo
En la teoría de los grupos finitos, los teoremas de Sylow implican que, si un poder de un número primo divide el orden de un grupo, entonces tiene un subgrupo de orden . Según el teorema de Lagrange, cualquier grupo de primer orden es un grupo cíclico, y según el teorema de Burnside, cualquier grupo cuyo orden sea divisible por solo dos primos es solvente.
Métodos computacionales
Durante mucho tiempo, la teoría de números en general, y el estudio de los números primos en particular, se consideraba el ejemplo canónico de las matemáticas puras, sin aplicaciones fuera de las matemáticas, con la excepción del uso de dientes de engranajes numerados para distribuir el desgaste uniformemente. En particular, teóricos de números como el matemático británico GH Hardy se enorgullecían de hacer un trabajo que no tenía absolutamente ningún significado militar.
Esta visión de la pureza de la teoría de los números se hizo añicos en la década de 1970, cuando se anunció públicamente que los números primos podrían usarse como base para la creación de algoritmos de criptografía de clave pública. Estas aplicaciones han llevado a un estudio significativo de algoritmos para calcular con números primos, y en particular de pruebas de primalidad, métodos para determinar si un número dado es primo. La rutina de prueba de primalidad más básica, la división de prueba, es demasiado lenta para ser útil para números grandes. Un grupo de pruebas modernas de primalidad es aplicable a números arbitrarios, mientras que las pruebas más eficientes están disponibles para números de tipos especiales. La mayoría de las pruebas de primalidad solo dicen si su argumento es primordial o no. Las rutinas que también proporcionan un factor principal de argumentos compuestos (o todos sus factores primos) se llaman algoritmos de factorización.
División de prueba
El método más básico para verificar la primalidad de un entero dado se llama división de prueba . Este método se divide por cada número entero desde 2 hasta la raíz cuadrada de . Cualquier entero tal que se divide uniformemente establece como compuesto; de lo contrario, es primo. Números enteros mayores que la raíz cuadrada no necesitan ser revisados, ya que, cada vez , uno de los dos factores y es menor o igual a la raíz cuadrada de . Otra optimización es verificar solo los primos como factores en este rango. Por ejemplo, para verificar si 37 es primo, este método lo divide por los números primos en el rango de 2 a √ 37, que son 2, 3 y 5. Cada división produce un resto distinto de cero, por lo que 37 es de hecho primo.
Aunque este método es simple de describir, no es práctico probar la primalidad de enteros grandes, ya que la cantidad de pruebas que realiza crece exponencialmente en función del número de dígitos de estos enteros. Sin embargo, aún se usa la división de prueba, con un límite más pequeño que la raíz cuadrada en el tamaño del divisor, para descubrir rápidamente números compuestos con pequeños factores, antes de utilizar métodos más complicados en los números que pasan este filtro.
Tamices
Antes de las computadoras, las tablas matemáticas que enumeraban todos los primos o las factorizaciones primarias hasta un límite dado se imprimían comúnmente. El método más antiguo para generar una lista de primos se llama tamiz de Eratóstenes. La animación muestra una variante optimizada de este método. Otro método de tamizado más eficiente para el mismo problema es el tamiz de Atkin. En matemáticas avanzadas, la teoría del tamiz aplica métodos similares a otros problemas.
Prueba de primalidad versus prueba de primalidad
Algunas de las pruebas modernas más rápidas para determinar si un número arbitrario dado es primo son los algoritmos probabilísticos (o Monte Carlo), lo que significa que tienen una pequeña probabilidad aleatoria de producir una respuesta incorrecta. Por ejemplo, el test de primalidad Solovay-Strassen en un número dado elige un número al azar de a y utiliza exponenciación modular para comprobar si es divisible por . Si es así, responde que sí y, de lo contrario, responde que no. Si realmente es primo, siempre responderá que sí, pero si es compuesto, entonces responde que sí con probabilidad como máximo 1/2 y no con probabilidad al menos 1/2. Si esta prueba se repite veces en el mismo número, la probabilidad de que un número compuesto pueda pasar la prueba cada vez es como máximo . Debido a que esto disminuye exponencialmente con el número de pruebas, proporciona una alta confianza (aunque no es cierto) de que un número que pase la prueba repetida es primo. Por otro lado, si la prueba falla alguna vez, entonces el número es ciertamente compuesto. Un número compuesto que pasa tal prueba se llama pseudoprima.
Por el contrario, algunos otros algoritmos garantizan que su respuesta siempre será correcta: los primos siempre se determinarán como primos y los compuestos siempre se determinarán como compuestos. Por ejemplo, esto es cierto para la división de prueba. Los algoritmos con salida garantizada correcta incluyen algoritmos determinísticos (no aleatorios), como la prueba de primalidad AKS y algoritmos aleatorizados de Las Vegas donde las elecciones aleatorias hechas por el algoritmo no afectan su respuesta final, como algunas variaciones de forma elíptica prueba de primalidad de la curva La prueba de primalidad de curva elíptica es la más rápida en la práctica de las pruebas de primalidad con garantía garantizada, pero su análisis de tiempo de ejecución se basa en argumentos heurísticos en lugar de pruebas rigurosas. La prueba de primalidad AKS ha demostrado matemáticamente la complejidad del tiempo, pero es más lento que la prueba de primitilidad de curva elíptica en la práctica. Estos métodos se pueden usar para generar grandes números primos aleatorios, generando y probando números aleatorios hasta encontrar uno que sea primo; al hacer esto, una prueba probabilística más rápida puede eliminar rápidamente la mayoría de los números compuestos antes de que se use un algoritmo de garantía garantizada para verificar que los números restantes sean primos.
La siguiente tabla enumera algunas de estas pruebas. Su tiempo de ejecución se da en términos de , el número a ser probado y, para los algoritmos probabilísticos, el número de pruebas realizadas. Además, es un número positivo arbitrariamente pequeño, y log es el logaritmo de una base no especificada. La gran notación O significa que cada límite de tiempo debe multiplicarse por un factor constante para convertirlo de unidades adimensionales a unidades de tiempo; este factor depende de los detalles de implementación, como el tipo de computadora utilizada para ejecutar el algoritmo, pero no de los parámetros de entrada y .
| Prueba de primalidad AKS | 2002 | determinista | |||
| Prueba de primalidad de curva elíptica | 1977 | Las Vegas | heurísticamente | ||
| Prueba de primalidad Miller-Rabin | 1980 | Monte Carlo | probabilidad de error | ||
| Prueba de primalidad Solovay-Strassen | 1977 | Monte Carlo | probabilidad de error |
Algoritmos de propósito especial y el mayor conocido conocido
Además de las pruebas antes mencionadas que se aplican a cualquier número natural, algunos números de una forma especial pueden probarse con mayor rapidez. Por ejemplo, la prueba de primalidad de Lucas-Lehmer puede determinar si un número de Mersenne (uno menos que una potencia de dos) es primordial, determinista, al mismo tiempo que una única iteración de la prueba de Miller-Rabin. Esta es la razón por la cual desde 1992 (a partir de enero de 2018) el primo más grande conocido siempre ha sido un primo de Mersenne. Se conjetura que hay infinitos números primos de Mersenne.
La siguiente tabla proporciona los primos más grandes conocidos de varios tipos. Algunos de estos primos se han encontrado usando computación distribuida. En 2009, el Great Internet Mersenne Prime Searchproject recibió un premio de US $ 100.000 por descubrir por primera vez una empresa principal con al menos 10 millones de dígitos. Electronic Frontier Foundation también ofrece $ 150,000 y $ 250,000 para números primos con al menos 100 millones de dígitos y mil millones de dígitos, respectivamente.
| Tipo | principal | Cantidad de dígitos decimales | Fecha | Encontrado por |
|---|---|---|---|---|
| Mersenne prime | 2 - 1 | 23,249,425 | 26 de diciembre de 2017 | Jonathan Pace, Great Internet Mersenne Prime Search |
| Proth prime (pero no un primo de Mersenne) | 10,223 × 2 + 1 | 9,383,761 | 31 de octubre de 2016 | Péter Szabolcs, PrimeGrid |
| prima factorial | 208,003! - 1 | 1,015,843 | Julio de 2016 | Sou Fukui |
| prima primordial | 1.098.133 # - 1 | 476,311 | Marzo de 2012 | James P. Burt, PrimeGrid |
| primos gemelos | 2,996,863,034,895 × 2 ± 1 | 388,342 | Septiembre de 2016 | Tom Greer, PrimeGrid |
Factorización de enteros
Dado un número entero compuesto , la tarea de proporcionar uno (o todos) factores primos se conoce como factorización de . Es significativamente más difícil que las pruebas de primalidad, y aunque se conocen muchos algoritmos de factorización, son más lentos que los métodos más rápidos de prueba de primalidad. La división de prueba y el algoritmo rho de Pollard se pueden usar para encontrar factores muy pequeños , y la factorización de curva elíptica puede ser efectiva cuando tiene factores de tamaño moderado. Los métodos adecuados para grandes números arbitrarios que no dependen del tamaño de sus factores incluyen el tamiz cuadrático y el tamiz de campo de número general. Al igual que con las pruebas de primalidad, también existen algoritmos de factorización que requieren que su entrada tenga una forma especial, incluido el tamiz de campo de número especial. A partir de enero de 2018, el mayor número que se sabe que ha sido factorizado por un algoritmo de propósito general es RSA-768, que tiene 232 dígitos decimales (768 bits) y es el producto de dos números primos grandes.
El algoritmo de Shor puede factorizar cualquier número entero en un número polinómico de pasos en una computadora cuántica. Sin embargo, la tecnología actual solo puede ejecutar este algoritmo para números muy pequeños. A partir de octubre de 2012, el número más grande que ha sido factorizado por una computadora cuántica que ejecuta el algoritmo de Shor es 21.
Otras aplicaciones computacionales
Varios algoritmos de criptografía de clave pública, como RSA y el intercambio de claves Diffie-Hellman, se basan en grandes números primos (primos de 2048 bits son comunes). RSA se basa en la suposición de que es mucho más fácil (es decir, más eficiente) para llevar a cabo la multiplicación de dos números (grandes) y que para calcular y (primos entre sí, se supone) si sólo el producto es conocido. El intercambio de claves Diffie-Hellman se basa en el hecho de que existen algoritmos eficientes para la exponenciación modular (informática ), mientras que la operación inversa (el logaritmo discreto) se considera un problema difícil.
Los números primos se utilizan con frecuencia para tablas hash. Por ejemplo, el método original de Carter y Wegman para el hashing universal se basaba en las funciones hash de cálculo al elegir funciones lineales aleatorias con números primos grandes. Carter y Wegman generalizaron este método a hashing independiente mediante el uso de polinomios de alto grado, nuevamente números primos de módulo grande. Además de en la función hash, los números primos se utilizan para el tamaño de la tabla hash en tablas hash basadas en sondeos cuadráticos para garantizar que la secuencia de la sonda cubra toda la tabla.
Algunos métodos de suma de comprobación se basan en las matemáticas de los números primos. Por ejemplo, las sumas de verificación utilizadas en los Números de Libro Estándar Internacionales se definen tomando el resto del número módulo 11, un número primo. Como 11 es primo, este método puede detectar errores de un solo dígito y transposiciones de dígitos adyacentes. Otro método de suma de comprobación, Adler-32, usa el módulo aritmético 65521, el número primo más grande menos que . Los números primos también se usan en generadores de números pseudoaleatorios, incluidos los generadores congruenciales lineales y el Twister de Mersenne.
Temas relacionados
Los números primos son de importancia central para la teoría de números, pero también tienen muchas aplicaciones en otras áreas dentro de las matemáticas, incluido el álgebra abstracta y la geometría elemental. Por ejemplo, es posible colocar números primos de puntos en una cuadrícula bidimensional para que no haya tres en una línea, o para que cada triángulo formado por tres de los puntos tenga un área grande. Otro ejemplo es el criterio de Eisenstein, una prueba para si un polinomio es irreductible basado en la divisibilidad de sus coeficientes por un número primo y su cuadrado.
El concepto de número primo es tan importante que se ha generalizado de diferentes maneras en varias ramas de las matemáticas. Generalmente, "prime" indica minimización o indecomposability, en un sentido apropiado. Por ejemplo, el campo principal de un campo dado es su subcampo más pequeño que contiene tanto 0 como 1. Es el campo de números racionales o un campo finito con un número primo de elementos, de ahí el nombre. Con frecuencia se pretende un segundo significado adicional mediante el uso de la palabra primo, es decir, que cualquier objeto puede descomponerse, esencialmente de forma única, en sus componentes principales. Por ejemplo, en la teoría de nudos, un nudo principal es un nudo indescomponible en el sentido de que no puede escribirse como la suma conectada de dos nudos no triviales. Cualquier nudo se puede expresar de manera única como una suma conectada de nudos principales.
Más allá de las matemáticas y la informática, los números primos tienen conexiones potenciales con la mecánica cuántica, y se han utilizado metafóricamente en las artes y la literatura. También se han utilizado en la biología evolutiva para explicar los ciclos de vida de las cigarras.
Polígonos y polígonos constructivos
Los primos Fermat son primos de la forma
con un número natural Se nombran después de Pierre de Fermat, que conjeturó que todos esos números son primos. Los primeros cinco de estos números, 3, 5, 17, 257 y 65.537, son primos, pero son compuestos y también lo son todos los demás números de Fermat que se han verificado a partir de 2017. Un gráfico regular es construible usando regla y compás si y solo si los factores primos impares de (si hay alguno) son primos de Fermat distintos. Del mismo modo, un octágono regular puede construirse usando regla, compás y un trisector de ángulo si y solo si los factores primos de son cualquier número de copias de 2 o 3 junto con un conjunto (posiblemente vacío) de primos de Pierpont distintos, primos de la forma .
Es posible dividir cualquier polígono convexo en polígonos convexos más pequeños de igual área y perímetro igual, cuando es una potencia de un número primo, pero esto no se conoce para otros valores de .
Mecánica cuántica
Comenzando con el trabajo de Hugh Montgomery y Freeman Dyson en la década de 1970, los matemáticos y los físicos han especulado que los ceros de la función zeta de Riemann están conectados a los niveles de energía de los sistemas cuánticos. Los números primos también son importantes en la ciencia de la información cuántica, gracias a las estructuras matemáticas, tales como las bases mutuamente imparciales y las medidas simétricas de información completa de operador positivo.
Biología
La estrategia evolutiva utilizada por las cigarras del género Magicicada hace uso de números primos. Estos insectos pasan la mayor parte de sus vidas como larvas bajo tierra. Solo pupan y luego salen de sus madrigueras después de 7, 13 o 17 años, en ese momento vuelan, se reproducen y luego mueren después de unas pocas semanas como máximo. Los biólogos teorizan que estas longitudes del ciclo de reproducción del número primo han evolucionado para evitar que los depredadores se sincronicen con estos ciclos. Por el contrario, los períodos de varios años entre la floración en las plantas de bambú se hipotéticamente son números suaves, teniendo solo números primos pequeños en sus factorizaciones.
Artes y literatura
Los números primos han influido en muchos artistas y escritores. El compositor francés Olivier Messiaen utilizó números primos para crear música ametral a través de "fenómenos naturales". En obras como La Nativité du Seigneur (1935) y Quatre études de rythme (1949-50), emplea simultáneamente motivos con longitudes dadas por diferentes números primos para crear ritmos impredecibles: los números primos 41, 43, 47 y 53 aparecen en el tercer étude, "Neumes rythmiques". Según Messiaen, esta manera de componer estaba "inspirada en los movimientos de la naturaleza, movimientos de duraciones libres y desiguales".
En su novela de ciencia ficción Contact , el científico Carl Sagan sugirió que la factorización prima podría usarse como un medio para establecer planos de imagen bidimensionales en las comunicaciones con alienígenas, una idea que había desarrollado informalmente por primera vez con el astrónomo estadounidense Frank Drake en 1975. novela El incidente curioso del perro en la noche por Mark Haddon, el narrador organiza las secciones de la historia por números primos consecutivos como una forma de transmitir el estado mental de su personaje principal, un adolescente matemáticamente dotado con síndrome de Asperger. Los números primos se utilizan como una metáfora de la soledad y el aislamiento en la novela de Paolo Giordano La soledad de los números primos , en la que se los retrata como "extraños" entre enteros.