Primo de Mersenne

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^{n − 1} para algún número entero n. Llevan el nombre de Marin Mersenne, un fraile minim francés, que los estudió a principios del siglo XVII. Si n es un número compuesto, entonces también lo es 2^{n − 1}. Por lo tanto, una definición equivalente de los primos de Mersenne es que son los números primos de la forma M_p = 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).

Números de la forma M_n = 2ⁿ − 1 sin el requisito de primalidad pueden llamarse números de Mersenne. A veces, sin embargo, los números de Mersenne se definen para tener 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 perfectos pares y los números primos de Mersenne. Muchos de los números primos más grandes conocidos son números primos de Mersenne porque los números de Mersenne son más fáciles de comprobar en busca de primalidad.

Hasta octubre de 2022, se conocen 51 números primos de Mersenne. El mayor número primo conocido, 2^{82 589 933} − 1, es un primo de Mersenne. 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 superó un hito importante en el proyecto después de que todos los exponentes por debajo de 100 millones fueran verificados al menos una vez.

Acerca de los números primos de Mersenne

Muchas preguntas fundamentales sobre los primos de Mersenne siguen sin resolverse. Ni siquiera se sabe si el conjunto de primos de Mersenne es finito o infinito. La conjetura Lenstra-Pomerance-Wagstaff afirma que hay infinitamente muchos primos de Mersenne y predice su orden de crecimiento. Tampoco se sabe si infinitamente muchos números de Mersenne con exponentes primos son compuestos, aunque esto seguiría de conjeturas ampliamente creídas sobre números primos, por ejemplo, la infinitud de Sophie Germain primos congruentes con 3 (mod 4). Para estos primos p, 2p + 1 (que es también primo) dividirá M_p, por ejemplo, 23 Silencio M₁₁, 47 Silencio M₂₃, 167 Silencio M₈₃, 263 Silencio M₁₃₁, 359 Silencio M₁₇₉, 383 Silencio M₁₉₁, 479 Silencio M₂₃₉, y 503 Silencio M₂₅₁ (secuencia) A002515 en el OEIS). Desde para estos primos p, 2p + 1 es congruente con 7 mod 8, por lo que 2 es un mod de residuos cuadrático 2p + 1, y el orden multiplicativo de 2 mod 2p + 1 debe dividirse ${fnK}=p}$. Desde p es un primo, debe ser p 1. Sin embargo, no puede ser 1 desde entonces ${displaystyle Phi _{1}(2)=1}$ y 1 no tiene factores principales, por lo que debe ser p. Por lo tanto, 2p + 1 divideciones ${displaystyle Phi _{p}(2)=2^{p}-1}$ y ${displaystyle 2^{p}-1=M_{p}$ no puede ser primo.

Los primeros cuatro números primos de Mersenne son M₂ = 3, M₃ = 7, M₅ = 31 y M₇ = 127 y porque el primer primo de Mersenne comienza en M₂, todos los números primos de Mersenne son congruentes con 3 (mod 4). Aparte de M₀ = 0 y M< sub>1 = 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 a 3 (módulo 4).

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 sigue de la identidad

$${fnMicrosoft Sans Serif}b}cdotcdotcdotcdotcdotcdot(1+2^{2a}+2^{2a}+2cdots +2^{0}a}cdot}{2}{2}{2}bdot1}{2}$$

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

M₁₁ = 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 número entero impar arbitrario de tamaño similar seleccionado al azar. No obstante, los valores primos de M_p parecen volverse cada vez más escasos a medida que p aumenta. Por ejemplo, ocho de los primeros 11 números primos p dan lugar a un número primo de Mersenne M_p (los términos correctos en la lista original de Mersenne), mientras que M_p es primo solo para 43 de los primeros dos millones de números primos (hasta 32,452,843).

La falta actual de una prueba simple para determinar si un número de Mersenne dado es primo hace que la búsqueda de 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 en gran medida en esta tarea, lo que hace 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 número primo más grande conocido tiene algo de seguidores de culto. En consecuencia, se ha gastado una gran cantidad de potencia informática en la búsqueda de nuevos números primos de Mersenne, gran parte de lo 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 se requiere conocer la factorización de ese número, por lo que los números primos de Mersenne permiten encontrar polinomios primitivos de orden muy alto. Dichos trinomios primitivos se utilizan en generadores de números pseudoaleatorios con períodos muy grandes, como el Mersenne twister, el registro de desplazamiento generalizado y los generadores de Fibonacci retardado.

Números perfectos

Los números primos de Mersenne M_p 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, a la inversa, todos los números perfectos pares tienen esta forma. Esto se conoce como el teorema de Euclides-Euler. Se desconoce si existen números perfectos impares.

