Mersenne prima

Número primo de la forma (2^n)-1

En matemáticas , un primo de Mersenne es un número primo que es uno menos que una potencia de dos . Es decir, es un número primo de la forma M _n = 2 ⁿ − 1 para algún número entero n . Llevan el nombre de Marin Mersenne , un fraile mínimo francés , que los estudió a principios del siglo XVII. Si n es un número compuesto , entonces también lo es 2 ⁿ − 1 . Por lo tanto, una definición equivalente de los primos de Mersenne es que son números primos de la forma Mp = 2 _p ⁻ 1 para algún primo p .

Los exponentes n que dan números primos de Mersenne son 2, 3, 5, 7, 13, 17, 19, 31,... (secuencia A000043 en el OEIS ) y los números primos de Mersenne resultantes son 3 , 7 , 31 , 127 , 8191, 131071, 524287, 2147483647 , ... (secuencia A000668 en el OEIS ).

Los números de la forma M _n = 2 ⁿ − 1 sin el requisito de primalidad pueden denominarse números de Mersenne . A veces, sin embargo, los números de Mersenne se definen con el requisito adicional de que n sea primo. El número de Mersenne compuesto más pequeño con exponente primo n es 2 ¹¹ − 1 = 2047 = 23 × 89 .

Los números primos de Mersenne se estudiaron en la antigüedad debido a su estrecha conexión con los números perfectos: el teorema de Euclides-Euler afirma una correspondencia uno a uno entre los números pares perfectos y los números primos de Mersenne. Muchos de los números primos más grandes conocidos son primos de Mersenne porque es más fácil comprobar la primalidad de los números de Mersenne.

En 2023 ^[árbitro], se conocen 51 primos de Mersenne. El mayor número primo conocido , 2 ^82.589.933 − 1 , es un primo de Mersenne. ^[1] Desde 1997, todos los números primos de Mersenne recién encontrados han sido descubiertos por Great Internet Mersenne Prime Search , un proyecto de computación distribuida . En diciembre de 2020 se alcanzó un hito importante en el proyecto después de que se comprobaran al menos una vez todos los exponentes inferiores a 100 millones. ^[2]

Acerca de los primos de Mersenne

Problema no resuelto en matemáticas :

¿Hay infinitos números primos de Mersenne?

(más problemas sin resolver en matemáticas)

Muchas cuestiones fundamentales sobre los números primos de Mersenne siguen sin resolverse. Ni siquiera se sabe si el conjunto de los números primos de Mersenne es finito o infinito.

La conjetura de Lenstra-Pomerance-Wagstaff afirma que hay infinitos números primos de Mersenne y predice su orden de crecimiento y frecuencia: por cada número n, debería haber en promedio alrededor de ≈ 5,92 primos p con n dígitos decimales (es decir, 10 ^n-1 < p < 10 ⁿ ) para el cual es primo. ${\displaystyle e^{\gamma }\cdot \log _{2}(10)}$ ${\displaystyle M_{p}}$

Tampoco se sabe si una infinidad de números de Mersenne con exponentes primos son compuestos, aunque esto se derivaría de conjeturas ampliamente aceptadas sobre números primos, por ejemplo, la infinitud de los primos de Sophie Germain congruentes con 3 ( mod 4 ). Para estos primos p , 2 p + 1 (que también es primo) dividirá a M _p , por ejemplo, 23 | M ₁₁ , 47 | M ₂₃ , 167 | M ₈₃ , 263 | M ₁₃₁ , 359 | M ₁₇₉ , 383 | M ₁₉₁ , 479 | M ₂₃₉ y 503 | M ₂₅₁ (secuencia A002515 en la OEIS ). Dado que para estos primos p , 2 p + 1 es congruente con 7 mod 8, entonces 2 es un residuo cuadrático mod 2 p + 1 , y el orden multiplicativo de 2 mod 2 p + 1 debe dividir . Dado que p es primo, debe ser p o 1. Sin embargo, no puede ser 1 ya que y 1 no tiene factores primos , por lo que debe ser p . Por tanto, 2 p + 1 divide y no puede ser primo. Los primeros cuatro primos de Mersenne son M ₂ = 3 , M ₃ = 7 , M ₅ = 31 y M ₇ = 127 y debido a que el primer primo de Mersenne comienza en M ₂ , todos los primos de Mersenne son congruentes con 3 (mod 4). Aparte de M ₀ = 0 y M ₁ = 1 , todos los demás números de Mersenne también son congruentes con 3 (mod 4). En consecuencia, en la factorización prima de un número de Mersenne (  ≥ M ₂  ) debe haber al menos un factor primo congruente con 3 (mod 4). ${\textstyle {\frac {(2p+1)-1}{2}}=p}$ ${\displaystyle \Phi _{1}(2)=1}$ ${\displaystyle \Phi _{p}(2)=2^{p}-1}$ ${\displaystyle 2^{p}-1=M_{p}}$

Un teorema básico sobre los números de Mersenne establece que si M _p es primo, entonces el exponente p también debe ser primo. Esto se desprende de la identidad

$${\displaystyle {\begin{aligned}2^{ab}-1&=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\cdots +2^{(b-1)a}\right)\\&=(2^{b}-1)\cdot \left(1+2^{b}+2^{2b}+2^{3b}+\cdots +2^{(a-1)b}\right).\end{aligned}}}$$

M ₄ = 2 ⁴ − 1 = 15 = 3 × 5 = (2 ² − 1) × (1 + 2 ² )

Aunque los ejemplos anteriores podrían sugerir que Mp es primo para todos los primos p , este no es el caso y el contraejemplo más pequeño es el número de Mersenne _.

METRO ₁₁ = 2 ¹¹ - 1 = 2047 = 23 × 89 .

