Demuestre que si $n$ es un número entero positivo y $n|2^n-1$ entonces $n=1$ .

Question

Tengo muy poca experiencia con las pruebas y me cuesta empezar con esto.

Hasta ahora he tratado de demostrarlo usando la ecuación de la división $a=bq+r$ para demostrar que el resto $r+1$ nunca es cero para $n>1$ para $2^n=nq+(r+1)$ . Los casos triviales son sólo eso, y la parte con la que supongo que estoy teniendo problemas es cómo generalizar eso, para aplicarlo a cualquier n (si es que es una buena manera de hacerlo).

Answer 1

Supongamos que $n \neq 1$ .

Dejemos que $p$ sea el primo más pequeño que divide a $n$ . Escriba $n= p^k \cdot l$ .

Ahora, usted sabe que $$1 \equiv 2^n \equiv (2^l)^{p^k} \pmod p$$

Utilice el hecho de que $a^p \equiv a \pmod p$ para concluir que $ (2^l)^{p^k} \equiv 2^l \pmod{p}$ .

Esto demuestra que $$2^l \equiv 1 \pmod{p}$$ También sabe que $$2^{p-1} \equiv 1 \pmod{p}$$

Esto hace que $2^{\gcd (l, p-1)}\equiv 1 \pmod{p}$ .

Ahora bien, si $\gcd(l, p-1) \neq 1$ es divisible por un primo $q$ . Este primo divide $l$ por lo que $n$ y $q$ también divide $p-1$ y por lo tanto es menor que $p$ . Pero esto contradice que $p$ es el primo más pequeño que divide a $n$ .

Por lo tanto, podemos concluir que $\gcd (l, p-1)=1$ .

Así, $2^1 \equiv 1 \pmod{p} \Rightarrow p\mid 2-1=1$ .

Esto es una contradicción.