¿Cómo demostró Euler que el número de Mersenne 231−1231−12^{31}-1 es un número primo tan temprano en la historia?

Question

¿Cómo demostró Euler que el número de Mersenne 231−1231−12^{31}-1 es un número primo tan temprano en la historia?

Matemáticas
números primos

nadarbicicletacorrer

Leí que Euler probó $2^{31} -1$ es primo ¿Qué técnicas usó para probar esto tan temprano en la historia? ¿No se hacen cosas con números muy grandes con computadoras? ¿Sabes si Euler tenía un equipo de personas para seguir algoritmos para él, llamados "computadoras"?

Tomas Andrews

2^{31} - 1

$2^{31}-1$ no es tan grande - se trata de

2

$2$ mil millones.

Álvaro Lozano-Robledo

Demostrando que

n = 31 = 2^{5} - 1

$n=31=2^5-1$ es un primo de Mersenne no es nada dificil. Sin embargo, probar que

2^{31} - 1

$2^{31}-1$ es primo... Esa es otra historia. Mi punto: deberías arreglar el título.

alex j mejor

François Arago dijo una vez de Euler: "Calculó sin ningún esfuerzo aparente, tal como los hombres respiran, como las águilas se sostienen en el aire".

MiUsuarioEsEste

No calcularon todas las posibilidades, como lo haríamos con una computadora hoy en día. Tenga en cuenta que algunos números de Mersenne se encontraron antes que los más pequeños. Por ejemplo,

M_{127}

$M_{127}$ se encontró que era primo antes

M_{61}

$M_{61}$ ,

M_{89}

$M_{89}$ y

M_{107}

$M_{107}$ . Así que probablemente lo hicieron de una manera diferente. Lea esto: en.wikipedia.org/wiki/Mersenne_prime para algunas pruebas de primalidad en los números de Mersenne.

Kaz

Incluso con pruebas de divisibilidad exhaustivas (tamiz de Erastótenes) no hay necesidad de probar divisores mayores que

\sqrt{n}

$\sqrt n$ , o 46340, y solo los números primos en ese espacio son candidatos. Este espacio no es tanto trabajo para probar, especialmente si tienes estudiantes. De inmediato podemos eliminar todos los números pares y los divisibles por tres, dejando solo alrededor de 15,450 números para probar. Los múltiplos de 2 y 5 se distinguen por su dígito decimal menos significativo y los múltiplos de tres se reconocen y eliminan fácilmente. Si hay disponible una lista de números primos por debajo de 46340, es aún más fácil.

4pie0

y tiene solo 227,832 dígitos

Robert Sopa

Algunas personas se sorprenden de que la "hipótesis china" no haya sido refutada antes, ya que el contraejemplo es relativamente pequeño (es decir, 341) y el período de la aritmética modular es aún más pequeño (es decir, 10). Pero puedo entender que desde

2^{341} > 10^{102}

$2^{341} > 10^{102}$ , debe haber parecido muy desalentador en ese entonces.

Respuestas (3)

¿Cómo demostró Euler que el número de Mersenne 231−1231−12^{31}-1 es un número primo tan temprano en la historia?

Demostrando que $n=31=2^5-1$ es un primo de Mersenne no es nada dificil. Sin embargo, probar que $2^{31}-1$ es primo... Esa es otra historia. Mi punto: deberías arreglar el título.
François Arago dijo una vez de Euler: "Calculó sin ningún esfuerzo aparente, tal como los hombres respiran, como las águilas se sostienen en el aire".
No calcularon todas las posibilidades, como lo haríamos con una computadora hoy en día. Tenga en cuenta que algunos números de Mersenne se encontraron antes que los más pequeños. Por ejemplo, $M_{127}$ se encontró que era primo antes $M_{61}$ , $M_{89}$ y $M_{107}$ . Así que probablemente lo hicieron de una manera diferente. Lea esto: en.wikipedia.org/wiki/Mersenne_prime para algunas pruebas de primalidad en los números de Mersenne.
Incluso con pruebas de divisibilidad exhaustivas (tamiz de Erastótenes) no hay necesidad de probar divisores mayores que $\sqrt n$ , o 46340, y solo los números primos en ese espacio son candidatos. Este espacio no es tanto trabajo para probar, especialmente si tienes estudiantes. De inmediato podemos eliminar todos los números pares y los divisibles por tres, dejando solo alrededor de 15,450 números para probar. Los múltiplos de 2 y 5 se distinguen por su dígito decimal menos significativo y los múltiplos de tres se reconocen y eliminan fácilmente. Si hay disponible una lista de números primos por debajo de 46340, es aún más fácil.
Algunas personas se sorprenden de que la "hipótesis china" no haya sido refutada antes, ya que el contraejemplo es relativamente pequeño (es decir, 341) y el período de la aritmética modular es aún más pequeño (es decir, 10). Pero puedo entender que desde $2^{341} > 10^{102}$ , debe haber parecido muy desalentador en ese entonces.