La evidencia disponible sugiere que es mucho más probable que un número de Mersenne seleccionado al azar sea primo que un entero impar arbitrariamente seleccionado al azar de tamaño similar. ^[3] No obstante, los valores primos de _Mp parecen volverse cada vez más escasos a medida que aumenta p . Por ejemplo, ocho de los primeros 11 primos p dan lugar a un primo de Mersenne _Mp ( los términos correctos en la lista original de Mersenne), mientras que Mp _es primo para sólo 43 de los primeros dos millones de números primos (hasta 32.452.843).

La falta actual de una prueba sencilla para determinar si un número de Mersenne dado es primo hace que la búsqueda de números primos de Mersenne sea una tarea difícil, ya que los números de Mersenne crecen muy rápidamente. La prueba de primalidad de Lucas-Lehmer (LLT) es una prueba de primalidad eficiente que ayuda enormemente en esta tarea, haciendo que sea mucho más fácil probar la primalidad de los números de Mersenne que la de la mayoría de los otros números del mismo tamaño. La búsqueda del mayor número primo conocido tiene una especie de culto . ^{[ cita necesaria ]} En consecuencia, se ha gastado una gran cantidad de potencia informática buscando nuevos números primos de Mersenne, gran parte de la cual ahora se realiza mediante computación distribuida .

El módulo aritmético de un número de Mersenne es particularmente eficiente en una computadora binaria , lo que los convierte en opciones populares cuando se desea un módulo primo, como el generador de números aleatorios de Park-Miller . Para encontrar un polinomio primitivo de orden numérico de Mersenne es necesario conocer la factorización de ese número, por lo que los primos de Mersenne permiten encontrar polinomios primitivos de orden muy alto. Estos trinomios primitivos se utilizan en generadores de números pseudoaleatorios con períodos muy grandes, como el tornado de Mersenne , el registro de desplazamiento generalizado y los generadores de Fibonacci retrasados .

numeros perfectos

_{Los primos de} Mersenne Mp están estrechamente relacionados con los números perfectos . En el siglo IV a.C., Euclides demostró que si 2 ^p − 1 es primo, entonces 2 ^{p − 1} (2 ^p − 1 ) es un número perfecto. En el siglo XVIII, Leonhard Euler demostró que, por el contrario, todos los números pares perfectos tienen esta forma. ^[4] Esto se conoce como teorema de Euclides-Euler . Se desconoce si existen números perfectos impares .

Historia

Los primos de Mersenne toman su nombre del erudito francés del siglo XVII Marin Mersenne , quien compiló lo que se suponía era una lista de primos de Mersenne con exponentes hasta 257. Los exponentes enumerados por Mersenne en 1644 fueron los siguientes:

2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

Su lista replicaba los primos conocidos de su época con exponentes hasta 19. Su siguiente entrada, 31, era correcta, pero la lista se volvió en gran medida incorrecta, ya que Mersenne incluyó por error M ₆₇ y M ₂₅₇ (que son compuestos) y omitió M _61. , M ₈₉ y M ₁₀₇ (que son primos). Mersenne dio pocos indicios de cómo llegó a esa lista. ^[5]

Édouard Lucas demostró en 1876 que M ₁₂₇ es efectivamente primo, como afirmó Mersenne. Este fue el número primo más grande conocido durante 75 años hasta 1951, cuando Ferrier encontró un número primo más grande, usando una máquina calculadora de escritorio. ^{[6] : página 22} Ivan Mikheevich Pervushin determinó que M ₆₁ era primo en 1883 , aunque Mersenne afirmó que era compuesto, y por esta razón a veces se le llama número de Pervushin. Este era el segundo número primo más grande conocido y permaneció así hasta 1911. Lucas había mostrado otro error en la lista de Mersenne en 1876 al demostrar que M ₆₇ era compuesto sin encontrar un factor. No se encontró ningún factor hasta una famosa charla de Frank Nelson Cole en 1903. ^[7] Sin decir una palabra, fue a una pizarra y elevó 2 a la potencia 67, luego restó uno, lo que resultó en el número 147,573,952,589,676,412,927 . Del otro lado del tablero, multiplicó 193.707.721 × 761.838.257.287 y obtuvo el mismo número, luego regresó a su asiento (entre aplausos) sin hablar. ^[8] Más tarde dijo que el resultado le había llevado "tres años de domingos" para encontrarlo. ^[9] Se completó y verificó rigurosamente una lista correcta de todos los primos de Mersenne en este rango numérico sólo unos tres siglos después de que Mersenne publicara su lista. ${\displaystyle (2^{148}+1)/17}$

Buscando números primos de Mersenne

Se encuentran disponibles algoritmos rápidos para encontrar primos de Mersenne y, a partir de junio de 2023 ^[actualizar], los seis números primos más grandes conocidos son primos de Mersenne.

Los primeros cuatro primos de Mersenne M ₂ = 3 , M ₃ = 7 , M ₅ = 31 y M ₇ = 127 eran conocidos en la antigüedad. El quinto, M ₁₃ = 8191 , fue descubierto de forma anónima antes de 1461; los dos siguientes ( M ₁₇ y M ₁₉ ) fueron encontrados por Pietro Cataldi en 1588. Después de casi dos siglos, Leonhard Euler verificó que M ₃₁ era primo en 1772. El siguiente (en orden histórico, no numérico) fue M ₁₂₇ , encontrado por Édouard Lucas en 1876, luego M ₆₁ por Ivan Mikheevich Pervushin en 1883. Dos más ( M ₈₉ y M ₁₀₇ ) fueron encontrados a principios del siglo XX, por RE Powers en 1911 y 1914, respectivamente.

El método más eficaz conocido actualmente para probar la primalidad de los números de Mersenne es la prueba de primalidad de Lucas-Lehmer . Específicamente, se puede demostrar que para primo p > 2 , M _p = 2 ^p − 1 es primo si y solo si M _p divide a S _{p − 2} , donde S ₀ = 4 y S _k = ( S _{k − 1} ) ² − 2 para k > 0 .

