Número primo

Un número primo es un número natural que tiene exactamente dos divisores naturales distintos . En otras palabras, un número natural es primo si es diferente y divisible sin resto solo por sí mismo [1] . $pags$ $una$ $una$ $pags$

Ejemplo: el número es primo (divisible por y por ), pero no es primo, ya que, además de y , es divisible por - tiene tres divisores naturales. $2$ $una$ $2$ $cuatro$ $una$ $cuatro$ $2$

El estudio de las propiedades de los números primos se dedica a la teoría de los números , y el principal teorema de la aritmética establece su papel central en ella: cualquier número entero que exceda es primo o puede expresarse como un producto de números primos, y tal representación es único hasta el orden de los factores [1] . La unidad no se denomina números primos, ya que de lo contrario la expansión indicada se vuelve ambigua [2] : . $una$ $x=1\cdot x=1\cdot 1\cdot x=1\cdot 1\cdot ...\cdot 1\cdot x$

Los números naturales se pueden dividir en tres clases: uno (tiene un divisor natural), número primo (tiene dos divisores naturales), número compuesto (tiene más de dos divisores naturales) [1] . Hay infinitos números primos y compuestos.

La secuencia de números primos comienza así:

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Existen varios algoritmos para comprobar si un número es primo. Por ejemplo, el conocido método de enumeración de divisores es primitivo y lento en comparación con otros.

Los números primos se utilizan ampliamente en matemáticas y ciencias afines. Muchos algoritmos de tecnología de la información , como los criptosistemas asimétricos , utilizan las propiedades de factorización de los números enteros [4] .

Muchos problemas relacionados con los números primos siguen abiertos .

Hay generalizaciones del concepto de número primo para anillos arbitrarios y otras estructuras algebraicas .

Historia

No se sabe cuándo se definió el concepto de número primo, pero las primeras evidencias datan del Paleolítico Superior, lo que se confirma con el hueso de Ishango [5] .

En los registros supervivientes de los antiguos matemáticos egipcios , hay indicios de que tenían algunas ideas sobre los números primos: por ejemplo, el papiro Rhind , que data del segundo milenio antes de Cristo, contiene una tabla de proporciones del número 2 a , representada por el suma de tres o cuatro fracciones egipcias con una unidad en el numerador y diferentes denominadores. Las expansiones de fracciones cuyos denominadores tienen un divisor común son similares, por lo que los egipcios al menos conocían la diferencia entre un número primo y un número compuesto [6] . $norte$

Los primeros estudios de números primos que nos han llegado se deben a los matemáticos de la antigua Grecia . Inventaron la criba de Eratóstenes , un algoritmo para encontrar secuencialmente todos los números primos del 1 al . Publicado aproximadamente en el 300 a. C. , los Elementos de Euclides contienen importantes teoremas sobre números primos, incluido el infinito de su conjunto, el lema de Euclides y el teorema fundamental de la aritmética [7] . $norte$

Hasta el siglo XVII, no hubo nuevos trabajos significativos en el campo de los números primos [8] . En 1640, Pierre de Fermat formuló el pequeño teorema de Fermat , luego probado por Leibniz y Euler , y el teorema de la suma de dos cuadrados , y también conjeturó que todos los números de la forma son primos, e incluso demostró esto hasta . Pero ya para el siguiente número de Fermat, Euler probó la divisibilidad por . Hasta el momento no se han encontrado nuevos números primos en la secuencia de Fermat. Al mismo tiempo, el monje francés Marin Mersenne descubrió que la sucesión , donde es un número primo, también da un número primo [9] ( números de Mersenne ). $2^{{2^{n}}}+1$ $n=4$ ${\ estilo de visualización 2^{2^{5}}+1}$ ${\ estilo de visualización 641}$ ${\ estilo de visualización 2 ^ {p} -1}$ $pags$

El trabajo de Euler en teoría de números contenía mucha información sobre números primos. Demostró que una serie de números infinitos es divergente. En 1747 demostró que incluso los números perfectos son los valores de la sucesión , donde el factor es el número de Mersenne. En su correspondencia con Goldbach , este último enunció su famosa conjetura sobre la representación de cualquier número par, a partir de cuatro, por la suma de dos primos [10] . La prueba de la conjetura aún no se ha encontrado. ${\ estilo de visualización 1/2+1/3+1/5+1/7+1/11+...}$ ${\ estilo de visualización 2^{p-1}(2^{p}-1)}$

Desde principios del siglo XIX, la atención de muchos matemáticos ha estado ocupada por el problema de la distribución asintótica de los números primos [10] . Legendre y Gauss independientemente sugirieron que la densidad de números primos es, en promedio, cercana a un valor que es inversamente proporcional al logaritmo natural [11] .

Durante mucho tiempo, los números primos se consideraron de poca utilidad fuera de las matemáticas puras . Esto cambió en la década de 1970 con la llegada de los conceptos de criptografía de clave pública , en la que los números primos formaban la base de los primeros algoritmos de cifrado como RSA [12] .

Descomposición de números naturales en un producto de números primos

La representación de un número natural como producto de números primos se denomina descomposición en números primos o factorización de números . Por el momento, no se conocen algoritmos polinómicos para factorizar números, aunque no se ha demostrado que tales algoritmos no existan. El criptosistema RSA y algunos otros se basan en la supuesta alta complejidad computacional del problema de factorización. La factorización con complejidad polinomial es teóricamente posible en una computadora cuántica usando el algoritmo de Shor [13] .

Teorema fundamental de la aritmética

El teorema fundamental de la aritmética establece que todo número natural mayor que uno puede representarse como producto de números primos, y de forma única, hasta el orden de los factores [14] . Por lo tanto, los números primos son los "bloques de construcción" elementales de los números naturales. Por ejemplo:

${\ estilo de visualización 23244}$	$=2\cdot 2\cdot 3\cdot 13\cdot 149$
	$=2^{2}\cdot 3\cdot 13\cdot 149$ . ( denota cuadrado o segunda potencia ). $2^{2}$ $2$

Como se muestra en este ejemplo, el mismo divisor primo puede aparecer varias veces. Descomposición:

norte = pags 1 pags 2 ... pags t _

número n en (número finito) factores primos p 1 , p 2 , … , p t se llama descomposición en factores primos de n . El teorema fundamental de la aritmética se puede reformular de la siguiente manera: cualquier descomposición en números primos será idéntica hasta el orden de los divisores . En la práctica, para la mayoría de los números, hay muchos algoritmos de factorización simple, todos los cuales dan el mismo resultado [13] .

Simplicidad de la unidad

La mayoría de los antiguos griegos ni siquiera consideraban un número, por lo que no podían considerarlo un número primo [15] . Hacia la Edad Media y el Renacimiento, muchos matemáticos lo incluyeron como primer número primo [16] . A mediados del siglo XVIII, Christian Goldbach enumeró como primer número primo en su famosa correspondencia con Leonhard Euler ; sin embargo, el propio Euler no lo consideró un número primo [17] . En el siglo XIX, muchos matemáticos todavía consideraban que un número era un número primo. Por ejemplo, la lista de números primos de Derrick Norman Lemaire , reimpresa en 1956, comenzaba con el primer número primo. Se dice que Henri Lebesgue es el último matemático que llamó primos [18] . A principios del siglo XX, los matemáticos comenzaron a llegar a un consenso sobre lo que no es un número primo, sino que forma su propia categoría especial: "uno" [16] . $una$ $una$ $una$ $una$ $una$ ${\ estilo de visualización 10006721}$ $una$ $una$ $una$