Historia

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

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

Su lista reprodujo los números primos conocidos de su tiempo 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₆₁, M₈₉ y M₁₀₇ (que son números primos). Mersenne dio pocos indicios de cómo se le ocurrió su lista.

Édouard Lucas demostró en 1876 que M₁₂₇ es realmente primo, como dijo Mersenne. Este fue el mayor número conocido por 75 años hasta 1951, cuando Ferrier encontró un mayor número, ${displaystyle (2^{148}+1)/17}$, usando una máquina de cálculo de escritorio. M₆₁ fue determinado a ser el primero en 1883 por Ivan Mikheevich Pervushin, aunque Mersenne afirmó que era composite, y por esta razón a veces se llama el número de Pervushin. Este fue el segundo número mayor conocido, y permaneció hasta 1911. Lucas había mostrado otro error en la lista de Mersenne en 1876. Sin encontrar un factor, Lucas demostró que M₆₇ es en realidad compuesto. No se encontró ningún factor hasta una famosa charla de Frank Nelson Cole en 1903. Sin hablar una palabra, fue a una pizarra y levantó 2 a la 67a potencia, luego restó uno, dando lugar al número 147,573,952,589,676,412,927. Al otro lado del tablero, se multiplicó 193,707,721 × 761,838,257,287 y obtuvo el mismo número, luego regresó a su asiento (para aplausos) sin hablar. Más tarde dijo que el resultado le había llevado "tres años de domingos" a encontrar. Una lista correcta de todos los primos de Mersenne en esta gama de números fue completada y rigurosamente verificada sólo unos tres siglos después de que Mersenne publicara su lista.

Búsqueda de números primos de Mersenne

Hay disponibles algoritmos rápidos para encontrar números primos de Mersenne y, a partir de junio de 2019, los ocho números primos más grandes conocidos son números 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< sub>19) fueron encontrados por Pietro Cataldi en 1588. Después de casi dos siglos, M₃₁< /span> fue verificado como primo por Leonhard Euler en 1772. El siguiente (en orden histórico, no numérico) fue M₁₂₇< /span>, encontrado por Édouard Lucas en 1876, luego M₆₁ por Ivan Mikheevich Pervushin en 1883. Dos más (M₈₉ y M_{107< /sub>}) fueron encontrados a principios del siglo XX por R. E. Powers en 1911 y 1914, respectivamente.

