Demostrar que $2^{66}-1$ no es un número primo

Question

Acabo de empezar a estudiar Matemáticas Discretas y uno de los ejercicios que se pide probar que:

$$2^{66} - 1 \textrm{ is not a prime number}$$

El autor sugiere la utilización de la conocida relación:

$$x^2 - 1 = (x + 1)(x - 1)$$

Mi prueba va como tales (por favor, perdóname - y no me corrija si puedo utilizar cualquier mal símbolo o término). Vamos a definir el conjunto de $X$ como:

$$X=\{n\in\mathbb{N}\;|\;n>2\}$$

$\forall x\in X$ se definen dos números:

$$\begin{align}a & = x+1\\ b & = x-1\end{align}$$

Debido a $x>2$,$a>1$$b>1$. Por lo tanto, tenemos

$$c=a\cdot b$$

que no puede ser un número primo, porque:

$$\frac{c}{a}=b \quad \textrm{or} \quad \frac{c}{b}={a}$$

Esto, en mi opinión, es la prueba del teorema.

Podría usted por favor, hágamelo saber si mi prueba es correcta, o si no, ¿cómo demostrar el teorema?

Muchas gracias!

Valerio

Edit: Como se ha mencionado en los comentarios/respuestas que figuran a continuación, que no mostraron la factorización, así que aquí vamos:

$$2^{66}-1=(2^{33}+1)(2^{33}-1)$$

Ahora entiendo que no es necesario usar todos los pasos de arriba, pero yo estaba tratando de dar un general de la prueba, no sólo para el caso concreto.

De todos modos, gracias a todos por sus respuestas y mostrar interés en mi pregunta. No me lo esperaba para crear así un gran debate! :-)

Answer 1

La prueba es correcta.

Sólo un pequeño consejo para un problema como este, usted no necesita tener un complejo de la prueba. Sólo debe ser suficiente para mostrar que $$2^{66}-1=(2^{33}+1)(2^{33}-1)$$ y, a continuación, mostrar que $$2^{33}+1 \ne 1 \ne 2^{33}-1$$ $$2^{33}+1 \ne 2^{66}-1 \ne 2^{33}-1$$ Que debe ser bastante simple.

Pero su prueba parece bien a mí!

Edit: Hay una cosa que se ha perdido, como @AndrewD.Hwang señaló en los comentarios - que en realidad no han demostrado que la $2^{66}-1$ puede ser factorizado en la forma en que se decidió a utilizar.

Pero eso está bien, es una solución rápida!

Answer 2

Cuidado: overkill. Espero una interesante overkill.
Deje $\omega(n)$ ser el número de los distintos factores primos de a$n$$\nu_3(n)=\max\{m\in\mathbb{N}: 3^m\mid n\}$.

---

$$2^{66}-1 = (2^{33}-1)(2^{33}+1),\qquad \gcd(2^{33}+1,2^{33}-1)=\gcd(2^{33}+1,2)=1 $$ por lo tanto $\omega(2^{66}-1) = \omega(2^{33}-1)+\omega(2^{33}+1)$. Además $$ 2^{33}-1 = (2^{11}-1)(2^{22}+2^{11}+1),$$ $$ \gcd(2^{22}+2^{11}+1,2^{11}-1)=\gcd(3,2^{11}-1)=1 $$ a partir de que $\omega(2^{33}-1)\geq 2$. En una manera similar $$ 2^{33}+1 = (2^{11}+1)(2^{22}-2^{11}+1),$$ $$ \gcd(2^{22}-2^{11}+1,2^{11}+1)=3$$ y desde $\nu_3(2^{33}+1)=2$ también contamos $\omega(2^{33}+1)\geq 3$ y $$\boxed{ 2^{66}-1\text{ has at least }\color{red}{5}\text{ distinct prime factors}.} $$

---

En realidad $2^{66}-1$ $8$ distintos factores primos, y el más pequeño de ellos, $\{3,7,23, 67,89\}$, no son difíciles de reconocer. $2,6,22,66$ son divisores de $66$, lo $\{3,7,23,67\}$ son primos divisores de $2^{66}-1$ por Fermat poco teorema. $89$ es un divisor desde $89\mid(2^{11}-1)\mid(2^{66}-1)$.

Answer 3

La prueba es correcta, pero tengo tres críticas.

1) nunca en realidad la respuesta a la pregunta de si $2^{66} -1$ es primo o no.

En algún lugar es necesario indicar que si $n = 2^{33}$ $2^{66}-1 = n^2 -1$ que no es primo. Sí, es obvio. Pero en realidad nunca se indica cómo lo estaban probando se aplica a la pregunta en cuestión.

(Sé... era obvio y fue muy claro para usted.... pero, no obstante, debe ser indicado.)

2) la Adición de las variables $a,b,c$ simplemente ofusca.

Es más directa, simplemente, decir $n^2 - 1 = (n+1)(n-1)$. Así que si $n+1$ $n-1$ número natural distinto de $1$ ( $n > 2$ ), a continuación, $(n+1)(n-1) = n^2 -1$ es compuesto y no prime.

3) en realidad no tiene para el estado o demostrar que $x^2 - 1$ no es primo para $x > 2$. Es suficiente para el uso como una sugerencia.

La prueba se puede hacer en una sola frase:

$2^{66} = (2^{33} + 1)(2^{33} -1)$ $2^{66} -1$ tiene factores distintos de sí mismo y $1$, por lo que no es primo. QED.

Answer 4

Estoy sorprendido de que no ha habido ni una sola mención del término "Mersenne prime" o al menos "de Mersenne número" en las respuestas hasta el momento. Tengo que admitir que, aparte de ese detalle, la respuesta que le voy a dar no es diferente de las demás.

Es un hecho bien conocido que si $2^n - 1$ es primo (a Mersenne prime), a continuación, $n$ debe ser primo. Y también es bien sabido que si $n$ es primo, entonces $2^n - 1$ no es necesariamente primo.

De hecho, es mucho más probable que un ser compuesto. $2^{74207281} - 1$ se cree para ser el $49$th Mersenne prime, y $74207281$ es en sí mismo el $4350601$st prime en general. Supongo que encontrar un centenar de Mersenne prime exponentes entre el$37156667$$74207281$. Eso es raro, pero aún así quiere decir que menos de $1\%$ de los números primos hasta el $74207281$ son de Mersenne prime exponentes.

El hecho de que los compuestos de $n$ $2^n - 1$ también está compuesto ha sido conocido desde antes de Marin Mersenne del tiempo. El uso de la sugerencia que se le dio a usted, tenga en cuenta que $$2^{2m} = (2^m)^2.$$ Since $66 = 2 \veces 33$, it follows that $$2^{66} - 1 = (2^{33} - 1)(2^{33} + 1).$$ Clearly $1 < 2^{33} - 1 < 2^{33} + 1 < 2^{66} - 1$, meaning that $2^{66} - 1$ is divisible by positive integers other than $1$ y sí mismo.

Answer 5

Sugerencia: Empezar vamos a $2^{66}-1$, Entonces el factor de la siguiente manera: $$2^{66}-1=(2^{33})^2-1=(2^{33}+1)(2^{33}-1).$$ Ahora, para continuar a partir de aquí.