Durante la era del cálculo manual, todos los exponentes hasta 257 inclusive se probaron con la prueba de Lucas-Lehmer y se encontró que eran compuestos. Horace Scudder Uhler, profesor jubilado de física de Yale, hizo una contribución notable, quien hizo los cálculos para los exponentes 157, 167, 193, 199, 227 y 229. ^[10] Desafortunadamente para esos investigadores, el intervalo que estaban probando contiene el intervalo más grande conocido. brecha relativa entre los primos de Mersenne: el siguiente exponente primo de Mersenne, 521, resultaría ser más de cuatro veces mayor que el récord anterior de 127.

Gráfico del número de dígitos del primo de Mersenne más grande conocido por año: era electrónica. La escala vertical es logarítmica en el número de dígitos, siendo así una función en el valor del primo. ${\displaystyle \log(\log(y))}$

La búsqueda de los números primos de Mersenne se vio revolucionada con la introducción de la computadora digital electrónica. Alan Turing los buscó en el Manchester Mark 1 en 1949, ^[11] pero la primera identificación exitosa de un primo de Mersenne, M ₅₂₁ , por este medio se logró a las 10:00 pm del 30 de enero de 1952, utilizando la Oficina Nacional de EE. UU. de Standards Western Automatic Computer (SWAC) en el Instituto de Análisis Numérico de la Universidad de California, Los Ángeles , bajo la dirección de DH Lehmer , con un programa de búsqueda informática escrito y dirigido por el Prof. RM Robinson . Fue el primer primo de Mersenne identificado en treinta y ocho años; el siguiente, M ₆₀₇ , fue encontrado por la computadora poco menos de dos horas después.  El mismo programa encontró tres más ( M ₁₂₇₉ , M ₂₂₀₃ y M _{2281 ) en los meses siguientes.} M _4.423 fue el primer número primo descubierto con más de 1000 dígitos, M _44.497 fue el primero con más de 10.000 y M _6.972.593 fue el primero con más de un millón. En general, el número de dígitos en la representación decimal de M _n es igual a ⌊ n × log ₁₀ 2⌋ + 1 , donde ⌊ x ⌋ denota la función suelo (o equivalentemente ⌊log ₁₀ M _n ⌋ + 1 ).

En septiembre de 2008, los matemáticos de la UCLA que participaron en la Gran Búsqueda de Mersenne Prime en Internet (GIMPS) ganaron parte de un premio de 100.000 dólares de la Electronic Frontier Foundation por su descubrimiento de un primo de Mersenne de casi 13 millones de dígitos. El premio, finalmente confirmado en octubre de 2009, es para el primer número primo conocido con al menos 10 millones de dígitos. El principal se encontró en un Dell OptiPlex 745 el 23 de agosto de 2008. Este fue el octavo principal de Mersenne descubierto en UCLA. ^[12]

El 12 de abril de 2009, un registro del servidor GIMPS informó que posiblemente se había encontrado el número 47 de Mersenne Prime. El hallazgo se detectó por primera vez el 4 de junio de 2009 y se verificó una semana después. El primo es 2 ^42,643,801 − 1 . Aunque cronológicamente es el número 47 de Mersenne en ser descubierto, es más pequeño que el más grande conocido en ese momento, que fue el número 45 en ser descubierto.

El 25 de enero de 2013, Curtis Cooper , matemático de la Universidad de Missouri Central , descubrió un número primo de Mersenne número 48, 2 ^{57 885 161} − 1 (un número con 17 425 170 dígitos), como resultado de una búsqueda ejecutada por una red de servidores GIMPS. ^[13]

El 19 de enero de 2016, Cooper publicó su descubrimiento de un número 49 de Mersenne primo, 2 ^74.207.281 - 1 (un número con 22.338.618 dígitos), como resultado de una búsqueda ejecutada por una red de servidores GIMPS. ^{[14] [15] [16]} Este fue el cuarto primo de Mersenne descubierto por Cooper y su equipo en los últimos diez años.

El 2 de septiembre de 2016, Great Internet Mersenne Prime Search terminó de verificar todas las pruebas por debajo de M _37,156,667 , confirmando así oficialmente su posición como el 45º Mersenne Prime. ^[17]

El 3 de enero de 2018, se anunció que Jonathan Pace, un ingeniero eléctrico de 51 años que vivía en Germantown, Tennessee , había encontrado un número primo de Mersenne número 50, 2 ^{77 232 917} − 1 (un número con 23 249 425 dígitos), como resultado de una búsqueda ejecutada por una red de servidores GIMPS. ^[18] El descubrimiento se realizó mediante una computadora en las oficinas de una iglesia en la misma localidad. ^{[19] [20]}

El 21 de diciembre de 2018, se anunció que The Great Internet Mersenne Prime Search (GIMPS) descubrió el número primo más grande conocido, 2 ^{82 589 933} − 1 , con 24 862 048 dígitos. Una computadora ofrecida voluntariamente por Patrick Laroche de Ocala, Florida, hizo el hallazgo el 7 de diciembre de 2018. ^[21]

A finales de 2020, GIMPS comenzó a utilizar una nueva técnica para descartar posibles primos de Mersenne llamada prueba de primo probable (PRP), basada en el desarrollo de Robert Gerbicz en 2017, y una forma sencilla de verificar las pruebas desarrolladas por Krzysztof Pietrzak en 2018. La baja tasa de error y la facilidad de prueba, esto redujo casi a la mitad el tiempo de cálculo para descartar posibles primos en comparación con la prueba de Lucas-Lehmer (ya que dos usuarios ya no tendrían que realizar la misma prueba para confirmar el resultado del otro), aunque los exponentes que pasan la prueba La prueba PRP aún requiere una para confirmar su primalidad. ^[22]

Teoremas sobre los números de Mersenne