El método más eficaz que se conoce 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 números primos p > 2, M_p = 2^p − 1< /span> es primo si y solo si M_p divide a S _{p − 2}, donde S₀ = 4 y S_k = (S_{k< /i> − 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. El profesor de física jubilado de Yale, Horace Scudder Uhler, hizo una contribución notable, quien hizo los cálculos para los exponentes 157, 167, 193, 199, 227 y 229. Desafortunadamente para esos investigadores, el intervalo que estaban probando contiene la brecha relativa más grande conocida entre 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 en mayor conocido Mersenne prime by year – electronic era. La escala vertical es logarítmica en el número de dígitos, siendo así un ${displaystyle log(log(y)}$ función en el valor de la primera.

La búsqueda de números primos de Mersenne se revolucionó con la introducción de la computadora digital electrónica. Alan Turing los buscó en el Manchester Mark 1 en 1949, 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 Computadora Automática Occidental (SWAC) de la Oficina Nacional de Estándares de EE. UU. en el Instituto de Análisis Numérico de la Universidad de California, Los Ángeles, bajo la dirección de D. H. Lehmer, con un programa de búsqueda por computadora escrito y dirigido por el Prof. R. M. Robinson. Fue el primer número primo de Mersenne que se identificó en treinta y ocho años; el siguiente, M₆₀₇, fue encontrado por la computadora poco menos de dos horas después. Tres más: M₁₂₇₉, M₂₂₀₃ y M₂₂₈₁ — fueron encontrados por el mismo programa en el siguiente varios meses. M₄₄₂₃ 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 de piso (o equivalentemente ⌊log₁₀M_n⌋ + 1).

En septiembre de 2008, los matemáticos de UCLA que participaron en Great Internet Mersenne Prime Search (GIMPS) ganaron parte de un premio de 100 000 dólares de Electronic Frontier Foundation por su descubrimiento de un número 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 prime se encontró en un Dell OptiPlex 745 el 23 de agosto de 2008. Este fue el octavo Mersenne prime descubierto en UCLA.

El 12 de abril de 2009, un registro del servidor GIMPS informó que posiblemente se había encontrado un número 47 de Mersenne. El hallazgo se notó 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 es cronológicamente 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 Central Missouri, 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.

El 19 de enero de 2016, Cooper publicó su descubrimiento de un primo de Mersenne número 49, 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. 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 número 45 de Mersenne Prime.

El 3 de enero de 2018, se anunció que Jonathan Pace, un ingeniero eléctrico de 51 años que vive en Germantown, Tennessee, había encontrado un primo número 50 de Mersenne, 2^{77 232 917} − 1 (un número con 23.249.425 dígitos), como resultado de una búsqueda realizada por una red de servidores GIMPS. El hallazgo fue realizado por una computadora en las oficinas de una iglesia de la misma localidad.

El 21 de diciembre de 2018, se anunció que The Great Internet Mersenne Prime Search (GIMPS) descubrió el mayor número primo conocido, 2^{82 589 933} − 1, que tiene 24.862.048 dígitos. Una computadora ofrecida voluntariamente por Patrick Laroche de Ocala, Florida, hizo el hallazgo el 7 de diciembre de 2018.

A fines de 2020, GIMPS comenzó a usar una nueva técnica para descartar posibles números primos de Mersenne llamada prueba de número primo probable (PRP), basada en el desarrollo de Robert Gerbicz en 2017, y una forma simple de verificar pruebas desarrollada por Krzysztof Pietrzak en 2018 Debido a la baja tasa de error y la facilidad de prueba, esto redujo casi a la mitad el tiempo de cálculo para descartar posibles números primos sobre la prueba de Lucas-Lehmer (ya que dos usuarios ya no tendrían que realizar la misma prueba para confirmar la del otro). resultado), aunque los exponentes que pasan la prueba PRP aún requieren uno para confirmar su primalidad.

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 (modelo) a −1). Entonces... a^p (modelo) a −1)Así que a^p − 1 ≡ 0 (modelo a −1). Así a − 1 vida a^p − 1. Sin embargo, a^p − 1 es primo, así que a − 1 = a^p − 1 o a ± 1. En el caso anterior, a = a^p, por lo tanto a = 0, 1 (que es una contradicción, como ni −1 ni 0 es primordial) o p = 1. En este último caso, a = 2 o a = 0. Si a = 0, sin embargo, 0^p − 1 = 0 - 1 = 1 que no es la primera. Por lo tanto, a = 2.
2. Si 2^p − 1 es primo, entonces p es primo.
   • PruebaSupongamos 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)()(22)^a)^b−1 + (2^a)^b−2 +... + 2^a + 1) Así que... 2^p − 1 es composite. Por contraposición, si 2^p − 1 entonces es primo p es primo.
3. Si p es una prima extraña, entonces cada primo q que divide 2^p − 1 debe ser 1 más un múltiplo de 2p. Esto se mantiene 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: Por el pequeño teorema de Fermat, q es un factor 2^q−1 − 1. Desde q es un factor 2^p − 1, para todos los enteros positivos c, q es también un factor 2^pc − 1. Desde p es primo y q no es un factor 2¹ − 1, p es también el entero positivo más pequeño x tales que q es un factor 2^x − 1. Como resultado, para todos los enteros positivos x, q es un factor 2^x − 1 si p es un factor x. Por lo tanto, desde q es un factor 2^q−1 − 1, p es un factor q − 1 Así que... q (modelo) p). Además, desde entonces q es un factor 2^p − 1, que es extraño, q Es extraño. Por lo tanto, q 1 (mod 2p).
   • Este hecho conduce a una prueba del teorema de Euclides, que afirma la infinitud de los primos, distinta de la prueba escrita por Euclides: por cada primo impar p, todos los primos dividiendo 2^p − 1 son más grandes que p; por lo tanto siempre hay grandes primas que cualquier primo en particular.
   • De este hecho se desprende que para cada primo p ■ 2, hay al menos una primera de la forma 2kp+ 1 menos que o igual a M_p, para algunos enteros k.
4. Si p es una prima extraña, entonces cada primo q que divide 2^p − 1 es congruente con ±1 (mod 8).
   • Prueba: 2^{p+ 1} (modelo) q)Así que 2^1/2(p+1) es una raíz cuadrada 2 mod q. Por reciprocidad cuadrática, cada módulo primario en el que el número 2 tiene una raíz cuadrada es congruente con ±1 (mod 8).