Si se considera un número primo, entonces el teorema fundamental de la aritmética de Euclides (mencionado anteriormente) no se cumplirá, como se indicó al comienzo del artículo. Por ejemplo, un número se puede descomponer como 3 5 y 1 3 5 . Si fuera un número primo, estas dos opciones se considerarían factorizaciones diferentes ; en consecuencia, habría que cambiar el enunciado de este teorema [16] . De la misma manera, la criba de Eratóstenes no funcionaría correctamente si se considerara simple: una versión modificada de la criba, que asume que es un número primo, excluye todos los factores que son múltiplos (es decir, todos los demás números), y produce solo un número en la salida - . Además, los números primos tienen varias propiedades que un número no tiene , como la razón de un número a su correspondiente valor de la función de identidad de Euler o la suma de una función divisor [2] . $una$ $quince$ $una$ $quince$ $una$ $una$ $una$ $una$ $una$

Algoritmos para buscar y reconocer números primos

Formas sencillas de encontrar una lista inicial de números primos hasta cierto valor dan la criba de Eratóstenes , la criba de Sundaram y la criba de Atkin [19] .

Sin embargo, en la práctica, en lugar de obtener una lista de números primos, a menudo es necesario verificar si un número dado es primo. Los algoritmos que resuelven este problema se denominan pruebas de primalidad . Hay muchas pruebas de primalidad polinomial , pero la mayoría de ellas son probabilísticas (por ejemplo, la prueba de Miller-Rabin ) y se utilizan para las necesidades de la criptografía [20] . En 2002, se demostró que el problema general de primalidad es resoluble polinomialmente, pero la prueba determinista Agrawal-Kayal-Saksena propuesta tiene una complejidad computacional bastante grande , lo que dificulta su aplicación en la práctica [21] .

Para algunas clases de números, existen pruebas de primalidad eficientes especializadas (ver más abajo).

Prueba de simplicidad

Una prueba de primalidad (o prueba de primalidad) es un algoritmo que, habiendo tomado un número como entrada, permite no confirmar la suposición sobre la composición del número o afirmar con precisión su primalidad. En el segundo caso, se denomina prueba de primalidad verdadera. La tarea de la prueba de primalidad pertenece a la clase de complejidad P , es decir, el tiempo de ejecución de los algoritmos para resolverla depende polinomialmente del tamaño de los datos de entrada, lo cual fue probado en 2002 [22] . La aparición de un algoritmo polinomial fue predicha por la existencia de certificados de primalidad polinomial y, como consecuencia, por el hecho de que el problema de verificar la primalidad de un número pertenecía a las clases NP y co-NP al mismo tiempo.

Los algoritmos existentes para probar la primalidad de un número se pueden dividir en dos categorías: pruebas de primalidad verdadera y pruebas de primalidad probabilística. El resultado de los cálculos de las pruebas verdaderas es siempre el hecho de la simplicidad o composición de un número. La prueba probabilística muestra si un número es primo con alguna probabilidad. Los números que satisfacen la prueba de primalidad probabilística, pero son compuestos, se denominan pseudoprimos [23] . Un ejemplo de tales números son los números de Carmichael [24] .

Un ejemplo de pruebas de primalidad verdadera es la prueba de Luc-Lehmer para los números de Mersenne . La desventaja obvia de esta prueba es que solo se aplica a ciertos tipos de números. Otros ejemplos incluyen aquellos basados en el Pequeño Teorema de Fermat [25]

Prueba de Pepin para números de Fermat
Teorema de Prot para números de Prot
Prueba de Agrawal-Kayala-Saxene , la primera prueba de primalidad universal, polinomial, determinista e incondicional.
Prueba de Luc-Lehmer-Riesel

Tanto como:

método de iteración del divisor
teorema de wilson
criterio de pocklington
prueba de molinero
Prueba de Adleman-Pomerans-Rumeli , mejorada [26] por Cohen y Lenstroy
Prueba de primalidad mediante curvas elípticas .

Las pruebas de primalidad probabilística incluyen:

Primos grandes

Durante muchos siglos, la búsqueda de números primos "grandes" ha sido de interés para los matemáticos. En las últimas décadas, estos estudios han cobrado importancia práctica debido al uso de tales números en una serie de algoritmos de encriptación, como RSA [12] .

En el siglo XVII, Marin Mersenne sugirió que los números de la forma son primos (para n ≤ 257) solo para n igual a 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 y 257 [11 ] . La verificación de la exactitud de la suposición estaba mucho más allá de las capacidades de ese momento. Recién en el siglo XX se descubrió que la hipótesis era falsa y probablemente hecha "a ciegas", ya que Mersenne no tuvo en cuenta tres casos (para n = 61, 89 y 107); además, resultó que los números correspondientes a n = 67 y n = 257 son compuestos [11] . $2^{n}-1$

En 1876 , Eduard Lucas demostró que M 127 (un número de 39 dígitos) es un número primo, siguió siendo el número primo más grande conocido hasta 1951, cuando se encontraron (44 dígitos) y, un poco más tarde, (de 79 dígitos) - el último un número primo que se encontró usando una calculadora electrónica. Desde entonces, todos los números primos grandes subsiguientes han sido descubiertos por computadora: desde 1952 (cuando SWAC mostró que M 521 era primo), hasta 1996 fueron encontrados por una supercomputadora , y todos eran números primos de Mersenne (encontrados usando la prueba de Luc-Lehmer , una algoritmo específico para tales números), a excepción del número , que fue un récord entre 1989 y 1992 [27] . ${\frac{2^{148}+1}{17}}$ ${\ estilo de visualización 180 * (2 ^ {127} -1) ^ {2} +1}$ ${\ estilo de visualización 391581 * 2 ^ {216193} -1}$

Algoritmos para la obtención de números primos

Algunos problemas matemáticos que utilizan la factorización requieren una serie de números primos muy grandes elegidos al azar. El algoritmo para su obtención, basado en el postulado de Bertrand (Para todo número natural n ≥ 2, existe un número primo p en el intervalo n < p < 2 n .) [28] :

Algoritmo:

Entrada : número natural $norte$
Solución (búsqueda de un número primo aleatorio P)
1. $P\obtiene$ La función de generar un número natural arbitrario en un segmento $[N,2N]$
2. Si es compuesto entonces $PAGS$
  1. $P\flecha izquierda\,P+1$
  2. si entonces $P=2N$
    1. $P\flecha izquierda\,N$
3. Devuelve " -primo aleatorio" $PAGS$

El tiempo para resolver el problema por este algoritmo no está definido, pero existe una alta probabilidad de que siempre sea polinomial, siempre que haya suficientes números primos y estén distribuidos más o menos uniformemente . Para números aleatorios simples, estas condiciones se cumplen [21] .

El medio más efectivo para construir números primos es el pequeño teorema de Fermat [26] ligeramente modificado .

Sean N, S números naturales impares, N-1 = S*R, y para cada divisor primo q de S existe un entero tal que $a$

$a^{N-1}=1{\pmod {N))$ , $\gcd(a^{{\frac {N-1}{q}}-1},n)=1$

Entonces todo divisor primo p de N satisface la congruencia

$p=1{\pmod {2S))$

Consecuencia. Si se cumplen las condiciones del teorema de Fermat y , entonces N es un número primo [26] . $R\leqslant 4S+2$

Ahora mostremos cómo, con la ayuda de la última afirmación, dado un número primo grande , se puede construir un número primo sustancialmente mayor . Para hacer esto, elegimos aleatoriamente un número par en el intervalo y establecemos . Luego comprobamos la ausencia de pequeños divisores primos en el número dividiéndolo por pequeños números primos; Probemos varias veces usando el algoritmo de Rabin . Si al mismo tiempo resulta que es un número compuesto, debe elegir un nuevo valor y repetir los cálculos nuevamente. Esto debe hacerse hasta que se encuentre un número N que haya pasado la prueba del algoritmo de Rabin suficientes veces. En este caso, existe la esperanza de que sea un número primo, y se debe intentar probar la primacía usando pruebas de primacía [26] . $S$ $norte$ $R$ $R\leqslant 4S+2$ ${\ estilo de visualización N = SR + 1}$ $norte$ $norte$ $norte$ $R$ $norte$

