70 votos

¿Cómo Euler probar el de Mersenne número $2^{31}-1$ es un primer principio de la historia?

He leído que Euler demostró $2^{31} -1$ es primo. Las técnicas que se utilizó para probar esto tan temprano en la historia? No es muy grande el número de cosas por hacer con los ordenadores? ¿Sabe usted si Euler había un equipo de personas para que siga algoritmos para él, apodado el "ordenador"?

67voto

HappyEngineer Puntos 111

No, Euler no requieren de un equipo para este tipo de problema, se podría simplificar en gran medida los cálculos necesarios a mano, con algo de razonamiento matemático. (Según el comentarista MathGems a continuación, tuvo asistentes, pero incluso entonces, parece una leyenda urbana dice que él los llamó "equipos". Sin duda, era poco probable que se una palabra de inglés, a pesar de que él podría haber elegido el equivalente francés.)

Hizo uso de un asistente o más para este cálculo? Prácticamente imposible de decir. Iba a necesitar un equipo de personas crujido de distancia en un cuarto de vuelta para hacer este particular el cálculo? No.

Si $q$ es un primer factor de $2^p-1$ $2^p\equiv 1\pmod q$ y, por tanto,$p|q-1$, lo $q\equiv 1\pmod p$. Eso significa que, aproximadamente, cuando $p=31$, que usted sólo tiene que comprobar aproximadamente uno de cada $31$ números primos.

También se puede concluir que $q\equiv \pm 1\pmod 8$, desde $$2\equiv 2^{p+1} \equiv \left(2^{\frac{p+1}{2}}\right)^2\pmod q$$ so $2$ must be a square modulo $q$. This reduces roughly in half again the possible values for $p$.

Juntos, estos significa que $q\equiv 63$ o $q\equiv 1\pmod {8\cdot 31=248}$. El más pequeño posible, dichas $q$$311$. El siguiente es $q=1303.$ Como se puede ver, esto va a reducir considerablemente la cantidad de cheques que tenemos que hacer.

Ahora, con $n=2^{31}-1$ usted sólo tiene que comprobar factores primos de a $\sqrt{2^{31}-1}<46341$. Una estimación aproximada dice que debemos esperar aproximadamente $70$ de los números primos en esta gama que satisface las condiciones anteriores. (El número exacto es $84.$)

Además, no es necesario dividir $2^{31}-1$ $q$ a demostrar que no se dividen. En lugar, usted puede calcular el $2^{32}\pmod q$ por repetir la cuadratura. Por ejemplo, si $q=311$:

$$2^2\equiv 4\pmod {311}$$ $$2^4\equiv 4^2 \equiv 16\pmod {311}$$ $$2^8 \equiv 16^2 \equiv 256\equiv -55\pmod {311}$$ $$2^{16}\equiv (-55)^2 \equiv -85\pmod{311}$$ $$2^{32}\equiv (-85)^2\equiv 72\pmod {311}$$

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

37voto

Math Gems Puntos 14842

Euler demostró $\rm\: M_{31}= 2^{31}\!-1\:$ es el primer mostrando que todos los primos divisores son $\rm\equiv 1$ o $\rm\, 63\:\ (mod\ 248),\:$ luego de la prueba de la división por todos los números primos de esta forma por debajo de $\rm\sqrt{M_{31}}.\:$ La restricción en el primer divisores es una consecuencia inmediata de la (ahora) bien conocido de Mersenne factor teorema: para los impares, números primos $\rm\:p,q,\:$ $\rm\: p\mid M_q\:\Rightarrow\: p\equiv 1\,\ (mod\ q),\,\ p\equiv \pm 1\,\ (mod\ 8).\:$

A continuación es un extracto de su 1772 carta de Bernoulli describe este. Ver también esta página. enter image description hereenter image description here

9voto

Alex J Best Puntos 1380

Euler no hizo uso de un equipo de calcular todos los posibles primer divisiones, sin embargo pudo haber utilizado los asistentes a hacer la rutina de cálculo (ver los comentarios y otras respuestas). Él fue, sin embargo, muy muy inteligente y no tengo ninguna duda de que él mismo podría haber realizado los cálculos necesarios de forma muy rápida. Como he mencionado en los comentarios François Arago dijo que "Se calcula sin ningún esfuerzo aparente, como los hombres respiran, como la de las águilas se sostienen en el aire." Él se dio cuenta de algunas de las propiedades de los números primos dividiendo $2^{31}-1$, lo que redujo el cálculo requiere inmensamente. Todos los detalles están aquí.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X