Tomas Andrews · Answer 1

No, Euler no requería un equipo para este tipo de problema, podía simplificar mucho los cálculos necesarios a mano usando algún razonamiento matemático. (Según el comentarista MathGems a continuación, tenía asistentes, pero incluso entonces, parece una leyenda urbana decir que los llamó "computadoras". Ciertamente, era poco probable que fuera una palabra en inglés, aunque podría haber elegido el equivalente francés. .)

¿Usó un asistente o más para este cálculo? Prácticamente imposible de decir. ¿Necesitaría un equipo de personas trabajando en una habitación trasera para hacer este cálculo en particular? No.

Si $q$ es un factor primo de $2^p-1$ entonces $2^p\equiv 1\pmod q$ y por lo tanto $p|q-1$ , entonces $q\equiv 1\pmod p$ . Eso significa, más o menos, cuando $p=31$ , que solo tienes que marcar uno de cada $31$ primos

También puedes concluir que $q\equiv \pm 1\pmod 8$ , desde

2 \equiv 2^{pag + 1} \equiv {(2^{\frac{pag + 1}{2}})}^{2} (modificación q)

$2\equiv 2^{p+1} \equiv \left(2^{\frac{p+1}{2}}\right)^2\pmod q$ entonces

2

$2$ debe ser un modulo cuadrado

q

$q$ . Esto reduce aproximadamente a la mitad de nuevo los valores posibles para

q

$q$ .

Juntos, esto significa que $q\equiv 63$ o $q\equiv 1\pmod {8\cdot 31=248}$ . Lo más pequeño posible como $q$ es $311$ . el siguiente es $q=1303.$ Como puede ver, esto reducirá en gran medida la cantidad de comprobaciones que tenemos que hacer.

Ahora con $n=2^{31}-1$ solo tienes que comprobar los factores primos hasta $\sqrt{2^{31}-1}<46341$ . Una estimación aproximada dice que deberíamos esperar aproximadamente $70$ primos en este rango que satisfacen las condiciones anteriores. (La cuenta exacta es $84.$ )

Además, no es necesario dividir realmente $2^{31}-1$ por $q$ para demostrar que no se divide. Más bien, puede calcular $2^{32}\pmod q$ por elevación repetida al cuadrado. Por ejemplo, si $q=311$ :

2^{2} \equiv 4 (modificación 311)

$2^2\equiv 4\pmod {311}$

2^{4} \equiv 4^{2} \equiv dieciséis (modificación 311)

$2^4\equiv 4^2 \equiv 16\pmod {311}$

2^{8} \equiv {dieciséis}^{2} \equiv 256 \equiv - 55 (modificación 311)

$2^8 \equiv 16^2 \equiv 256\equiv -55\pmod {311}$

2^{dieciséis} \equiv (- 55)^{2} \equiv - 85 (modificación 311)

$2^{16}\equiv (-55)^2 \equiv -85\pmod{311}$

2^{32} \equiv (- 85)^{2} \equiv 72 (modificación 311)

$2^{32}\equiv (-85)^2\equiv 72\pmod {311}$

Desde $2^{32}\not\equiv 2\pmod {311}$ , lo sabemos $2^{31}-1$ no es divisible por $311$ .

¿El 2 en la última línea debería ser un 1, o estoy siendo tonto?
Hay varios $2$ s en la última línea, @AlexJBest. Desde que calculé $2^{32}$ porque era más fácil que calcular $2^{31}$ , estaba usando eso $311|2^{32}-2$ si y solo si $311|2^{31}-1$
Muy lindo. Entonces, de hecho, el cálculo real podría ser realizado en una hora o dos por un niño paciente en edad escolar. Ciertamente no requeriría un equipo de computadoras humanas.
@NateEldredge Suponiendo que ya tenía la lista de números primos hasta $46340$ , Sí.
@ThomasAndrews: Que en sí mismo podría generarse en unas pocas horas por un par de monos entrenados, usando un tamiz, por ejemplo.
@NateEldredge Sí, pero sospecho que Euler ya tenía esa lista. Sin él, probablemente le tomaría a un niño en edad escolar más de una o dos horas, pero ciertamente no más de un día. :)
Pero Euler tenía un equipo. Por ejemplo, si lee la teoría de números de Weil, un enfoque a través de la historia, encontrará al menos 15 pasajes que mencionan a los "asistentes" de Euler (que incluían al hijo de Euler, Nicolas Fuss, y gente enviada desde Basilea con la cooperación de Daniel Bernoulli). Es de suponer que los asistentes jugaron un papel importante después de que Euler quedó ciego (alrededor de 1771).
@MathGems Debería haber escrito "no requería un equipo". Para este cálculo, quiero decir.
@Tomás $\$ Dado que $\,84\,$ del $\,186\,$ los divisores candidatos son primos: $\rm\ (311,1303,\ldots,45137,45943),\:$ No me sorprendería que Euler enviara a sus asistentes estos muchos cálculos manuales poco esclarecedores.
De ahí mi lenguaje reformulado. @MathGems El punto es que el cálculo no es tan desalentador como para necesitar un equipo. Una persona siempre puede preferir que otras personas hagan el trabajo pesado, por supuesto. E incluso entonces, bien podría elegir que solo lo haga un asistente, no un equipo.
También hay $372$ candidatos, más o menos - hay que duplicar $46341/248$ porque tienes los dos $1$ y $63$ como posibles restos. @MathGems
Sí, estoy de acuerdo en que es muy posible que una sola persona pueda hacer todos esos cálculos. Pero dado que tales cálculos generalmente no arrojan nuevos conocimientos, sospecho que algunos (o todos) se enviarían a los asistentes si estuvieran disponibles. Bien, $186$ debe ser el doble de arriba.