Infinidad de números primos

Hay infinitos números primos . Esta declaración se conoce como el teorema de Euclides, en honor al antiguo matemático griego Euclides , ya que se le atribuye la primera prueba conocida de esta declaración. Se conocen muchas más pruebas para la infinidad de números primos, incluida la prueba analítica de Euler, la prueba de Goldbach usando números de Fermat [29] , la prueba de Furstenberg usando topología general y la prueba elegante de Kummer .

El número primo más grande conocido

Los registros se han mantenido durante mucho tiempo, marcando los números primos más grandes conocidos en ese momento [30] . Uno de los récords fue establecido en un momento por Euler , habiendo encontrado un número primo 2 31 − 1 = 2 147 483 647 .

El número primo más grande conocido en enero de 2019 es el número de Mersenne M 82 589 933 = 2 82 589 933 − 1 . Contiene 24.862.048 dígitos decimales ; un libro que registre este número tendría unas nueve mil páginas. Se encontró el 7 de diciembre de 2018 como parte de la búsqueda distribuida de números primos de Mersenne de GIMPS . El anterior número primo más grande conocido, descubierto en diciembre de 2017, tenía 1 612 623 caracteres menos [31] .

Los números de Mersenne se diferencian favorablemente del resto por la presencia de una prueba de primalidad eficaz : la prueba de Luc-Lehmer . Gracias a él, los números primos de Mersenne han mantenido durante mucho tiempo el récord como los números primos más grandes conocidos.

Para encontrar números primos de más de 100 000 000 y 1 000 000 000 de dígitos decimales , la EFF otorgó [32] premios en efectivo de $150 000 y $250 000 , respectivamente [33] . La EFF ha otorgado premios anteriormente por encontrar números primos de 1,000,000 y 10,000,000 de dígitos decimales.

Números primos de un tipo especial

Hay una serie de números cuya primalidad se puede establecer de manera eficiente utilizando algoritmos especializados.

Los números de Mersenne son números de la forma , donde n es un número natural [34] . Además, un número de Mersenne puede ser primo solo si n es un número primo. Como se señaló anteriormente, una prueba de primalidad eficaz es la prueba de Luc-Lehmer [35] . $M_{n}=2^{n}-1$
Los números de Fermat son números de la forma , donde n es un número entero no negativo [36] . Una prueba de primalidad efectiva es la prueba de Pepin . A partir de febrero de 2015, solo se conocen 5 números primos de Fermat (para n = 0, 1, 2, 3, 4), los siguientes veintiocho números primos de Fermat (hasta e inclusive) resultaron ser compuestos [37] , pero No se ha probado que otros primos de la Granja no [38] . $F_{n}=2^{2^{n}}+1$ ${\ estilo de visualización F_ {32}}$
Los números de Woodall son números de la forma [39] . Una prueba de primalidad efectiva es la prueba de Lucas-Lehmer-Riesel [40] . $W_{n}=n\cdot 2^{n}-1$
Los números de Cullen son números de la forma [41] [42] . $C_{n}=n\cdot 2^{n}+1$
Los números proth son números de la forma , donde k es impar y [43] . Una prueba de primalidad eficaz para los números de Proth es la prueba de Brillhart -Lehmer-Selfridge [ 44 ] . Los números de Cullen y los números de Fermat son un caso especial de los números de Proth (para k = n y para k = 1, respectivamente ) [45] . $P=k\cdot 2^{n}+1$ $2^{n}>k$ $n=2^{m}$
Los números de Mills son números de la forma donde es la constante de Mills [46] . $P_{n}=[A^{3^{n}}],$ $A$

Para buscar números primos de tipos designados, actualmente se utilizan los proyectos de computación distribuida GIMPS , PrimeGrid , Ramsey@Home , Seventeen o Bust , Riesel Sieve , Wieferich@Home .

Algunas propiedades

Si p es primo y p divide a ab , entonces p divide a o b . La prueba de este hecho fue dada por Euclides y se conoce como Lema de Euclides [7] [47] . Se utiliza en la demostración del teorema fundamental de la aritmética .
Un anillo de residuos es un campo si y solo si es simple [48] . $\mathbb {Z} _{n}$ $norte$
La característica de cada campo es cero o un número primo [48] .
Si es primo y es natural, entonces es divisible por ( pequeño teorema de Fermat ) [49] . $pags$ $a$ $a^{p}-a$ $pags$
Si es un grupo finito cuyo orden es divisible por , entonces contiene un elemento de orden ( teorema de Cauchy ) [50] . $GRAMO$ $|G|$ $pags$ $GRAMO$ $pags$
Si es un grupo finito, y es la máxima potencia que divide , entonces tiene un subgrupo de orden , llamado subgrupo de Sylow , además, el número de subgrupos de Sylow es igual para algún número entero ( teorema de Sylow ) [51] . $GRAMO$ $pag^{n}$ $pags$ $|G|$ $GRAMO$ $pag^{n}$ $paquete+1$ $k$
Un natural es primo si y sólo si es divisible por ( teorema de Wilson ) [52] . $pag>1$ $(p-1)!+1$ $pags$
Si es un número natural, entonces existe un primo tal que ( postulado de Bertrand ) [53] . $n>1$ $pags$ $n<p<2n$
Una serie de números inversos a los primos diverge [10] . Además, en $x\a\infty$ $\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x.$
Cualquier progresión aritmética de la forma , donde son enteros coprimos , contiene infinitos números primos ( el teorema de Dirichlet sobre los números primos en la progresión aritmética ) [54] . $a,a+q,a+2q,a+3q,...$ $a,q>1$
Cualquier número primo mayor que 3 se puede representar como o , donde es algún número natural. Por lo tanto, si la diferencia entre varios números primos consecutivos (para k>1) es la misma, entonces es necesariamente un múltiplo de 6, por ejemplo: 251-257-263-269; 199-211-223; 20183-20201-20219. $6k+1$ $6k-1$ $k$
Si es primo, entonces es múltiplo de 24 (también válido para todos los números impares no divisibles por 3) [55] . $pag>3$ $p^{2}-1$
Teorema de Green-Tao . Hay progresiones aritméticas finitas arbitrariamente largas que consisten en números primos [56] .
Ningún número primo puede parecerse a , donde n >2, k >1. En otras palabras, el número que sigue a un primo no puede ser un cuadrado o una potencia superior con una base mayor que 2. También se deduce de esto que si un número primo tiene la forma , entonces k es un primo (ver números de Mersenne ) [34 ] . $n^{k}-1$ $2^{k}-1$
Ningún número primo puede parecerse a , donde n >1, k >0. En otras palabras, un número que precede a un primo no puede ser un cubo o una potencia impar superior con una base mayor que 1 [57] . $n^{{2k+1}}+1$
Cada número primo (excepto los números de la forma ) se puede representar como la suma de tres cuadrados [58] . ${\ estilo de visualización 8n-1}$

Aplicaciones

Los números primos son componentes fundamentales en muchas áreas de las matemáticas .

Funciones aritméticas

Las funciones aritméticas , es decir, las funciones definidas sobre el conjunto de los números naturales y que toman valores en el conjunto de los números complejos, juegan un papel crucial en la teoría de números. En particular, las más importantes entre ellas son las funciones multiplicativas , es decir, funciones que tienen la siguiente propiedad: si un par consta de números coprimos, entonces se produce la igualdad [59] $F$ $(a, b)$

