Si $2^n - 1$ es el primer de un número entero $n$, demostrar que n también debe ser primer.

Question

Entiendo la idea de la prueba. Sólo quiero para asegurarse de que escribí mi prueba bien.

Supongamos que $n$ no es primordial. $\exists x,y \in \mathbb{Z}$ Tal que $n = xy$.

$2^{xy} - 1 = (2^x)^y - 1$

$ = (2^y - 1)(2^{y(x-1)} + 2^{y(x-2)} + ... + 2^{y} + 1)$

Puesto que es divisible por $2^{n} - 1$$2^y - 1$ debe ser que $2^n - 1$ no es primordial. Contradicción. Así $n$ debe ser primer.

¿Cómo funciona este look?

Answer 1

Voy a tratar de recapituate todos los comentarios realizados en una versión adaptada de la prueba.

Si $2^n−1$ es primo de algunos entero$~n$, $n$ también debe ser primo.

Desde la hipótesis requiere de $n\geq2$ para ser verdad, uno puede asumir que. Vamos a comprobar el contrapositivo: si $n\geq2$ no es primo, a continuación, $2^n-1$ no es primo.

Supongamos $n\geq2$ no es primo. Entonces existen enteros $x,y>1$ tal que $n = xy$.

Uno ha $2^n-1 = 2^{yx} - 1 = (2^y)^x - 1 = (2^y - 1)(2^{y(x-1)} + 2^{y(x-2)} + \cdots + 2^{y.1} + 2^{y.0})$. Desde $y>1$ el primer factor $2^y - 1$${}>1$, y desde $x>1$ que factor es menor que $2^n-1$.

Desde $2^n - 1$ tiene una adecuada divisor $2^y - 1$ mayor que$~1$, hemos demostrado que $2^n - 1$ es compuesto, estableciendo el contrapositivo.

Observación. El contrapositivo declaración resultó siendo cierto si los poderes de $2$ son reemplazados en su totalidad por los poderes de algunos entero $a\geq2$. Sin embargo con el cambio ya no es cierto que la hipótesis original requiere de $n\geq2$ $n=1$ podría funcionar. Por lo tanto, una generalización de la declaración original requiere una explícita adicionales hipótesis de $n\geq2$.

Answer 2

Tal vez un menor nit-pick, pero me parece el paso medio debería ser $((2^y)^x-1)$, puesto que están utilizando la identidad $$a^x-1=(a-1)(a^{x-1}+a^{x-2}+\cdots+a+1)$$ with $ un = 2 ^ y$.

Answer 3

Se siente más como prueba por contrapositive que prueba por contradicción. También, aunque obvio, sin condiciones de n, x, y no está claro que $2^y-1$ no puede ser 1.