5.4: Fermet y Mersenne Primes

Última actualización
Guardar como PDF

Page ID: 111484

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

A través de los siglos, volviendo a la antigüedad temprana, las personas han quedado fascinadas por los números\(6\), como, que son la suma de sus divisores distintos de sí mismo, a saber:\(6 = 1+2+3\). Los primos de Mersenne y Fermat, primos de la forma\(2^{k} \pm 1\), han atraído siglos de atención. Tenga en cuenta que si\(p\) es un primo distinto de\(2\), entonces\(p^{k} \pm 1\) es divisible por\(2\) y por lo tanto no un primo.

Definición 5.11

Los primos de Mersenne son\(M_{k} = 2^{k}-1\). Un número primo de Mersenne es un número Mersenne que también es primo.
Los primos de Fermat son\(F_{k} = 2^{2^k}-1\). Un número primo de Fermat es un número Fermat que también es primo. El número\(n \in \mathbb{N}\) se llama perfecto, si\(\sigma (n) = 2n\)

Lema 5.12

Si\(ad = k\), entonces\(2^{d}-1 | 2^{k}-1\).
Si\(ad = k\) y\(a\) es impar, entonces\(2^{d}+1 | 2^{k}+1\).

Prueba

Sólo probamos (2). La otra afirmación puede probarse de manera similar. Entonces supongamos que eso\(a\) es extraño, entonces

\[2^{d} = _{2^{d}+1} -1 \Rightarrow 2^{ad} = _{2^{d}+1} (-1)^{a} = _{2^{d}+1} -1 \Rightarrow 2^{ad}+1 = _{2^{d}+1} 0 \nonumber\]

lo que prueba la declaración. Observe que esto incluye el caso donde\(d=1\). En ese caso, tenemos\(3 | 2^{a}+1\) (siempre que sea\(a\) impar).

Una prueba usando la serie geomética se puede encontrar en el ejercicio 1.14. Este lema implica inmediatamente lo siguiente.

Corolario 5.13

Si\(2^{k}-1\) es primo, entonces\(k\) es primo.

Si\(2^{k}+1\) es primo, entonces\(k=2^r\).

Entonces, los candidatos de primos de Mersenne son los números\(2^{p}-1\) donde\(p\) está primo. Esto funciona para\(p \in \{0, 1, \cdots, 10\}\), pero\(2^{11}-1\) es la llave de los monos.

Es igual a\(23 \cdot 89\) y por lo tanto es compuesto. Después de eso, los primos de Mersenne se vuelven cada vez más escasos. Entre los primeros aproximadamente\(2.3\) millones de primos, solo\(45\) dan primos de Mersenne. Al momento de escribir este artículo (2017), no se sabe si hay infinitamente muchos primos de Mersenne. En 2016, se descubrió un prime Mersenne muy grande:\(2^{74,207,281}-1\). Los primos de Mersenne se utilizan en generadores de números pseudoaleatorios.

Turing a primos de la forma\(2^{k}+1\), los únicos candidatos son\(F_{r} = 2^{2^{r}}+1\). El propio Fermat señaló que\(F_{r}\) es primo para\(0 \le r \le 4\), y conjetura que todos estos números eran primos. De nuevo, ¡Fermat no lo hizo bien! Resulta que el número 5-ésimo de Fermat,\(2^{32}+1\), es divisible por\(641\) (ver ejercicio 5.11). De hecho, a partir de este escrito en 2017, ¡no hay otros primos de Fermat conocidos entre los primeros\(297\) 297 números de fermat! Los primos Fermat también se utilizan en generadores de números pseudoaleatorios.

Lema 5.14

Si\(2^k-1\) es primo, entonces\(k>1\) y\(2^{k-1} (2^{k}-1)\) es perfecto.

Prueba

Si\(2^{k}-1\) es primo, entonces debe ser por lo menos\(2\), y así\(k>1\). Vamos\(n = 2^{k-1} (2^{k}-1)\). Como\(\sigma\) es multiplicativo y\(2^{k}-1\) es primo, podemos calcular (usando el Teorema 4.5):

\[\sigma (n) = \sigma (2^{k-1}) \sigma (2^{k}-1) = (\sum_{i=0}^{k-1} 2^i) 2^k = (2^{k}-1) 2^{k} = 2n \nonumber\]

lo que prueba el lema.

Teorema 5.15 (Teorema de Euler)

Supongamos que\(n\) es par. Entonces\(n\) es perfecto si y solo si\(n\) es de la forma\(2^{k-1} (2^{k}-1)\) donde\(2^{k}-1\) es primo.

Prueba

Una dirección se desprende del lema anterior. Sólo tenemos que probar que si un número par\(n = _{q} 2^{k-1}\) donde\(k \ge 2\), es perfecto entonces es de la forma estipulada.

Ya que\(n\) es par, podemos suponer\(n = _{q} 2^{k-1}\) dónde\(k \ge 2\) y\(2 \nmid q\). Utilizando la multiplicatividad de\(\sigma\) y el hecho de que\(\sigma (n) = 2n\):

\[\sigma (n) = \sigma (q) (2^{k}-1) = _{q} 2^{k} \nonumber\]

Así

\[(2^{k}-1) \sigma (q) - 2^{k} q = 0 \nonumber\]

Ya que\(2^{k}-(2^{k}-1) = 1\), sabemos por Bezout eso\(\gcd ((2^{k}-1, 2^{k}) = 1\). Así Propostion 3.5 implica que la solución general de la ecuación anterior es:

\[\begin{array} {ccc} {q=(2^{k}-1)t}&{\mbox{and}}&{\sigma (q) = 2^{k} t} \end{array} \nonumber\]

donde\(t>0\), porque sabemos que\(q>0\)

Supongamos primero eso\(t>1\). La forma de\(q\), es decir\(q = (2^{k}-1)t\), nos permite identificar al menos cuatro divisores distintos de\(q\). Esto da que

\[\sigma (q) \ge 1+t+(2^{k}-1)+(2^{k}-1)t = 2^{k}(t+1) \nonumber\]

Esto contradice la ecuación 5.2, y así\(t=1\).

Ahora usa la ecuación 5.2 nuevamente (con\(t = 1\)) para obtener que\(n = _{q}2^{k-1} = (2^{k}-1) 2^{k-1}\) tenga la forma requerida. Futhermore, la misma ecuación dice aquello\(\sigma (q) = \sigma (2^{k}-1) = 2^k\) que prueba que\(2^{k}-1\) es primo.

Se desconoce a la fecha de este escrito si existen números impares perfectos.