${\ Displaystyle f (ab) = f (a) f (b)}$

Ejemplos de funciones multiplicativas son la función de Euler , que asocia un número con el número de números naturales menores que n y coprimos con él y el número de divisores de n [60] . El valor de estas funciones de la potencia de un número primo: $\fi$ $norte$

Función de Euler $\fi$ :

${\ estilo de visualización \ phi (p^{m})=p^{m}-p^{m-1))$

Función divisoria :

${\ estilo de visualización \ sigma (p ^ {m}) = m + 1}$

Las funciones aritméticas se pueden calcular fácilmente conociendo los valores que toman para las potencias de los números primos [59] . De hecho, a partir de la factorización de un número natural n

$n=p_{1}^{q_{1}}\cdot ...\cdot p_{a}^{q_{a}}$

tenemos eso

$f(n)=f(p_{1}^{q_{1)))\cdot ...\cdot f(p_{a}^{q_{a)))$

y por tanto, volviendo al problema del cálculo, resulta que suele ser más fácil calcular a partir de cada potencia de un divisor primo que hacerlo mediante la fórmula general [61] . $f(n)$ $F$ $F$

Por ejemplo, para saber el valor de la función de Euler de n = 450 = 2 × 3 2 × 5 2 , basta con calcular $\fi$

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

Aritmética modular

En la aritmética modular , los números primos juegan un papel muy importante: un anillo de residuos es un campo si y solo si n es primo [48] . Además, la existencia de una raíz anular primitiva está ligada a los primos: existe solo si n es un número primo, 1, 2, 4 o un número en la forma , donde p es impar. $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} /n\mathbb {Z}$ $p^{n}\circ 2p^{n}$

Uno de los teoremas más importantes de la aritmética modular es el pequeño teorema de Fermat [52] . Este teorema establece que para cualquier número primo p y cualquier número natural a tenemos:

$a^{p}\equiv a{\pmod {p))$

o para cualquier primo p y cualquier a natural no divisible por p ,

$a^{p-1}\equiv 1{\pmod {p))$

Esta propiedad se puede utilizar para comprobar si un número no es primo. De hecho, si n es tal que:

$a^{n}\not \equiv a{\pmod {n))$

para alguna a natural , entonces n no puede ser simple [52] . Sin embargo, esta propiedad no se puede usar para probar si un número es primo: hay algunos números llamados números de Carmichael (el más pequeño es 561) para los cuales esto no será cierto. Un número de Carmichael es un número compuesto que es un pseudoprimo en toda base b coprimo con n. En 1994, William Robert Alford, Andrew Granville y Carl Pomerance demostraron que existen infinitos números de este tipo [62] .

Teoría de grupos

Los números primos también juegan un papel fundamental en el álgebra . En la teoría de grupos, un grupo en el que cada elemento es una potencia de un primo p se denomina grupo p [63] . Un P-grupo es finito si y solo si el orden del grupo (el número de sus elementos) es una potencia de p. Un ejemplo de un grupo p infinito es el grupo p de Prufer [64] . Se sabe que los p -grupos tienen un centro no trivial y por lo tanto no pueden ser simples (excepto para un grupo con p elementos); si el grupo es finito, además, todos los subgrupos normales intersecan el centro de una manera no trivial.

Un ejemplo de tales grupos es el grupo cíclico de multiplicación módulo un número primo [65] .

Todos los grupos de orden p son cíclicos y por lo tanto abelianos ; todo grupo de orden p 2 también es abeliano . Además, cualquier grupo abeliano finito es isomorfo a un producto directo de un número finito de grupos p cíclicos.

El teorema de Cauchy establece que si el orden de un grupo finito G es divisible por un número primo p, entonces G contiene elementos de orden p. Este teorema es generalizado por los teoremas de Sylow [50] .

Criptosistema de clave pública

Algunos algoritmos de criptografía de clave pública, como RSA y el intercambio de claves Diffie-Hellman , se basan en números primos grandes (normalmente 1024-2048 bits). RSA se basa en la suposición de que es mucho más fácil (es decir, más eficiente) realizar la multiplicación de dos números (grandes) x e y que calcular coprimos x e y si solo se conoce su producto . El intercambio de claves Diffie-Hellman se basa en el hecho de que existen algoritmos eficientes para el módulo de exponenciación , y la operación inversa del logaritmo discreto se considera difícil [66] [67] . $x\cdot y$

La dificultad de factorizar números grandes condujo al desarrollo del primer método eficiente de criptografía de clave pública , RSA [68] . En este sistema criptográfico, la persona que va a recibir el mensaje cifrado genera una clave: se eligen dos números primos aleatorios diferentes y de un tamaño determinado (normalmente se utilizan números de 1024 o 2048 bits ). Además, se calcula su producto , llamado módulo . El valor de la función de Euler se calcula a partir del número : . Se elige un número entero ( ) que sea coprimo con el valor de la función . Por lo general, los números primos pequeños se toman como tales (por ejemplo, los números primos de Fermat ). El número se llama exponente público . Se calcula un número , llamado exponente secreto, multiplicativamente inverso al número e módulo . El par se publica como una clave pública RSA ( clave pública RSA ) . El par desempeña el papel de una clave privada RSA y se mantiene en secreto [12] . $pags$ $q$ ${\ estilo de visualización n = p * q}$ $norte$ ${\ estilo de visualización \ phi (n) = (p-1) (q-1)}$ $mi$ ${\ estilo de visualización 1 <e <\ phi (n)}$ $\phi(n)$ $mi$ $mi$ $d$ $\phi(n)$ ${\ estilo de visualización \ {e, n \}}$ ${\ estilo de visualización \ {d, \ phi (n) \}}$

En teoría, es posible derivar una clave privada a partir de información pública: esto actualmente requiere la factorización de números , lo que hace que sea seguro transmitir un mensaje seguro si los números primos cumplen ciertas condiciones y son "lo suficientemente grandes". Todavía no se sabe si existen métodos eficientes para descifrar un mensaje que no impliquen un ataque de factorización directa , pero se ha demostrado que una mala selección de la clave pública puede hacer que el sistema sea más vulnerable a este tipo de ataques [69] . $norte$ $norte$

En 1991, RSA Security publicó una lista de semiprimes , ofreciendo premios en efectivo por factorizar algunos de ellos, para probar la seguridad del método y fomentar la investigación en esta área: una iniciativa llamada Challenge RSA Factoring [70] . A lo largo de los años, algunos de estos números se han descompuesto y, para otros, el problema de la factorización sigue abierto; sin embargo, la competencia terminó en 2007 [70] .

Fórmulas para encontrar números primos

En varios momentos se intentó indicar una expresión cuyos valores para diferentes valores de las variables incluidas en ella serían números primos [54] . L. Euler indicó un polinomio que toma valores primos para n = 0, 1, 2,…, 40 . Sin embargo, para n = 41 , el valor del polinomio es un número compuesto. Se puede probar que no existe un polinomio en una variable n que tome valores primos para todos los enteros n [54] . P. Fermat sugirió que todos los números de la forma 2 2 k + 1 son simples; sin embargo, Euler refutó esta conjetura demostrando que el número 2 2 5 + 1 = 4 294 967 297 es compuesto [54] . $\textstyle n^{2}-n+41,$

Sin embargo, existen polinomios cuyo conjunto de valores positivos, para valores no negativos de las variables, coincide con el conjunto de primos. Un ejemplo es el polinomio