1. Si a y p son números naturales tales que a ^p − 1 es primo, entonces a = 2 o p = 1 .
   • Prueba : a ≡ 1 ( mod a − 1) . Entonces a ^p ≡ 1 (mod a − 1) , entonces a ^p − 1 ≡ 0 (mod a − 1) . Por lo tanto a − 1 | un ^pag − 1 . Sin embargo, a ^p − 1 es primo, por lo que a − 1 = a ^p − 1 o a − 1 = ±1 . En el primer caso, a = a ^p , por lo tanto a = 0, 1 (lo cual es una contradicción, ya que ni −1 ni 0 son primos) o p = 1. En el último caso, a = 2 o a = 0 . Sin embargo, si a = 0 , 0 ^p − 1 = 0 − 1 = −1, que no es primo. Por tanto, a = 2 .
2. Si 2 ^p − 1 es primo, entonces p es primo.
   • Prueba : Supongamos que p es compuesto, por lo tanto se puede escribir p = ab con a y b > 1 . Entonces 2 ^p − 1 = 2 ^ab − 1 = (2 ^a ) ^b − 1 = (2 ^a − 1) ( (2 ^a ) ^{b −1} + (2 ^a ) ^{b −2} + ... + 2 ^a + 1 ) entonces 2 ^p − 1 es compuesto. Por contraposición, si 2 ^p − 1 es primo, entonces p es primo.
3. Si p es un primo impar, entonces todo primo q que divide a 2 ^p − 1 debe ser 1 más un múltiplo de 2 p . Esto es válido incluso cuando 2 ^p − 1 es primo.
   • Por ejemplo, 2 ⁵ − 1 = 31 es primo y 31 = 1 + 3 × (2 × 5) . Un ejemplo compuesto es 2 ¹¹ − 1 = 23 × 89 , donde 23 = 1 + (2 × 11) y 89 = 1 + 4 × (2 × 11) .
   • Prueba : Según el pequeño teorema de Fermat , q es un factor de 2 ^{q −1} − 1 . Dado que q es un factor de 2 ^p − 1 , para todos los enteros positivos c , q también es un factor de 2 ^pc − 1 . Dado que p es primo y q no es factor de 2 ¹ − 1 , p también es el entero positivo más pequeño x tal que q es factor de 2 ^x − 1 . Como resultado, para todos los números enteros positivos x , q es un factor de 2 ^x − 1 si y sólo si p es un factor de x . Por lo tanto, dado que q es un factor de 2 ^{q −1} − 1 , p es un factor de q − 1 entonces q ≡ 1 (mod p ) . Además, dado que q es un factor de 2 ^p − 1 , que es impar, q es impar. Por tanto, q ≡ 1 (mod 2 p ) .
   • Este hecho conduce a una prueba del teorema de Euclides , que afirma la infinitud de los números primos, distinta de la prueba escrita por Euclides: para cada primo impar p , todos los primos que dividen a 2 ^p − 1 son mayores que p ; por tanto, siempre hay números primos mayores que cualquier número primo en particular.
   • De este hecho se deduce que para cada primo p > 2 , hay al menos un primo de la forma 2 kp +1 menor o igual a Mp , para algún número entero _k .
4. Si p es un primo impar, entonces todo primo q que divide a 2 ^p − 1 es congruente con ±1 (mod 8) .
   • Prueba : 2 ^{p +1} ≡ 2 (mod q ) , entonces 2^1/2(p+1) es una raíz cuadrada de 2 mod q . Por reciprocidad cuadrática , todo módulo primo en el que el número 2 tiene raíz cuadrada es congruente con ±1 (mod 8) .
5. Un primo de Mersenne no puede ser un primo de Wieferich .
   • Prueba : Demostramos que si p = 2 ^m − 1 es un primo de Mersenne, entonces la congruencia 2 ^{p −1} ≡ 1 (mod p ² ) no se cumple. Según el pequeño teorema de Fermat, m | pag - 1 . Por lo tanto, se puede escribir p − 1 = mλ . Si se satisface la congruencia dada, entonces p ² | 2 ^mλ − 1 , por lo tanto 0 ≡2 ^mλ − 1/2 ^metros - 1 = 1 + 2 ^metro + 2 ^{2 metro} + ... + 2 ^{( λ − 1) metro} ≡ − λ mod (2 ^metro − 1) . Por tanto 2 ^metro − 1 | λ , y por tanto λ ≥ 2 ^m − 1 . Esto lleva a p − 1 ≥ m (2 ^m − 1) , lo cual es imposible ya que m ≥ 2 .
6. Si myn son números naturales, entonces myn son coprimos si y sólo si 2 m − ¹ y 2 ⁿ − 1 son coprimos. En consecuencia, un número primo divide como máximo a un número de Mersenne con exponente primo. ^[23] Es decir, el conjunto de números perniciosos de Mersenne es coprimo por pares.
7. Si p y 2 p + 1 son primos (lo que significa que p es un primo de Sophie Germain ), y p es congruente con 3 (mod 4) , entonces 2 p + 1 divide a 2 ^p − 1 . ^[24]
   • Ejemplo : 11 y 23 son primos y 11 = 2 × 4 + 3 , por lo que 23 divide 2 ¹¹ − 1 .
   • Prueba : Sea q 2 p + 1 . Según el pequeño teorema de Fermat, 2 ^{2 p} ≡ 1 (mod q ) , entonces 2 ^p ≡ 1 (mod q ) o 2 ^p ≡ −1 (mod q ) . Suponiendo que esto último sea cierto, entonces 2 ^{p +1} = (2^{1/2( p + 1)} ) ² ≡ −2 (mod q ) , entonces −2 sería un residuo cuadrático mod q . Sin embargo, dado que p es congruente con 3 (mod 4) , q es congruente con 7 (mod 8) y por lo tanto 2 es un residuo cuadrático mod q . Además, dado que q es congruente con 3 (mod 4) , −1 es un mod q sin residuo cuadrático , entonces −2 es el producto de un residuo y un no residuo y, por tanto, es un no residuo, lo cual es una contradicción. Por lo tanto, la congruencia anterior debe ser verdadera y 2 p + 1 divide a M _p .
