Encontrar el menor Divisor primo de $2^{17}-1$

Question

Muestran que el menor divisor primo de $2^{17}-1$ es $2^{17}-1$ sí.

Esta pregunta es realmente molesta. Deje $N=2^{17}-1$. Lo que quiero saber es que si $q\mid N$,, a continuación, $q=34k+1$ para algunos $k \in \Bbb{N}$ e $q \equiv \pm1 \pmod 8$. Por lo tanto,

$$q \equiv 2k+1 \equiv \pm1 \pmod 8$$

Llegamos $k \equiv -1, 0 \pmod 4$. Por lo $q=136x+1$ o $q=136x-33$ para algunos $x \in \Bbb{N}$.

Esto es todo lo que sé acerca de encontrar un divisor primo de la forma ${2^{p}-1}$, que podría ser la de Mersenne número. Pero tengo que acaba de sustituir a cada posible valor de $q$ a $N$ con el fin de mostrar que es lo que en definitiva no tiene primos divisores distintos de $N$ sí? Se necesita mucho tiempo y esfuerzo. Y no creo que el problema es simplemente hacer que los estudiantes tediosamente sustituir cada caso uno por uno(si es así, entonces estoy tan frustrado).

Así que la pregunta: ¿hay alguna más ahorro de tiempo de modo de distinguir ciertos tipos de Mersenne número sin subir demasiado lejos de mi comprendiendo de la Teoría de los números? O debo sustituir uno por uno y que es la mejor opción que puedo tomar?

Gracias!

Editado Esta fue una pregunta que me desconcertó acerca de unos meses, y después de estudiar el caso para una perfecta números, ahora sé que $2^{17}-1$ es una de Mersenne número(en relación con el número perfecto de la $8589869056$). Pero aún creo que solo memorizar el caso de que no me da la plena comprensión de esta área.

Answer 1

Deje $p|2^{17} - 1$, luego tenemos a $2^{17} \equiv 1 \pmod p$, pero también hemos de Fermat Poco Teorema $2^{p-1} \equiv 1 \pmod p$.

Teorema de Lagrange para el grupo de fin de conseguir que la $2^{lcm(p-1,17)} \equiv 1 \pmod p$.

Obivously el mínimo común múltiplo es $17$, porque de lo contrario $2 \equiv 1 \pmod p$, lo cual es imposible.

Luego tenemos a $17 \mid p-1$ y debido a $p-1$ es aún tenemos $34\mid p-1$. Así que tenemos que comprobar todos los números primos de la forma $p=34k + 1 \quad \forall k \in \mathbb{N}$ tal que $p \in (1,\sqrt{2^{17} - 1}]$. Lo que reduce el número de divisores de comprobar. En realidad, hay sólo $4$ de los números primos en este inteval, esos son $103, 137, 239, 307$. Usted puede comprobar que ninguno de ellos se divide $2^{17} - 1$, lo que implica que $2^{17} - 1$ es primo.

También se puede comprobar cómo Euler demostró que $2^{31} - 1$ es primo, y aplicar el mismo método en $2^{17} - 1$.

De hecho $2^{17} - 1 = 131071$ no es grande el número, incluso sin conocimientos en la teoría de los números no es hord trabajo que hacer.

Y por último, como otros usuarios han sugerido el uso de Lucas-Lehmer de la Prueba.