{\begin{alineado}{\bigl (}k+2{\bigr)}{\bigl \{}1&-{\bigl [}wz+h+jq{\bigr]}^{2}- {\bigl [}(gk+2g+k+1)(h+j)+hz{\bigr]}^{2}-{\bigl [}2n+p+q+ze{\bigr]}^{ 2}\\&-{\bigl [}16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}{\bigr ]}^{ 2}-{\bigl [}e^{3}(e+2)(a+1)^{2}+1-o^{2}{\bigr]}^{2}-{\bigl [} (a^{2}-1)y^{2}+1-x^{2}{\bigr]}^{2}\\&-{\bigl [}16r^{2}y^{4} (a^{2}-1)+1-u^{2}{\bigr]}^{2}-{\bigl [}((a+u^{2}(u^{2}-a) )^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}{\bigr]}^{2}-{\bigl [}n+l+vy{ \bigr ]}^{2}\\&-{\bigl [}(a^{2}-1)l^{2}+1-m^{2}{\bigr ]}^{2}-{ \bigl [}ai+k+1-li{\bigr]}^{2}-{\bigl [}p+l(an-1)+b(2an+2a-n^{2}-2n-2 )-m{\bigr]}^{2}\\&-{\bigl [}q+y(ap-1)+s(2ap+2a-p^{2}-2p-2)-x{\ bigr]}^{2}-{\bigl [}z+pl(ap)+t(2ap-p^{2}-1)-pm{\bigr]}^{2}{\bigr \}}\ fin{alineado}}

que contiene 26 variables y tiene un grado de 25. El grado más pequeño para polinomios conocidos de este tipo es 5 con 42 variables; el número más pequeño de variables es 10 con un grado de alrededor de 1.6·10 45 [71] [72] . Este resultado es un caso especial de la propiedad diofántica de cualquier conjunto enumerable demostrado por Yuri Matiyasevich .

Curiosamente, el polinomio anterior, que genera números primos, se factoriza a sí mismo. Tenga en cuenta que el segundo factor de este polinomio (entre llaves) tiene la forma: uno menos la suma de los cuadrados. Así, un polinomio puede tomar valores positivos (para valores positivos ) solo si, cada uno de estos cuadrados (es decir, cada polinomio entre corchetes) es igual a cero. En este caso, la expresión entre llaves será igual a 1 [73] . $k$

Preguntas abiertas

Todavía quedan muchas preguntas abiertas sobre los números primos, las más famosas de las cuales fueron enumeradas por Edmund Landau en 1912 en el Quinto Congreso Matemático Internacional [74] :

Problema de Goldbach ( primer problema de Landau ): ¿es cierto que todo número par mayor que dos se puede representar como la suma de dos primos?
Segundo problema de Landau : ¿existe un conjunto infinito de " gemelos simples ", pares de números primos cuya diferencia es igual a 2 [54] ? En 2013, el matemático Zhang Yitang de la Universidad de New Hampshire [75] [76] demostró que existen infinitos pares de números primos cuya distancia no supera los 70 millones. Más tarde, James Maynard mejoró el resultado a 600. En 2014, el proyecto Polymath dirigido por Terence Tao mejoró un poco el último método al reemplazar la estimación de distancia con 246.
Conjetura de Legendre ( tercer problema de Landau ): ¿es cierto que para cualquier número natural entre y siempre hay un número primo [77] ? $norte$ $n^{2}$ $(n+1)^2$
Cuarto problema de Landau : ¿el conjunto de primos de la forma es infinito , donde es un número natural [54] ? $n^{2}+1$ $norte$

Un problema abierto es también la existencia de un número infinito de números primos en muchas sucesiones enteras, incluidos los números de Mersenne [54] , los números de Fibonacci, los números de Fermat , etc.

Variaciones y generalizaciones

Elementos irreductibles y primos

Al comienzo del artículo, se dio la definición de un número primo: un número natural se llama primo si tiene exactamente dos divisores: uno y el número mismo. Un concepto similar se puede introducir en otras estructuras algebraicas; la mayoría de las veces, se consideran anillos conmutativos sin divisores de cero ( dominios de integridad ) [78] [79] . Tales anillos, sin embargo, pueden tener divisores de la unidad , formando un grupo multiplicativo . Por ejemplo, en el anillo de los números enteros hay dos divisores de la unidad: y Por lo tanto, todos los números enteros, excepto los divisores de la unidad, no tienen dos, sino al menos cuatro divisores; por ejemplo, el número 7 tiene divisores , lo que significa que la generalización del concepto de número primo debe basarse en sus otras propiedades. $+1$ $-una.$ ${\ estilo de visualización 1; 7; -1; -7.}$

El análogo de un número primo para el área de integridad es un elemento irreducible . que se define como sigue [80] .

Un elemento distinto de cero del dominio de integridad se llama irreducible (a veces indescomponible ) si no es un divisor de la unidad y se sigue de la igualdad que o es un divisor de la unidad. $pags$ ${\ estilo de visualización p = ab}$ $a$ $b$

Para números enteros, esta definición significa que los elementos irreducibles son los números naturales primos, así como sus opuestos.

De la definición se deduce que el conjunto de divisores de un elemento irreducible consta de dos partes: todos los divisores de la unidad y los productos por todos los divisores de la unidad (estos productos se denominan asociados a los elementos). Es decir, el número de divisores del irreducible , si es finito, es el doble del número de divisores de la unidad en el anillo. $pags$ $pags$ $pags$ $pags,$

De gran importancia es el análogo del teorema principal de la aritmética , que en forma generalizada se formula de la siguiente manera [81] :

Un anillo se llama factorial si todo elemento distinto de cero en él que no sea divisor de la unidad se puede representar como un producto de elementos irreducibles, y esta representación es única hasta una permutación de factores y su asociación (multiplicación por divisores de la unidad ).

No todos los dominios de integridad son factoriales, consulte el contraejemplo . Un anillo euclidiano siempre es factorial [82] .

Existe otra generalización más limitada del concepto de número primo, llamada elemento primo [80] .

Un elemento distinto de cero del dominio de integridad se llama simple si no es un divisor de unidades y el producto puede ser divisible por solo si al menos uno de los elementos o es divisible por . $pags$ $abdominales$ $pags$ $a$ $b$ $pags$

Un elemento primo es siempre irreducible. De hecho, si el elemento es simple y luego, por la definición de un elemento simple, uno de los factores, que sea divisible por , es decir , entonces o, reduciendo por (en el dominio de integridad, la reducción de un factor distinto de cero siempre es posible) : es decir, es un divisor de la unidad. ■ $pags$ ${\ estilo de visualización p = ab,}$ $a,$ $pags,$ ${\ estilo de visualización a = pq.}$ $p=ab=pqb$ $pags$ ${\ estilo de visualización 1 = qb,}$ $b$

Lo contrario no es cierto en general; un elemento irreducible puede no ser simple si el anillo no es factorial. Ejemplo [83] : Considere un anillo de números de la forma donde son enteros. El número 3 en él es irreducible, ya que solo tiene 4 divisores: . Sin embargo, no es un elemento simple, como lo demuestra la igualdad: $a+b{\sqrt {5}}i,$ $a, b$ ${\ estilo de visualización 3,1,-3,-1}$

\left(2+{\sqrt {5}}i\right)\left(2-{\sqrt {5}}i\right)=9

El número 3 divide el lado derecho de la igualdad, pero no divide ninguno de los factores. Podemos concluir de este hecho que el anillo en cuestión no es factorial; y, de hecho, la igualdad muestra que la factorización en factores irreducibles en este anillo no es única. $6=2\cdot 3=(1-i{\sqrt {5)))(1+i{\sqrt {5)))$

Ejemplos

El anillo de los enteros es factorial. Como se mencionó anteriormente, tiene dos divisores de unidades.