8. Todos los divisores compuestos de números de Mersenne con exponente primo son pseudoprimos fuertes en base 2.
9. Con la excepción de 1, un número de Mersenne no puede ser una potencia perfecta. Es decir, y de acuerdo con el teorema de Mihăilescu , la ecuación 2 ^m − 1 = n ^k no tiene soluciones donde m , n y k son números enteros con m > 1 y k > 1 .

Lista de primos de Mersenne conocidos

A partir de 2023 ^[actualizar], los 51 primos de Mersenne conocidos son 2 ^p − 1 para los siguientes p :

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 2170, 1, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 11, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933. (secuencia A000043 en la OEIS )

Factorización de números compuestos de Mersenne

Como son números primos, los primos de Mersenne son divisibles sólo por 1 y por sí mismos. Sin embargo, no todos los números de Mersenne son primos de Mersenne. Los números de Mersenne son muy buenos casos de prueba para el algoritmo de criba de campos numéricos especiales , por lo que a menudo el número más grande factorizado con este algoritmo ha sido un número de Mersenne. A junio de 2019 ^[actualizar], 2 ^1,193 − 1 tiene el récord, ^[25] habiendo sido factorizado con una variante del tamiz de campo numérico especial que permite la factorización de varios números a la vez. Consulte los registros de factorización de números enteros para obtener enlaces a más información. El tamiz de campo numérico especial puede factorizar números con más de un factor grande. Si un número tiene sólo un factor muy grande, entonces otros algoritmos pueden factorizar números más grandes encontrando primero factores pequeños y luego ejecutando una prueba de primalidad en el cofactor. A partir de septiembre de 2022 ^[actualizar], el número completamente factorizado más grande (con probables factores primos permitidos) es 2 ^12,720,787 − 1 = 1,119,429,257 × 175,573,124,547,437,977 × 8,480,999,878,421,106,991 × q , donde q es 3,829,2 Prima probable de 94 dígitos. Fue descubierto por un participante de GIMPS con el sobrenombre de "Funky Waddle". ^{[26] [27]} A partir de septiembre de 2022 ^[actualizar], el número de Mersenne M ₁₂₇₇ es el número de Mersenne compuesto más pequeño sin factores conocidos; no tiene factores primos inferiores a 2 ⁶⁸ , ^[28] y es muy poco probable que tenga factores inferiores a 10 ⁶⁵ (~2 ²¹⁶ ). ^[29]

La siguiente tabla muestra factorizaciones para los primeros 20 números compuestos de Mersenne (secuencia A244453 en OEIS ).

El número de factores para los primeros 500 números de Mersenne se puede encontrar en (secuencia A046800 en OEIS ).

Números de Mersenne en la naturaleza y en otros lugares

En el problema matemático Torre de Hanoi , resolver un rompecabezas con una torre de n discos requiere M _n pasos, suponiendo que no se cometan errores. ^[30] El número de granos de arroz en todo el tablero de ajedrez en el problema del trigo y el tablero de ajedrez es M ₆₄ . ^[31]

El asteroide con el planeta menor número 8191 se llama 8191 Mersenne en honor a Marin Mersenne, porque 8191 es un primo de Mersenne ( 3 Juno , 7 Iris , 31 Euphrosyne y 127 Johanna fueron descubiertos y nombrados durante el siglo XIX). ^[32]

En geometría , un triángulo rectángulo entero que es primitivo y tiene su cateto par una potencia de 2 (  ≥ 4  ) genera un triángulo rectángulo único tal que su inradio es siempre un número de Mersenne. Por ejemplo, si el cateto par es 2 ^{n  + 1} , entonces, debido a que es primitivo, limita el cateto impar a ser 4 ⁿ  - 1 , la hipotenusa a ser 4 ⁿ  + 1 y su inradio a ser 2 ⁿ  - 1 . ^[33]

Primos de Mersenne-Fermat

Un número de Mersenne-Fermat se define como2 ^{p r} − 1/2 ^{p r − 1} − 1 con p primo, r número natural, y puede escribirse como MF( p , r ) . Cuando r = 1 , es un número de Mersenne. Cuando p = 2 , es un número de Fermat . Los únicos primos de Mersenne-Fermat conocidos con r > 1 son

MF(2, 2), MF(2, 3), MF(2, 4), MF(2, 5), MF(3, 2), MF(3, 3), MF(7, 2), y MF(59, 2) . ^[34]

De hecho, MF( p , r ) = Φ _{p ^r} (2) , donde Φ es el polinomio ciclotómico .

Generalizaciones

Los primos de Mersenne generalizados más simples son números primos de la forma f (2 ⁿ ) , donde f ( x ) es un polinomio de bajo grado con coeficientes enteros pequeños . ^[35] Un ejemplo es 2 ⁶⁴ − 2 ³² + 1 , en este caso, n = 32 , y f ( x ) = x ² − x + 1 ; otro ejemplo es 2 ¹⁹² − 2 ⁶⁴ − 1 , en este caso, n = 64 , y f ( x ) = x ³ − x − 1 .

También es natural intentar generalizar los primos de la forma 2 ⁿ − 1 a primos de la forma b ⁿ − 1 (para b ≠ 2 y n > 1 ). Sin embargo (ver también los teoremas anteriores), b ⁿ − 1 siempre es divisible por b − 1 , por lo que, a menos que este último sea una unidad , el primero no es primo. Esto se puede solucionar permitiendo que b sea un número entero algebraico en lugar de un número entero:

Números complejos

En el anillo de los números enteros (en números reales ), si b − 1 es una unidad , entonces b es 2 o 0. Pero 2 ⁿ − 1 son los primos de Mersenne habituales, y la fórmula 0 ⁿ − 1 no conduce a nada. interesante (ya que siempre es −1 para todo n > 0 ). Por lo tanto, podemos considerar un anillo de "enteros" en números complejos en lugar de números reales , como los enteros gaussianos y los enteros de Eisenstein .