gemas matemáticas · Answer 2

Euler demostró $\rm\: M_{31}= 2^{31}\!-1\:$ es primo demostrando que todos los divisores primos son $\rm\equiv 1$ o $\rm\, 63\:\ (mod\ 248),\:$ luego pruebe dividiendo por todos los números primos de esta forma a continuación $\rm\sqrt{M_{31}}.\:$ La restricción sobre los divisores primos es una consecuencia inmediata del (ahora) bien conocido teorema del factor de Mersenne: para primos impares $\rm\:p,q,\:$ $\rm\: p\mid M_q\:\Rightarrow\: p\equiv 1\,\ (mod\ q),\,\ p\equiv \pm 1\,\ (mod\ 8).\:$

A continuación se muestra un extracto de su carta de 1772 a Bernoulli que describe esto. Véase también esta página. ingrese la descripción de la imagen aquí

«Ces règles sont fondées sur un principe dont la démontration n'est pas encore connue.» Pura genialidad :-D
"Estas reglas se basan en un principio cuya demostración aún no se conoce"
¿No dice que Fermat ya había probado que $2^{31}-1$ es un primo?
Eso se debe al teorema de que 2 es un módulo cuadrado y un primo impar p si y solo si p es congruente con 1 o 7 módulo 8. Sería bueno si mencionaras eso, pero lo voté a favor de todos modos porque ya lo entendí.

alex j mejor · Answer 3

Euler no usó un equipo para calcular todas las posibles divisiones principales; sin embargo, es posible que haya usado asistentes para hacer cálculos de rutina (ver comentarios y otras respuestas). Sin embargo, era muy, muy inteligente y no tengo ninguna duda de que él mismo podría haber realizado los cálculos necesarios increíblemente rápido. Como mencioné en los comentarios, François Arago dijo: "Calculó sin ningún esfuerzo aparente, así como los hombres respiran, como las águilas se sostienen en el aire". Notó algunas propiedades de los números primos que dividen $2^{31}-1$ debe tener, lo que redujo enormemente el cálculo requerido. Los detalles completos están aquí .

«Muy, muy inteligente» es un eufemismo con respecto a Euler :-)
No sé qué significa esto: "Euler no tenía equipo": era profesor y estaba enseñando, por lo que tenía estudiantes y si no recuerdo mis lecturas completamente falsas, dejaron que sus estudiantes y asistentes hicieran estándar calculos Bueno, los comentarios sobre cosas como esa ocurren a veces como notas al margen o medias oraciones en las biografías, pero creo que debería haber sido un comportamiento común (al menos lo habría hecho de esta manera si hubiera vivido en esa época)
Sabes, tal vez Euler no era tan inteligente. Simplemente desarrolló su potencial al máximo al no perder el tiempo navegando por la web, respondiendo correos electrónicos, conduciendo dos horas al día en horas pico de tráfico o hundiendo el tiempo en basura como Unix, MS Windows, LaTeX, Mathematica,...

¿Cómo demostró Euler que el número de Mersenne 231−1231−12^{31}-1 es un número primo tan temprano en la historia?

nadarbicicletacorrer

Tomas Andrews

Álvaro Lozano-Robledo

alex j mejor

MiUsuarioEsEste

Kaz

4pie0

Robert Sopa

Respuestas (3)

Tomas Andrews

alex j mejor

Tomas Andrews

alex j mejor

Nate Eldredge

Tomas Andrews

Nate Eldredge

Tomas Andrews

gemas matemáticas

Tomas Andrews

gemas matemáticas

Tomas Andrews

Tomas Andrews

gemas matemáticas

gemas matemáticas

Mariano Suárez-Álvarez

usuario13107

Dan toca el violín a la luz del fuego

sandra oeste

Hormiga

Timoteo

alex j mejor

Mariano Suárez-Álvarez

alex j mejor

Gottfried Helms

alex j mejor

Kaz