Enteros gaussianos

El anillo de números gaussianos consta de números complejos de la forma donde son números enteros. Hay cuatro divisores de la unidad: este anillo es factorial, los elementos irreducibles son la fracción de primos ordinarios y "gaussianos simples" (por ejemplo, ). Ver criterio de primalidad del número gaussiano . ${\ estilo de visualización a + bi,}$ $a, b$ $1;-1;i;-i.$ $1+i$

Un ejemplo de descomposición para el número 2, que no es simple en el anillo de los números gaussianos: - la no unicidad de la descomposición aquí es evidente, ya que está asociada con , según la igualdad: ${\ estilo de visualización 2 = (1 + i) (1-i) = i (1-i) (1-i)}$ $1-yo$ $1+i$ $1-i=(-i)(1+i).$

enteros de Eisenstein

El anillo de enteros de Eisenstein consta de números complejos de la siguiente forma [84] : $\mathbb {Z} [\omega]$

z=a+b\omega ,

donde son números enteros, ( raíz cúbica de la unidad ),

a, b

\omega ={\frac {1}{2}}(-1+i{\sqrt {3}})=e^{2\pi i/3}

Este anillo tiene seis divisores unitarios: (±1, ±ω, ±ω 2 ), es euclidiano y por lo tanto factorial. Los elementos irreducibles (también son elementos simples) de un anillo se llaman números primos de Eisenstein.

Criterio de primacía : un número entero de Eisenstein es un primo de Eisenstein si y solo si se cumple una de las siguientes condiciones mutuamente excluyentes: ${\ estilo de visualización z = a + b \ omega}$

$z$ asociado a un número primo natural de la forma ${\ estilo de visualización 3n-1.}$
${\displaystyle |z|^{2}=a^{2}-ab+b^{2))$ (norma ) es un primo natural de la forma o . $z$ $3n$ $3n+1$

Esto implica que la norma de cualquier número entero de Eisenstein es un número natural primo o el cuadrado de un número natural primo [84] .

Los números asociados o complejos conjugados con primos de Eisenstein también son primos de Eisenstein.

Anillo de polinomios

De gran importancia en álgebra es el anillo de polinomios formado por polinomios con coeficientes de un cierto campo Los divisores de la unidad son aquí constantes distintas de cero (como polinomios de grado cero). El anillo polinomial es euclidiano y por lo tanto factorial. Si tomamos como campo el campo de los números reales , entonces todos los polinomios de 1er grado y aquellos polinomios de 2do grado que no tienen raíces reales (es decir, su discriminante es negativo) serán irreducibles [85] . $k[x]$ $k$ $k$

Véase también

Notas