Primos gaussianos de Mersenne

Si consideramos el anillo de los enteros gaussianos , obtenemos el caso b = 1 + i y b = 1 − i , y podemos preguntar ( WLOG ) para cuál n el número (1 + i ) ⁿ − 1 es un primo gaussiano que entonces llamarse primo gaussiano de Mersenne . ^[36]

(1 + i ) ⁿ − 1 es un primo gaussiano para el siguiente n :

2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367, 379, 457, 997, 1367, 3041, 10141, 14699, 27529, 49207, 77291, 85237, 106693, 160423, 203789, 364289, 991961, 1203793, 1667321, 3704053, 4792057, ... A057429 en la OEIS )

Al igual que la secuencia de exponentes de los primos de Mersenne habituales, esta secuencia contiene sólo números primos (racionales).

Como ocurre con todos los números primos gaussianos, las normas (es decir, los cuadrados de los valores absolutos) de estos números son números primos racionales:

5, 13, 41, 113, 2113, 525313, 536903681, 140737471578113, ... (secuencia A182300 en la OEIS ).

Primos de Eisenstein Mersenne

Se pueden encontrar casos en los que un primo de Mersenne sea también un primo de Eisenstein , siendo de la forma b = 1 + ω y b = 1 − ω . En estos casos, tales números se denominan primos de Eisenstein Mersenne .

(1 + ω ) ⁿ − 1 es un primo de Eisenstein para el siguiente n :

2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153, 7541, 9049, 10453, 23743, , 534827, 2237561, ... (secuencia A066408 en el OEIS )

Las normas (es decir, los cuadrados de los valores absolutos) de estos números primos de Eisenstein son números primos racionales:

7, 271, 2269, 176419, 129159847, 1162320517, ... (secuencia A066413 en la OEIS )

dividir un número entero

primos repunit

La otra forma de lidiar con el hecho de que b ⁿ − 1 siempre es divisible por b − 1 es simplemente quitar este factor y preguntar qué valores de n hacen

${\displaystyle {\frac {b^{n}-1}{b-1}}}$

ser primo. (El número entero b puede ser positivo o negativo). Si, por ejemplo, tomamos b = 10 , obtenemos n valores de:

2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ... (secuencia A004023 en la OEIS ),
correspondiente a los primos 11, 1111111111111111111, 1111111111111111111111, 1,... (secuencia A004022 en el OEIS ).

Estos números primos se llaman números primos repunit. Otro ejemplo es cuando tomamos b = −12 , obtenemos n valores de:

2, 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ... (secuencia A057178 en el OEIS ),
correspondiente a los primos −11, 19141, 57154490053, ....

Es una conjetura que para cada número entero b que no es una potencia perfecta , hay infinitos valores de n tales que^{segundo norte} - 1/segundo - 1es primo. (Cuando b es una potencia perfecta, se puede demostrar que existe como máximo un valor de n tal que^{segundo norte} - 1/segundo - 1es primo)

Menos n tal que^{segundo norte} - 1/segundo - 1son primos (comenzando con b = 2 , 0 si no existe tal n )

2, 3, 2, 3, 2, 5, 3, 0, 2, 17, 2, 5, 3, 3, 2, 3, 2, 19, 3, 3, 2, 5, 3, 0, 7, 3, 2, 5, 2, 7, 0, 3, 13, 313, 2, 13, 3, 349, 2, 3, 2, 5, 5, 19, 2, 127, 19, 0, 3, 4229, 2, 11, 3, 17, 7, 3, 2, 3, 2, 7, 3, 5, 0, 19, 2, 19, 5, 3, 2, 3, 2, ... (secuencia A084740 en el OEIS )

Para bases negativas b , son (comenzando con b = −2 , 0 si no existe tal n )

3, 2, 2, 5, 2, 3, 2, 3, 5, 5, 2, 3, 2, 3, 3, 7, 2, 17, 2, 3, 3, 11, 2, 3, 11, 0, 3, 7, 2, 109, 2, 5, 3, 11, 31, 5, 2, 3, 53, 17, 2, 5, 2, 103, 7, 5, 2, 7, 1153, 3, 7, 21943, 2, 3, 37, 53, 3, 17, 2, 7, 2, 3, 0, 19, 7, 3, 2, 11, 3, 5, 2, ... (secuencia A084742 en el OEIS ) (observe que esta secuencia OEIS no permite n = 2 )

Base mínima b tal quesegundo ^{primo( norte )} − 1/segundo - 1es primo son

2, 2, 2, 2, 5, 2, 2, 2, 10, 6, 2, 61, 14, 15, 5, 24, 19, 2, 46, 3, 11, 22, 41, 2, 12, 22, 3, 2, 12, 86, 2, 7, 13, 11, 5, 29, 56, 30, 44, 60, 304, 5, 74, 118, 33, 156, 46, 183, 72, 606, 602, 223, 115, 37, 52, 104, 41, 6, 338, 217, ... (secuencia A066180 en el OEIS )

Para bases negativas b , son

3, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (secuencia A103795 en el OEIS )

Otros primos de Mersenne generalizados

Otro número de Mersenne generalizado es

${\displaystyle {\frac {a^{n}-b^{n}}{a-b}}}$

con a , b cualquier número entero coprimo , a > 1 y − a < b < a . (Dado que a ⁿ − b ⁿ siempre es divisible por a − b , la división es necesaria para que haya alguna posibilidad de encontrar números primos.) ^[a] Podemos preguntar cuál n hace que este número sea primo. Se puede demostrar que dichos n deben ser primos en sí mismos o iguales a 4, y n puede ser 4 si y sólo si a + b = 1 y a ² + b ² es primo. ^[b] Es una conjetura que para cualquier par ( a , b ) tal que a y b no sean r -ésimas potencias perfectas para cualquier r y −4 ab no sea una cuarta potencia perfecta , hay infinitos valores de n tales esoun ^norte - segundo ^norte/un - segundoes primo. ^[c] Sin embargo, esto no se ha demostrado para ningún valor único de ( a , b ) .