5. Una prima de Mersenne no puede ser una prima de Wieferich.
   • Prueba: Mostramos si p = 2^m − 1 es una prima Mersenne, entonces la congruencia 2^p−1 (modelo) p²) no aguanta. Por el pequeño teorema de Fermat, m Silencio p − 1. Por lo tanto, uno puede escribir p − 1 = mλ. Si la congruencia dada está satisfecha, entonces p² Silencio^mλ − 1, por lo tanto 0 2^mλ − 1/2^m − 1 = 1 + 2^m + 2^2m +... + 2^{()λ −1)m} ↑λ mod (2^m −1). Por lo tanto 2^m − 1 vida λ, y por consiguiente λ ≥ 2^m − 1. Esto conduce a p ≥ 1 m(22)^m −1), que es imposible desde m ≥ 2.
6. Si m y n son números naturales entonces m y n son coprime si y sólo si 2^m − 1 y 2ⁿ − 1 son coprime. En consecuencia, un número primo divide a la mayoría de un número de Mersenne de primer costo. Es decir, el conjunto de números perniciosos de Mersenne es pareado coprime.
7. Si p y 2p + 1 ambos son primos (significando que p es una Sophie Germain prime), y p es congruente con 3 (mod 4), entonces 2p + 1 divideciones 2^p − 1.
   • Ejemplo: 11 y 23 son ambos primos, y 11 = 2 × 4 + 3, por lo que 23 divide 2¹¹ − 1.
   • Prueba# q Ser 2p + 1. Por el pequeño teorema de Fermat, 2^2p (modelo) q), así que 2^p (modelo) q) o 2^p (modelo) q). Supongamos que es cierto, entonces 2^{p+ 1} = 2^{1/2()p + 1)})² (modelo) q), por lo que −2 sería un mod de residuos cuadráticos q. Sin embargo, desde entonces p es congruente con 3 (mod 4), q es congruente con 7 (mod 8) por lo tanto 2 es un mod de residuos cuadráticos q. También desde q es congruente con 3 (mod 4), −1 es un mod quadratic nonresidue q, por lo tanto −2 es el producto de un residuo y un no residual y por lo tanto es un no residual, que es una contradicción. Por lo tanto, la anterior congruencia debe ser verdadera y 2p + 1 divideciones M_p.
8. Todos los divisores compuestos de los números de Mersenne de primera exposición son fuertes pseudoprimes a la base 2.
9. Con la excepción de 1, un número Mersenne no puede ser un poder perfecto. 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 enteros con m ■ 1 y k ■ 1.

Lista de números primos de Mersenne conocidos

En octubre de 2021, los 51 números 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, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 125778711 A000043 en el OEIS)

Factorización de números compuestos de Mersenne

Como son números primos, los números primos de Mersenne son divisibles solo por 1 y por ellos mismos. Sin embargo, no todos los números de Mersenne son números primos de Mersenne. Los números de Mersenne son muy buenos casos de prueba para el algoritmo de tamiz de campo numérico especial, por lo que a menudo el número más grande factorizado con este algoritmo ha sido un número de Mersenne. A partir de junio de 2019, 2¹¹⁹³ − 1 es el poseedor del récord, ya que se factorizó 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 enteros para obtener enlaces a más información. La criba de campo numérico especial puede factorizar números con más de un factor grande. Si un número tiene solo un factor muy grande, 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, el mayor número completamente factorizado (con factores primos probables permitidos) es 2^{12 720 787} − 1 = 1 119 429 257 × 175 573 124 547 437 977 × 8 480 999 878 421 106 991 × html q, donde q es una Número primo probable de 3.829.294 dígitos. Fue descubierto por un participante de GIMPS con el apodo de "Funky Waddle". A partir de septiembre de 2022, el número de Mersenne M₁₂₇₇ es el número de Mersenne compuesto más pequeño sin factores conocidos; no tiene factores primos por debajo de 2⁶⁸, y es muy poco probable que tenga factores por debajo de 10⁶⁵ (~2²¹⁶).

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

La cantidad de factores para los primeros 500 números de Mersenne se puede encontrar en (secuencia A046800 en el 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 n-disco requiere M_n pasos, suponiendo que no se cometan errores. 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₆₄.

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

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 radio interno es siempre un número de Mersenne. Por ejemplo, si el tramo par es 2^{n + 1} entonces, debido a que es primitivo, restringe el tramo impar para que sea 4ⁿ − 1, la hipotenusa será 4 ⁿ + 1 y su radio interno será 2ⁿ − 1.

Primos Mersenne-Fermat

Un número de Mersenne–Fermat se define como 2< i>^pr − 1/2^{pr − 1} − 1, con p primo, r número natural, y se puede escribir 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 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).

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 grado bajo con coeficientes enteros pequeños. Un ejemplo es 2⁶⁴ − 2³² + 1, en este caso, < i>n = 32, y f(x) = x ² − x + 1; otro ejemplo es 2¹⁹² − 2⁶⁴ − 1, en este caso, < i>n = 64, y f(x) = x ³ − x − 1.