↑ 1 2 3 Número primo // Enciclopedia matemática (en 5 volúmenes) . - M .: Enciclopedia soviética , 1977. - T. 4.
↑ 1 2 " Argumentos a favor y en contra de la primalidad de 1 Archivado el 24 de febrero de 2021 en Wayback Machine " .
↑ Secuencia A000040 en OEIS . Véase también la lista de números primos
↑ Gardner, Martín . De Penrose Tiles a Cifrados Fuertes = Penrose Tiles a Trapdoor Ciphers / per. De inglés. Yu. A. Danilova. - M. : [[Mir (editorial) |]], 1993. - 416 p. — 10.000 copias. — ISBN 5-03-001991-X .
↑ (francés) Préhistoire de la géométrie: le problème des source (PDF) (enlace no disponible) . Sitio de l'IREM de La Reunión. Voir aussi "Les fables d'Ishango, ou l'irrésistible tentation de la mathématique-fiction" Archivado el 22 de diciembre de 2017 en Wayback Machine , analizar par O. Keller sur Bibnum
↑ Fracciones de unidades egipcias // Mathpages. Archivado desde el original el 1 de abril de 2016.
↑ 1 2 Rybnikov K. Ediciones rusas de "Comienzos" de Euclides // Avances en las ciencias matemáticas . - Academia Rusa de Ciencias , 1941. - No. 9 . - S. 318-321 . (Ruso)
↑ John J. O'Connor, Edmund F. Robertson. Números primos (inglés) . MacTutor .
↑ Lista de números primos de Mersenne conocidos . Gran búsqueda de Internet Mersenne Prime . Archivado desde el original el 15 de marzo de 2016. (indefinido)
↑ 1 2 3 Apostol, Tom M. Introducción a la teoría analítica de números . - Nueva York: Springer-Verlag, 1976. - xii, 338 páginas p. — ISBN 0387901639 . Archivado el 28 de abril de 2020 en Wayback Machine .
↑ 1 2 3 Du Sautoy, Marcus. L'enigma dei numeri primi . - Milán: Rizzoli, 2005. - 606 p. Con. — ISBN 8817008435 .
↑ 1 2 3 Menezes, AJ (Alfred J.), 1965-. Manual de criptografía aplicada . - Boca Ratón: CRC Press, 1997. - xxviii, 780 páginas p. — ISBN 9780849385230 .
↑ 1 2 Ishmukhametov Sh. T. Métodos de factorización de números naturales: libro de texto // Kazan: Universidad de Kazan. - 2011. - S. 190 .
↑ Dudley, Underwood (1978), Teoría elemental de números (2.ª ed. ) , WH Freeman and Co., ISBN 978-0-7167-0076-0 , Sección 2, Teorema 2
↑ Véase, por ejemplo, el comentario de David E. Joyce sobre Elementos (Euclides) , Libro VII, definiciones 1 y 2 Archivado el 5 de agosto de 2011 en Wayback Machine .
↑ 1 2 3 ¿Por qué el número uno no es primo? (de la lista de preguntas frecuentes de Prime Pages) por Chris K. Caldwell. Archivado el 19 de abril de 2015 en Wayback Machine .
↑ Véase, por ejemplo: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160-188. Observaciones de variaciones alrededor de series infinitas, Teorema 19, p.187. Archivado el 5 de octubre de 2013 en Wayback Machine .
↑ Derbyshire, John (2003), The Prime Number Theorem, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics , Washington, DC: Joseph Henry Press, p. 33, ISBN 978-0-309-08549-6 , OCLC 249210614
↑ David Gries, Jayadev Misra. Un algoritmo de tamiz lineal para encontrar números primos. — 1978.
↑ Knuth, Donald Ervin, 1938-. El arte de la programación de computadoras . - Lectura, Massachusetts: Addison-Wesley Pub. Co, ©1973-©1981. - 4 volúmenes pág. — ISBN 0201896842 . Archivado el 15 de junio de 2020 en Wayback Machine .
↑ 1 2 Vasilenko, ON (Oleg Nikolaevich). Teoretiko-chislovye algoritmy v kriptografii . — Moscú: MT︠S︡NMO. Moskovskiĭ t︠s︡entr nepreryvnogo matematicheskogo obrazovanii︠a︡, 2006. — 333 páginas p. — ISBN 5940571034 .
↑ B. Schneier. Criptografía aplicada. - S. 296-300.
↑ Kormen T., Leiser Ch . Algoritmos. Construcción y análisis. - M. : MTSNMO, 2002. - S. 765-772.
↑ Crandall R., Pomerance C. Números primos: una perspectiva computacional. — Springer, 2005.
↑ Introducción a los algoritmos . — 2ª ed. - Cambridge, Mass.: MIT Press, 2001. - xxi, 1180 páginas p. — ISBN 0262032937 . Archivado el 29 de enero de 2010 en Wayback Machine .
↑ 1 2 3 4 Nesterenko Yu. V. Introducción a la criptografía. - Pedro, 2001. - 288 p.
↑ Chris Caldwell. El primo más grande conocido por año: una breve historia (inglés) . Las páginas principales . Consultado el 8 de marzo de 2010. Archivado desde el original el 19 de agosto de 2013.
↑ Jitsuro Nagura. Sobre el intervalo que contiene al menos un número primo (EN) // Actas de la Academia de Japón. - 1952. - T. 28 , núm. 4 . - S. 177-181 . — ISSN 0021-4280 . -doi : 10.3792 / pja/1195570997 . Archivado desde el original el 17 de noviembre de 2017.
↑ Carta archivada el 11 de junio de 2015 en Wayback Machine en latín de Goldbach a Euler, julio de 1730.
↑ Registros de números primos por año . Consultado el 8 de marzo de 2010. Archivado desde el original el 19 de agosto de 2013. (indefinido)
↑ Starr, Michelle . Se ha descubierto el número primo más grande hasta la fecha y nos está dañando el cerebro , ScienceAlert . Archivado desde el original el 6 de enero de 2018. Consultado el 6 de enero de 2018.
↑ EFF Cooperative Computing Awards Archivado el 9 de noviembre de 2008 en Wayback Machine .
↑ Julia Rudy. Un profesor de los EE. UU. ha determinado el número primo más grande . Vesti.Ru (7 de febrero de 2013). Consultado el 25 de febrero de 2018. Archivado desde el original el 26 de febrero de 2018. (indefinido)
↑ 1 2 Secuencia A001348 en OEIS
↑ Secuencia OEIS A000668 : primos de Mersenne
↑ Secuencia A000215 en OEIS
↑ Keller, Wilfrid (15 de febrero de 2015), Factores primos de los números de Fermat , < http://www.prothsearch.net/fermat.html#Summary > . Consultado el 1 de marzo de 2016. Archivado el 10 de febrero de 2016 en Wayback Machine .
↑ Violant-y-Holtz, Albert. Misterio de la granja. Un desafío de tres siglos para las matemáticas. - M. : De Agostini, 2014. - S. 78. - 151 p. — (El Mundo de las Matemáticas: en 45 volúmenes, tomo 9). — ISBN 978-5-9774-0625-3 .
↑ Secuencia OEIS A003261 _
↑ Secuencia OEIS A050918 : Woodall primos
↑ Secuencia OEIS A002064 _
↑ Secuencia OEIS A050920 : primos Cullen
↑ Secuencia OEIS A080075 _
↑ John Brillhart ; Derrick Henry Lehmer ; Juan Selfridge . Nuevos criterios de primalidad y factorizaciones de 2^m ± 1 // Matemáticas de computación : diario. - 1975. - Abril ( vol. 29 ). - Pág. 620-647 . -doi : 10.1090/ S0025-5718-1975-0384673-1 .
↑ Secuencia OEIS A080076 : Proth primos
↑ Caldwell, Chris K. & Cheng, Yuanyou (2005), Determinación de la constante de Mills y una nota sobre el problema de Honaker , Journal of Integer Sequences Vol . 8 (5.4.1) , < http://www.cs.uwaterloo.ca /journals/JIS/VOL8/Caldwell/caldwell78.html > Archivado el 5 de junio de 2011 en Wayback Machine .
↑ Dudley, Underwood (1978), Teoría elemental de números (2.ª ed. ) , WH Freeman and Co., ISBN 978-0-7167-0076-0 , Sección 2, Lema 5
↑ 1 2 3 Stepanov S. A. Comparaciones . - M. : "Conocimiento", 1975. - 64 p.
↑ Vinberg, 2008 , pág. 43.
↑ 1 2 Kurosh A. G. Teoría de grupos. 3.ª ed., M.: Nauka, 1967.
↑ AI Kostrikin. Introducción al Álgebra, Parte III. Moscú: Fizmatlit, 2001.
↑ 1 2 3 Vinogradov I. M. Fundamentos de la teoría de números . - 5ª ed.- M. - L .: Gostekhizdat, 1952.
↑ Chris Caldwell, el postulado de Bertrand. Archivado el 22 de diciembre de 2017 en el glosario de Wayback Machine en Prime Pages .
↑ 1 2 3 4 5 6 7 Diccionario enciclopédico de un joven matemático, 1985 .
↑ Prueba . Un número impar p que no es un múltiplo de 3 es igual a 1 o 2 mod 3 y es igual a 1, 3, 5 o 7 mod 8. Elevando al cuadrado da 1 mod 3 y 1 mod 8. Restar 1 da 0 mod módulo 3 y 0 módulo 8. Por lo tanto, un múltiplo de 3 y un múltiplo de 8; por lo tanto es múltiplo de 24 $p^{2}-1$
↑ Weisstein, Eric W. Green-Tao Theorem en el sitio web de Wolfram MathWorld .
↑ Estas 2 propiedades se derivan directamente de las fórmulas de expansión para la suma y diferencia de grados
↑ Diccionario enciclopédico de un joven matemático, 1985 , p. 332.
↑ 1 2 Graham, Ronald L. (1935-). Konkretnaâ matematika : osnovanie informatiki . - Moscú: Editorial "Mir", 1998. - 703, [1] s. Con. — ISBN 5030017933 .
↑ Sandifer, Charles Edward, 1951-. Las primeras matemáticas de Leonhard Euler . — Washington, DC: Asociación Matemática de América, 2007. — xix, 391 páginas p. — ISBN 0883855593 .
↑ Bach, Eric. Teoría algorítmica de números . — Cambridge, Mass.: MIT Press, ©1996-. - volúmenes <1> s. — ISBN 0262024055 .
↑ WR Alford, Andrew Granville, Carl Pomerance. Hay infinitamente muchos números de Carmichael // Annals of Mathematics. - 1994. - T. 139 , núm. 3 . - S. 703-722 . -doi : 10.2307/ 2118576 . Archivado desde el original el 26 de febrero de 2019.
↑ Charles C. Sims. Enumeración de grupos p // Actas de la London Mathematical Society. — 1965-01-01. — vol. s3-15 , edición . 1 . - pág. 151-166 . — ISSN 1460-244X . -doi : 10.1112 / plms/s3-15.1.151 . Archivado desde el original el 23 de diciembre de 2017.
↑ Jacobson, Nathan, 1910-1999. Álgebra básica . — 2.ª ed., edición de Dover. - Mineola, NY: Dover Publications, 2009. - 2 volúmenes p. — ISBN 9780486471877 .
↑ Sagalovich Yu.L. Introducción a los códigos algebraicos . - 2011. - 302 págs. Archivado el 25 de diciembre de 2017 en Wayback Machine .
↑ Ferguson, Niels. criptografía práctica . - Nueva York: Wiley, 2003. - xx, 410 páginas p. — ISBN 0471223573 . Archivado el 10 de junio de 2009 en Wayback Machine .
↑ W. Diffie, M. Hellman. Nuevas direcciones en criptografía // IEEE Transactions on Information Theory. - noviembre de 1976. - T. 22 , núm. 6 _ - S. 644-654 . — ISSN 0018-9448 . -doi : 10.1109/ tit.1976.1055638 . Archivado desde el original el 28 de diciembre de 2017.
↑ Bakhtiari, Maarof, 2012 , pág. 175.
↑ Boneh D. Veinte años de ataques al RSA Cryptosystem // Notices Amer . Matemáticas. soc. / F. Morgan - AMS , 1999. - vol. 46, edición. 2.- Pág. 203-213. — ISSN 0002-9920 ; 1088-9477
↑ 1 2 RSA Laboratories, The RSA Factoring Challenge Archivado {{{2}}}. . Publicado el 18 de mayo de 2007.
↑ Jones JP, Sato D., Wada H., Wiens D. Representación diofántica del conjunto de números primos // Amer . Matemáticas. Lun. : diario. - 1976. - vol. 83 , núm. 6 _ - Pág. 449-464 . Archivado desde el original el 31 de marzo de 2010.
↑ Yuri Matiyasevich, Ecuaciones diofánticas en el siglo XX (enlace inaccesible)
↑ Polinomio de Matijasevic Archivado el 6 de agosto de 2010 en Wayback Machine . El glosario principal.
↑ Weisstein, Problemas de Eric W. Landau en el sitio web Wolfram MathWorld .
↑ Un matemático desconocido hace un gran avance en la teoría de los números primos gemelos . Fecha de acceso: 20 de mayo de 2013. Archivado desde el original el 7 de junio de 2013. (indefinido)
↑ Brechas acotadas entre números primos . Consultado el 21 de mayo de 2013. Archivado desde el original el 18 de mayo de 2013. (indefinido)
↑ Weisstein, Eric W. Legendre's Hypothesis (inglés) en el sitio web de Wolfram MathWorld .
↑ Generalización a semigrupos arbitrarios , véase el libro de Kurosh.
↑ Van der Waerden, 2004 , pág. 75.
↑ 12 Kurosh , 1973 , pág. 82-83.
↑ Leng, 1967 , pág. 89.
↑ Van der Waerden, 2004 , pág. 77-78.
↑ William W. Adams, Larry Joel Goldstein (1976), Introducción a la teoría de números, p. 250, Prentice-Hall, Inc., ISBN 0-13-491282-9
↑ 1 2 Eisenstein Integer--de MathWorld . Consultado el 23 de diciembre de 2017. Archivado desde el original el 15 de diciembre de 2020. (indefinido)
↑ Vinberg E. B. Álgebra de polinomios. - M. : Educación, 1980. - S. 122-124. — 176 pág.