^* Nota: si b < 0 y n es par, entonces los números n no están incluidos en la secuencia OEIS correspondiente.

Cuando a = b + 1 , es ( b + 1 ) ⁿ − b ⁿ , una diferencia de dos nésimas potencias consecutivas perfectas, y si a ⁿ − b ⁿ es primo, entonces a debe ser b + 1 , porque es divisible por a − b .

Los mínimos n tales que ( b + 1 ) ⁿ − b ⁿ son primos son

2, 2, 2, 3, 2, 2, 7, 2, 2, 3, 2, 17, 3, 2, 2, 5, 3, 2, 5, 2, 2, 229, 2, 3, 3, 2, 3, 3, 2, 2, 5, 3, 2, 3, 2, 2, 3, 3, 2, 7, 2, 3, 37, 2, 3, 5, 58543, 2, 3, 2, 2, 3, 2, 2, 3, 2, 5, 3, 4663, 54517, 17, 3, 2, 5, 2, 3, 3, 2, 2, 47, 61, 19, ... (secuencia A058013 en la OEIS )

Menos b tales que ( b + 1) ^{primo( n )} − b ^{primo( n )} es primo son

1, 1, 1, 1, 5, 1, 1, 1, 5, 2, 1, 39, 6, 4, 12, 2, 2, 1, 6, 17, 46, 7, 5, 1, 25, 2, 41, 1, 12, 7, 1, 7, 327, 7, 8, 44, 26, 12, 75, 14, 51, 110, 4, 14, 49, 286, 15, 4, 39, 22, 109, 367, 22, 67, 27, 95, 80, 149, 2, 142, 3, 11, ... (secuencia A222119 en el OEIS )

Ver también

• Repunit
• Número de Fermat
• Poder de dos
• Constante de Erdős-Borwein
• Conjeturas de Mersenne
• tornado de mersenne
• Número doble de Mersenne
• Prime95 / MPrime
• Gran búsqueda de Mersenne Prime en Internet (GIMPS)
• Número primo más grande conocido
• Wieferich principal
• Wagstaff principal
• Cullen principal
• Woodall prima
• Proth cebado
• solinas prime
• La conjetura de Gillies
• número de williams

Notas

1. Este número es el mismo que el número de Lucas U _n ( a + b , ab ) , ya que a y b son las raíces de la ecuación cuadrática x ² − ( a + b ) x + ab = 0 .
2. Desdeun ⁴ - segundo ⁴/un - segundo= ( una + segundo )( una ² + segundo ² ) . Así, en este caso el par ( a , b ) debe ser ( x + 1, − x ) y x ² + ( x + 1) ² debe ser primo. Es decir, x debe estar en OEIS : A027861 .
3. Cuando a y b son r -ésimas potencias perfectas para algún r > 1 o cuando −4 ab es una cuarta potencia perfecta, se puede demostrar que hay como máximo dos valores de n con esta propiedad: en estos casos,un ^norte - segundo ^norte/un - segundose puede factorizar algebraicamente. ^{[ cita necesaria ]}

Referencias