También es natural tratar de 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 < span class="texhtml">b − 1, por lo que a menos que el último sea una unidad, el primero no es un número primo. Esto se puede remediar permitiendo que b sea un número entero algebraico en lugar de un número entero:

Números complejos

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

Primos gaussianos de Mersenne

Si consideramos el anillo de enteros gaussianos, obtenemos el caso b = 1 + i y b = 1 − i, y puede preguntar (WLOG) para cuál n el número (1 + i)ⁿ − 1 es un primo gaussiano que luego se llamará primo gaussiano de Mersenne.

(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, 3793, 3792321, 379 (secuencia) A057429 en el OEIS)

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

En cuanto a 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 el OEIS).

Primas de Eisenstein Mersenne

Se pueden encontrar casos en los que un número primo de Mersenne sea también un número primo de Eisenstein, siendo de la forma b = 1 + ω y b = 1 − ω. En estos casos, dichos 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, 255361, 534827, 2237561,... (secuencia) A066408 en el OEIS)

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

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

Dividir un entero

Repetir números primos

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

${displaystyle {frac {fn}{b-1}} {fn}} {fnK}}} {fn}} {fn}}} {fn}}} {fn}}}}}} {fn}}$

sé principal. (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 el OEIS),
correspondiente a los primos 11, 11111111111111111111111111111111111111111111111111111111111111111,... (sequencencence A004022 en el OEIS).

Estos números primos se denominan 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,... A057178 en el OEIS),
correspondientes a primos −11, 19141, 57154490053,....

Es una conjetura que por cada entero b que no es una potencia perfecta, existen infinitos valores de n tal que b ⁿ − 1/b − 1 es primo. (Cuando b es una potencia perfecta, se puede demostrar que hay como mucho una n< /i> valor tal que bⁿ − 1/b − 1 es primo)

Menor n tal que bⁿ − 1/ b − 1 es primo son (comenzando con b = 2, 0 si no existe tal n)

2, 3, 2, 3, 2, 5, 3, 0, 2, 17, 2, 5, 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, 7, 3, 2, 3, 2, 3, 2, 3, 2, A084740 en el OEIS)

Para las bases negativas b, son (empezando por b = − 2, 0 si no existe tal n)

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

Base mínima b tal que < abarcan clase="num">b^prime(n) − 1/ b − 1 es primo son

2, 2, 2, 2, 5, 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, 104, 41, 6, 338... 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, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3... A103795 en el OEIS)

Otros primos de Mersenne generalizados

Otro número de Mersenne generalizado es

${displaystyle {fn} {fn} {fn} {fn}} {fn}} {fn}}} {fn}}}} {fn}}} {fn}}} {fn}}}}} {fn}}} {f}}}}}$

con a, b< /span> cualquier entero coprimo, a > 1 y −a < b < a. (Ya que aⁿ − b^{n< /i>} siempre es divisible por a − b, la división es necesaria para hay alguna posibilidad de encontrar números primos). Podemos preguntar qué n hace que este número sea primo. Se puede demostrar que tales n deben ser primos ellos mismos o iguales a 4, y n puede ser 4 si y solo si a + b = 1 y a² + b² es primo. Es una conjetura que para cualquier par (a, b) tal que a y b no son perfectos résimas potencias para cualquier r y −4ab no es una cuarta potencia perfecta, hay infinitos valores de n tal que a^{< i>n} − bⁿ/ a − b es primo. Sin embargo, esto no se ha probado 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 perfectas consecutivas, y si a< /i>ⁿ − bⁿ es primo, entonces a debe ser b + 1, porque es divisible por a − b.

Menor n tal que (b + 1) ⁿ − bⁿ es número primo

2, 3, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 17, 3, 2, 5, 2, 5, 2, 2, 229, 2, 3, 3, 2, 3, 2, 3, 2, 5, 3, 2, 3, 2, 3, 2, 3, 2, 7, 2, 3, 37, 2, 3, 5, 58543, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 5, 3, 4663, 54517, 17, 2, 3, 2, 3, 2, 3, 2, 3, 2, 5, 2, 5, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 5, 2, 3, 2, 3, 2, 3, 2, 3, 2, A058013 en el OEIS)

Menor b tal que (b + 1) ^prime(n) − b^prime(n) es primos son

1, 1, 1, 1, 5, 1, 1, 5, 2, 1, 39, 6, 4, 12, 2, 2, 1, 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, 3, 3, 11... A222119 en el OEIS)