1.14: Fermat Primes y Mersenne Primes
- Page ID
- 117441
Encontrar primos grandes y demostrar que efectivamente son primos no es fácil. Durante mucho tiempo, la gente ha buscado fórmulas para producir números primos, con diversos grados de éxito. En este capítulo aprenderemos sobre preguntas y respuestas relacionadas aportadas por muchas personas a lo largo de los últimos siglos, e incluso en el actual.
Let\(f(n) = n^2 - n + 41\), donde\(n\) es un entero positivo. A medida que conectamos\(1,2,\dots\), los primeros números obtenemos la secuencia\[41,43, 47, 53, 61, ...,\nonumber \] que parece estar produciendo muchos números primos. De hecho, los primeros cuarenta términos son todos primos, hasta e inclusive\(40^2-40+41 = 1601\), así que si tuviéramos que hacer una generalización apresurada, podríamos sospechar que siempre\(f(n)\) será primo, y hemos encontrado una fórmula simple para generar números primos.
Esto es falso, sin embargo, observe lo que sucede si dejamos\(n=41\): Resultados\[f(41)=41^2-41+41 = 41\cdot 41.\nonumber \] similares ocurren siempre que\(n\) es un múltiplo de\(41\), así que desafortunadamente\(f\) no siempre produce números primos.
Las funciones\(f(n)\) y el polinomio similar\(n^2+n+41\), ambos ejemplos de polinomios que producen varios números primos, fueron estudiados por los grandes matemáticos Leonhard Euler (1707—1783) y Adrien-Marie Legendre (1752—1833). Fue demostrado por Christian Goldbach (1690—1764) en 1752 que ningún polinomio con coeficientes enteros puede generar solo números primos, por lo que los polinomios tales como\(f(n)\) no pueden ser utilizados para generar consistentemente primos.
La función\(g(n)=6n+5\) claramente no siempre produce primos, según la prueba de Goldbach. También es fácil de ver eso\(g(6)=35=5\cdot 7\), y se\(5\) divide\(g(n)\) siempre que\(n\) sea un múltiplo de 5.
No obstante, el Ejercicio 1.11.2 indica que cada número primo que no sea 2 o 3 tiene la forma\(6n+1\) o\(6n+5\). Dado que hay infinitamente muchos primos, cualquiera\(g(n)=6n+5\) o\(h(n)=6n+1\) (o ambos) deben producir un número primo para infinitamente muchos\(n\). El ejercicio te\(\PageIndex{2}\) lleva a demostrar que esto es cierto para\(g(n)\).
De hecho, Johann Lejeune Dirichlet (1805—1859) demostró en 1837 que siempre\(a\) y\(b\) son relativamente primos, la función\(f(n)=an+b\) produce un número primo para infinitamente muchos valores de\(n\). En 2004, Ben Green y Terrence Tao anunciaron una prueba de que para cualquier longitud positiva\(k\), existen coeficientes\(a\) y\(b\) tales que\(f(n)=an+b\) producirán al menos\(k\) primos usando consecutivos valores de\(n\). (Por ejemplo,\(g(0)=5, g(1)=11, g(2)=17, g(3)=23, g(4)=29\), por lo que\(6n+5\) ya produce primos para cinco valores consecutivos de\(n\).)
Aunque las funciones como\(n^2-n+41\) o\(6n+5\) no siempre pueden producir primos, un gran número de primos (y a veces infinitamente muchos) sí tienen esta forma, así que una forma de encontrar primos, y quizás primos muy grandes, es mirar números que tienen alguna forma especial. Por ejemplo, varios de los primos más pequeños, como\(3\),\(5\),\(7\),\(17\),,\(31\) son todos una unidad menos que o una unidad más que una potencia de 2. Con eso en mente, el resto de este capítulo se fijará en lo siguiente.
¿Para qué valores de\(a\) y\(n\) podría\[a^{n}+1\quad\text{or}\quad a^n-1\nonumber\] ser un número primo?
Es fácil descartar algunos valores de\(a\) y\(n\). Por ejemplo tenemos lo siguiente.
Dejar\(a>1\) y\(n>1\). Lo siguiente es cierto.
- Si\(a^n-1\) es primo, entonces\(a=2\) y\(n\) es primo.
- Si\(a^n+1\) es primo, entonces\(a\) es parejo y\(n=2^k\) para algunos\(k \ge 1\).
Comprobante de 1
Sabemos por el Ejercicio 1.3.8 que\[\label{eq12-1ast} a^n-1=(a-1)(a^{n-1}+\dotsb+a+1).\] Si\(a>2\) y\(n>1\), entonces\(a-1>1\) y\(a^{n-1}+\dotsb+a+1>a+1>3\) así ambos factores en la ecuación\(\eqref{eq12-1ast}\) son mayores que 1 y por lo tanto no\(a^n-1\) es primo. De ahí\(a^n-1\) que si es primo debemos tener\(a=2\). Supongamos que este es el caso, es decir, que\(2^n-1\) es primo. Afirmamos que\(n\) es primo. Si no, entonces\(n=st\) para enteros\(s\) y\(t\) tal que\(1<s<n\) y\(1<t<n\). Entonces\[2^n-1=2^{st}- 1=(2^s)^t-1\nonumber \] es primo. Pero acabamos de demostrar que si\(a^n-1\) es prime debemos tener\(a=2\). Entonces debemos tener\(2^s=2\), forzando\(s=1\), una contradicción. De ahí\(n\) que debe ser primo, como se afirma.
Comprobante de 2
Supongamos primero que\(n\) es impar. Sustituyendo\(a\) por\(-a\) en ecuación\(\eqref{eq12-1ast}\), obtenemos\[(-a)^n-1=(-a-1)\left((-a)^{n-1}+(-a)^{n-2}+\dotsb+(-a)+1\right)\nonumber \] Dado que\(n\) es impar,\(n-1\)\(n-2\) es par\(\dotsc\), es impar,, etc.\((-a)^n=-a^n,(-a)^{n-1}=a^{n-1},(-a)^{n-2}=-a^{n-2},\dotsc\), tenemos, etc. sustituyendo estos valores rendimientos\[-(a^n+1)=-(a+1)\left(a^{n-1}-a^{n-2}+\dotsb+-a+1\right).\nonumber \] Multiplicando ambos lados por\(-1\) obtenemos\[a^n+1=(a+1)(a^{n-1}-a^{n-2}+\dotsb-a+1)\nonumber \] cuando\(n\) es impar. Si\(n\ge 2\), entonces\(a^n + 1> a+1\), y la ecuación anterior muestra que cuando\(n\) es impar y\(a>1\), el número no\(a^n+1\) es primo, ya que\(a+1\) es un divisor estrictamente entre\(1\) y \(a^n+1\). Por lo tanto, si\(a^n+1\) se supone que es primo, debe ser el caso que\(n\) sea parejo.
Supongamos ahora que\(n\) es par, y expresarlo como\(n=2^st\), donde\(t\) es impar (así\(s \geq 1\)). Si\(a^n+1\) es primo, entonces\((a^{2^s})^t+1\) es primo. Pero por lo que acabamos de mostrar, esto no puede ser primo si\(t\) es extraño y\(t\ge 2\). Ya que\(t\) es extraño, debemos tener\(t=1\) y así\(n=2^s\).
Por último, tenga en cuenta que ya\(n\) es positivo,\(a\) y\(a^n\) tienen la misma paridad, así\(a^n+1\) es impar si y sólo si\(a\) es par. El número 2 (el único primo par) es demasiado pequeño para ser escrito como\(a^n+1\) para cualquiera\(a>1\) y\(n>1\), así que si\(a^n+1\) es primo, entonces\(a\) es par y\(n\) es una potencia de 2, como se afirma.
Los teóricos de los números han estudiado los números primos satisfaciendo las conclusiones del Teorema\(\PageIndex{1}\). Recordamos dos en particular, a saber, Pierre de Fermat (1607—1665) y Marin Mersenne (1588—1648), a través de nombres dados a estos números.
Un número de la forma\(F_n=2^{(2^n)}+1\)\(n\ge 0\),, se llama número Fermat. Si\(F_n\) es primo, se llama Fermat prime. Un número de la forma\(M_n=2^n-1\),\(n\ge 2\), se dice que es un número de Mersenne. Si\(M_n\) es primo, se llama Mersenne prime.
Cuando Fermat estudió los números que ahora llevan su nombre, conjeturó que todos los números de Fermat son primos. En efecto, uno puede probar que\(F_0=3\)\(F_1=5\),\(F_2=17\),,\(F_3=257\) y\(F_4=65537\) son primos. A\(n\) medida que aumenta los números\(F_n=2^{(2^n)}+1\) aumentan de tamaño muy rápidamente y no son fáciles de verificar la primalidad en un tiempo razonable. Sin embargo, ahora se sabe que\(F_n\) es compuesto para muchos valores de\(n\ge 5\). Esto incluye todo\(n\) tal que\(5\le n\le 30\) y un gran número de otros valores de\(n\) inclusión\(18233954\) (el más grande conocido como de una revisión reciente de este texto) \(^{1}\). Ahora se conjetura que\(F_n\) es compuesto para todos\(n\ge 5\). Entonces el pensamiento original de Fermat que\(F_n\) es primordial para\(n\ge 0\) parece estar bastante lejos de la realidad.
Mersenne, amiga del matemático y filósofo René Descartes, estudió los números de Mersenne e intentó hacer una lista de primos de Mersenne con exponentes hasta 257, aunque la lista contenía algunos errores. Para ver algunos números pequeños de Mersenne, mira los números\(M_2=2^2-1 = 3\) y\(M_3=2^3-1 = 7\), que son ambos primos de Mersenne, y at\(M_4=2^4-1=15\), que es un número Mersenne pero no un primo (esto no debería ser de sorpresas a la luz del Teorema\(\PageIndex{1}\), ya que el exponente 4 no es primo). Nos detenemos aquí para reiterar esta idea.
Si\(M_n\) es primo, entonces\(n\) es primo.
Prueba
Esto es inmediato del Teorema\(\PageIndex{1}\) (1).
Quizás te preguntes si lo contrario de este Lema es cierto, si\(M_p=2^p-1\) es prime cuando\(p\) es prime. La respuesta es no; el número Mersenne no\(M_{11}=2^{11}-1=2047=23\cdot89\) es primo.
A lo largo de los años la gente ha seguido trabajando en el problema de determinar para qué primos\(p\),\(M_p=2^p-1\) es prime. A la fecha se han encontrado primos de\(51\) Mersenne. Se sabe que\(2^p-1\) es primo si\(p\) es uno de los siguientes 51 primos: 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, 216, 091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933.
El mayor prime de Mersenne actualmente conocido,\(M_{82589933}=2^{82589933}-1\), fue encontrado el 7 de diciembre de 2018. La representación decimal de este número tiene\(24,862,048\) dígitos (aproximadamente un millón y medio de dígitos más que en la representación de\(M_{77232917}\)). Fue encontrada por una computadora voluntaria por Patrick Laroche como parte de la Great Internet Mersenne Prime Search (GIMPS); vea www.mersenne.org para más información sobre esto. Este prime podría ser el prime 51 de Mersenne (en orden de tamaño), pero solo lo sabremos con certeza cuando GIMPS complete las pruebas de todos los exponentes primos entre 43112609 y 82589933. Posteriormente mostramos la conexión entre los primos de Mersenne y una clase especial de números llamados números perfectos.
La siguiente prueba de primalidad para números de Mersenne facilita verificar si\(M_p\) es primo o no cuando\(p\) es un primo grande.
Dejar\(p\) ser un primo impar. Definir la secuencia\[r_1,r_2,r_3,\dotsc,r_{p-1}\nonumber \] por las reglas\[r_1=4\nonumber \] y para\(k\ge 2\),\[r_k= (r_{k-1}^2-2) \bmod M_p.\nonumber \] Entonces\(M_p\) es primo si y solo si\(r_{p-1}=0\).
[La prueba de esto no es fácil. Un lugar para encontrar una prueba es el libro “Una selección de problemas en la teoría de los números” de W. Sierpinski, Pergamon Press, 1964.]
Vamos\(p=5\). Entonces\(M_p=M_5=31\). \[\begin{aligned} r_1 &=4 \\ r_2 &=(4^2-2) \bmod 31=14\bmod 31=14 \\ r_3 &=(14^2-2) \bmod 31=194\bmod 31=8 \\ r_4 &=(8^2-2) \bmod 31=62\bmod 31=0.\end{aligned}\]De ahí que por la prueba Lucas-Lehmer,\(M_5=31\) sea prime.
Tenga en cuenta que la prueba de Lucas-Lehmer para\(M_p=2^p-1\) toma solo\(p-1\) pasos. Por otro lado, si uno intenta demostrar\(M_p\) primo probando todos los primos\(\le\sqrt{M_p}\) uno debe considerar acerca de\(2^{p/2}\) los pasos. Esto es MUCHO más grande que\(p\) en general.
Este capítulo ha introducido los números y primos de Fermat y Mersenne y algo de lo que sabemos de ellos. Ojalá te hayas dado cuenta por los nombres y fechas aquí mencionados que ha tomado el trabajo de mucha gente a lo largo de mucho tiempo para averiguar lo que sabemos ahora. Ojalá también hayas tenido la sensación de que este trabajo no ha terminado, ¡hay mucho más que aprender! Aquí están algunas preguntas básicas sin resolver.
- ¿Hay infinitamente muchos primos de la forma\(2^{2^n}+1\) (es decir, primos de Fermat)?
- ¿Hay infinitamente muchos primos de la forma\(2^n-1\) (es decir, los primos de Mersenne)?
¿Cuándo tendremos respuestas? ¿Quién los proporcionará? ¿Serás parte de ese trabajo?
Ejercicios
Mostrar que si\[f(x) = a_px^p + a_{p-1}x^{p-1}+\cdots+a_2x^2+a_1x+a_0,\nonumber \] donde\(a_0,\dots, a_p\) están todos los enteros, con\(a_p \neq 0\) y\(p\geq 1\) y\(a_0>1\), entonces existe un valor de\(x\) tal que\(f(x)\) se garantiza que no sea primo. (Dé un ejemplo de tal valor.)
En este ejercicio, mostraremos que\(g(n)=6n+5\) producirá un número primo para infinitamente muchos valores de\(n\).
- Demostrar que aparte de 2 o 3, cada número primo tiene la forma\(6n+1\) o\(6n+5\).
(Compárelo con el Ejercicio 1.11.2.) - Mostrar que multiplicar dos números cualesquiera de la forma\(6n+1\) crea otro número del formulario\(6n+1\).
- Mostrar que multiplicar dos números de la forma\(6n+5\) crea un número del formulario\(6n+1\).
- Demuestre que hay infinitamente muchos primos de la forma\(6n+5\). (Pista: imitar la prueba de Euclides en el Teorema 1.11.1, mostrando que si\(q_1,q_2,\ldots ,q_k\) son todos los primos de la forma\(6n+5\), entonces\(q_1q_2\cdots q_k+4\) o\(5q_1q_2\cdots q_k+4\) debe tener un divisor primo de la forma\(6n+5\).
Usa una computadora para factorizar\(F_5\), describiendo los pasos y herramientas que uses.
Demostrar que si\(m,n\) son enteros con\(m<n\), entonces\(F_m \mid (F_n - 2)\).
(Sugerencia: Recordemos cómo factorial una diferencia de cuadrados.)
- Usa el ejercicio anterior para demostrarlo\(\gcd(F_m,F_n) = 1\) cuando sea\(m \neq n\).
- Explique por qué la parte (a) da una nueva prueba de que hay infinitamente muchos números primos.
- Usa la inducción matemática para mostrar eso\[F_n = (F_{n-1}-1)^2 + 1\nonumber \] para todos\(n \geq 2\).
- Utilice la inducción matemática y la parte (a) para mostrar que aparte de\(F_0\) y\(F_1\), todos los números de Fermat tienen 7 como último dígito.
Encuentra todos los enteros, si los hay, que sean tanto un primo de Mersenne como un primo de Fermat. Justifica tu respuesta.
Determine qué números de Mersenne\(M_n\) son primos cuando\(2\le n\le 12\). Puedes usar una computadora o sistema de álgebra computacional para este ejercicio, aunque en tu respuesta debes describir todos los pasos y herramientas que usas.
Mostrar usando la prueba Lucas-Lehmer que\(M_7=127\) es prime.
Notas al pie
[1] Este valor fue anunciado en octubre de 2020 por el usuario ryanp en https://www.mersenneforum.org/showth...=15449&page=28.