1. "El proyecto GIMPS descubre el número primo más grande conocido: 282.589.933-1". Investigación Mersenne, Inc. 21 de diciembre de 2018 . Consultado el 21 de diciembre de 2018 .
2. "Informe de hitos de GIMPS". Mersenne.org . Investigación Mersenne, Inc. Consultado el 5 de diciembre de 2020 .
3. Caldwell, Chris. "Heurística: derivación de la conjetura de Wagstaff Mersenne".
4. Chris K. Caldwell, Primos de Mersenne: historia, teoremas y listas
5. The Prime Pages, la conjetura de Mersenne.
6. Resistente, GH ; Wright, EM (1959). Introducción a la teoría de los números (4ª ed.). Prensa de la Universidad de Oxford.
7. Cole, FN (1 de diciembre de 1903). "Sobre la factorización de números grandes". Boletín de la Sociedad Matemática Estadounidense . 10 (3): 134-138. doi : 10.1090/S0002-9904-1903-01079-9 .
8. Bell, ET y Asociación Matemática de América (1951). Matemáticas, reina y servidora de la ciencia . McGraw-Hill Nueva York.pag. 228.
9. "h2g2: números de Mersenne". Noticias de la BBC . Archivado desde el original el 5 de diciembre de 2014.
10. Horacio S. Uhler (1952). "Una breve historia de las investigaciones sobre los números de Mersenne y los últimos números primos inmensos". Scripta Matemática . 18 : 122-131.
11. Brian Napper, El Departamento de Matemáticas y Mark 1.
12. Maugh II, Thomas H. (27 de septiembre de 2008). "Los matemáticos de UCLA descubren un número primo de 13 millones de dígitos". Los Ángeles Times . Consultado el 21 de mayo de 2011 .
13. Tía Ghose. "Número primo más grande descubierto". Científico americano . Consultado el 7 de febrero de 2013 .
14. Cooper, Curtis (7 de enero de 2016). "Descubrimiento del número primo de Mersenne - 274207281 - ¡1 es primo!". Investigación Mersenne, Inc. Consultado el 22 de enero de 2016 .
15. Brook, Robert (19 de enero de 2016). "El número primo con 22 millones de dígitos es el más grande jamás encontrado". Científico nuevo . Consultado el 19 de enero de 2016 .
16. Chang, Kenneth (21 de enero de 2016). "Nuevo número primo más grande = 2 elevado a 74 millones ... Uh, es grande". Los New York Times . Consultado el 22 de enero de 2016 .
17. "Hitos". Archivado desde el original el 3 de septiembre de 2016.
18. "Mersenne Prime Discovery - ¡2^77232917-1 es Prime!". www.mersenne.org . Consultado el 3 de enero de 2018 .
19. "El número primo más grande conocido encontrado en la computadora de la iglesia". christianchronicle.org . 12 de enero de 2018.
20. "Encontrado: un número primo especial, asombrosamente grande". 5 de enero de 2018.
21. "GIMPS descubre el número primo más grande conocido: 2^82.589.933-1" . Consultado el 1 de enero de 2019 .
22. "GIMPS - Las matemáticas - PrimeNet". www.mersenne.org . Consultado el 29 de junio de 2021 .
23. Página de Mersenne de Will Edgington Archivada el 14 de octubre de 2014 en la Wayback Machine.
24. Caldwell, Chris K. "Prueba de un resultado de Euler y Lagrange sobre los divisores de Mersenne". Páginas principales .
25. Kleinjung, Thorsten; Bos, Joppe W.; Lenstra, Arjen K. (2014). "Fábrica de factorización de Mersenne". Avances en Criptología – ASIACRYPT 2014 . Apuntes de conferencias sobre informática. vol. 8874, págs. 358–377. doi :10.1007/978-3-662-45611-8_19. ISBN 978-3-662-45607-1.
26. Henri Lifchitz y Renaud Lifchitz. "Mejores récords del PRP" . Consultado el 5 de septiembre de 2022 .
27. "Detalles del exponente del número de Mersenne M12720787". www.mersenne.ca . Consultado el 5 de septiembre de 2022 .
28. "Estado del exponente de M1277" . Consultado el 21 de julio de 2021 .
29. "Detalles del exponente del número de Mersenne M1277". www.mersenne.ca . Consultado el 24 de junio de 2022 .
30. Petković, Miodrag (2009). Famosos rompecabezas de grandes matemáticos . Librería AMS. pag. 197.ISBN​ 978-0-8218-4814-2.
31. Weisstein, Eric W. "Problema del trigo y el tablero de ajedrez". Mundo matemático. Wolframio . Consultado el 11 de febrero de 2023 .
32. Alan Chamberlin. "Explorador de bases de datos de cuerpos pequeños JPL". Ssd.jpl.nasa.gov . Consultado el 21 de mayo de 2011 .
33. "OEIS A016131". La enciclopedia en línea de secuencias enteras.
34. "Una investigación de los números primos de Mersenne y Fermat". Archivado desde el original el 29 de mayo de 2012.
35. Solinas, Jerome A. (1 de enero de 2011). "Mersenne Prime generalizado". En Tilborg, furgoneta Henk CA; Jajodia, Sushil (eds.). Enciclopedia de Criptografía y Seguridad . Springer Estados Unidos. págs. 509–510. doi :10.1007/978-1-4419-5906-5_32. ISBN 978-1-4419-5905-8.
36. Chris Caldwell: The Prime Glossary: ​​Gaussian Mersenne (parte de Prime Pages )
37. Zalnezhad, Ali; Zalnezhad, Hossein; Shabani, Gasem; Zalnezhad, Mehdi (marzo de 2015). "Relaciones y algoritmo para lograr los números primos más grandes". arXiv : 1503.07688 [matemáticas.NT].
38. (x, 1) y (x, −1) para x = 2 a 50
39. (x, 1) para x = 2 a 160
40. (x, −1) para x = 2 a 160
41. (x + 1, x) para x = 1 a 160
42. (x + 1, −x) para x = 1 a 40
43. (x + 2, x) para x impar = 1 a 107
44. (x, −1) para x = 2 a 200
45. Registros PRP, busque ( a n − b n ) / c {\displaystyle (a^{n}-b^{n})/c} , es decir, (a, b)
46. Registros PRP, busque ( a n + b n ) / c {\displaystyle (a^{n}+b^{n})/c} , es decir, (a, −b)

enlaces externos

• "Número de Mersenne", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Página de inicio de GIMPS
• Informe de hitos de GIMPS: la página de estado ofrece varias estadísticas sobre el progreso de la búsqueda, que generalmente se actualizan cada semana, incluido el progreso para demostrar el orden de los números primos de Mersenne más grandes conocidos.
• GIMPS, factores conocidos de los números de Mersenne
• M _q = (8 x ) ² − (3 qy ) ² Propiedad de los números de Mersenne con exponente primo que son compuestos (PDF)
• M _q = x ² + d · y ² tesis de matemáticas (PS)
• Suciedad, James. "31 y primos de Mersenne". Numéfilo . Brady Harán . Archivado desde el original el 31 de mayo de 2013 . Consultado el 6 de abril de 2013 .
• Bibliografía principal de Mersenne con hipervínculos a publicaciones originales.
• Informe sobre los números primos de Mersenne: detección detallada (en alemán)
• wiki de GIMPS
• Página Mersenne de Will Edgington: contiene factores para números pequeños de Mersenne
• Factores conocidos de los números de Mersenne
• Dígitos decimales y nombres en inglés de los primos de Mersenne
• Curiosidades principales: 2305843009213693951
• http://www.leyland.vispa.com/numth/factorization/cunningham/2-.txt Archivado el 5 de noviembre de 2014 en Wayback Machine.
• http://www.leyland.vispa.com/numth/factorization/cunningham/2+.txt Archivado el 2 de mayo de 2013 en Wayback Machine.
• Secuencia OEIS A250197 (Números n tales que la parte primitiva aurifeuilliana izquierda de 2^n+1 es prima) – Factorización de números de Mersenne M _n ( n hasta 1280)
• Factorización de números de Mersenne completamente factorizados
• El proyecto Cunningham, factorización de bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12
• http://www.leyland.vispa.com/numth/factorization/cunningham/main.htm Archivado el 4 de marzo de 2016 en Wayback Machine.
• http://www.leyland.vispa.com/numth/factorization/anbn/main.htm Archivado el 2 de febrero de 2016 en Wayback Machine.

Enlaces de MathWorld

• Weisstein, Eric W. "Número de Mersenne". MundoMatemático .
• Weisstein, Eric W. "Mersenne principal". MundoMatemático .