Literatura

Van der Waerden . Álgebra. Definiciones, teoremas, fórmulas. - San Petersburgo. : Lan, 2004. - 624 p. — ISBN 5-8114-0552-9 .
Vasilenko O. N. Algoritmos teóricos de números en criptografía . - M. : MTSNMO , 2003. - 328 p. — ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
El pequeño teorema de Vinberg EB Fermat y sus generalizaciones // Matem. iluminación - M. : Editorial del MTSNMO , 2008. - T. 12. - S. 43-53.
Galperin G. Solo sobre números primos // Kvant . - N º 4 . - S. 9-14.38 .
Henry S. Warren, Jr. Capítulo 16. Fórmulas para números primos // Trucos algorítmicos para programadores = Hacker's Delight. - M. : "Williams", 2007. - 288 p. — ISBN 0-201-91465-4 .
Karpushina N. Palíndromos y "cambiadores" entre números primos // Ciencia y Vida . - 2010. - Nº 5 . (Ruso)
Kordemsky B. A. Ingenio matemático . - M. : GIFML, 1958. - 576 p.
Kormen T., Leiser C. Capítulo 33.8. Comprobación de números por simplicidad // Algoritmos. Construcción y Análisis . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R. , Pomerance K. Números primos. Aspectos criptográficos y computacionales = Números primos: una perspectiva computacional. — M. : URSS , Librocom, 2011. — 664 p. - ISBN 978-5-397-02060-2 .
Kurosh A.G. Clases de álgebra general. - 2ª ed.- Nauka, 1973.
Leng S. Álgebra. — M .: Mir, 1967.
Matiyasevich Yu . Fórmulas para números primos // Kvant . - 1975. - Nº 5 . - S. 5-13 .
Nesterenko Yu. V. Problemas algorítmicos de teoría de números // Introducción a la criptografía / Editado por V. V. Yashchenko. - Pedro, 2001. - 288 p. - ISBN 5-318-00443-1 .
Zager D. Los primeros 50 millones de primos // Avances en Ciencias Matemáticas . - Academia Rusa de Ciencias , 1984. - T. 39 , No. 6 (240) . - S. 175-190 . (Ruso)
Cheryomushkin A. V. Conferencias sobre algoritmos aritméticos en criptografía . - M. : MTSNMO , 2002. - 104 p. - 2000 copias. — ISBN 5-94057-060-7 . Archivado desde el original el 31 de mayo de 2013. .
Número primo // Diccionario enciclopédico de un joven matemático / Comp. A. P. Savin. - M .: Pedagogía , 1985. - S. 262 -263. — 352 págs.
Enrique Gracien. Números simples. Largo camino al infinito. - De Agostini, 2014. - T. 3. - 148 p. — (Mundo de las Matemáticas). - ISBN 978-5-9774-0682-6 . - ISBN 978-5-9774-0637-6 .
Bakhtiari M. , Maarof M. A. Seria debilidad de seguridad en RSA Cryptosystem (inglés) // IJCSI - 2012. - Vol. 9, edición. 1, nº 3. - Pág. 175-178. — ISSN 1694-0814 ; 1694-0784
Crandall R., Pomerance C. Capítulo 3. Reconocimiento de números primos y compuestos. Capítulo 4. "Demostración de primalidad" // Números primos: una perspectiva computacional . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .

Enlaces

Knop K. En busca de la simplicidad .
Prime Pages es una base de datos de los primos más grandes conocidos .
Geometría de Números Primos y Perfectos (Español) .
Guión de visualización
Foro de buscadores principales .

diccionarios y enciclopedias

En catálogos bibliográficos
BNF : 11932592t TIERRA : 4047263-2 J9U : 987007538747905171 LCCN : sh85093218 LNB : 000232578 NDL : 00571462 NKC : ph139050

Sistemas numéricos
Conjuntos contables	Números naturales ( ) $\scriptstyle \mathbb {N}$ Enteros ( ) $\scriptstyle \mathbb {Z}$ Racional ( ) $\scriptstyle \mathbb {Q}$ algebraico ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Períodos Calculable Aritmética
Números reales y sus extensiones.	reales ( ) $\scriptstyle \mathbb {R}$ Complejo ( ) $\scriptstyle \mathbb {C}$ Cuaterniones ( ) $\scriptstyle \mathbb {H}$ Números de Cayley (octavas, octoniones) ( ) $\scriptstyle \mathbb {O}$ Sedeniones ( ) $\scriptstyle \mathbb {S}$ Alterniones Doble Hipercomplejo superrealista hipermaterial surrealista
Herramientas de extensión numérica	procedimiento de Cayley-Dixon teorema de frobenius teorema de Hurwitz
Otros sistemas numéricos	Numeros cardinales Números ordinales (transfinitos, ordinales) p-ádico Números sobrenaturales números de intervalo
ver también	números dobles Numeros irracionales numeros trascendentales haz de números bicuaternión

Números por características de divisibilidad
Información general	Factorización de números enteros Divisibilidad divisor unitario Función divisoria número primo Teorema fundamental de la aritmética número aritmético
Formas de factorización	número primo Número compuesto Semiprima número rectangular número esfénico Número sin cuadrados múltiplo completo grado perfecto numero de aquiles número suave número normal número aproximado número inusual
Con divisores limitados	número perfecto Cifras ligeramente insuficientes Números ligeramente redundantes número multiperfecto Números hemiperfectos número hiperperfecto número súper perfecto primo unitario número semiperfecto número pararítmico Número de Erdős-Nicolas
Números con muchos divisores	exceso de números Exceso de números primitivos Números altamente redundantes Números superredundantes Números enormemente redundantes número supercompuesto Un número altamente supercompuesto número extraño
Relacionado con secuencias alícuotas	número sagrado números amistosos números públicos Números casi amigables
Otro	No hay suficientes números números de amigos numeros sublimados Números de mineral número humilde Dígitos iguales número extravagante