Demostrar que $\forall n > 1 \quad2^n - 1 \pmod n \neq 0$

Question

Demostrar que $\forall n > 1, \quad2^n - 1 \pmod n \neq 0$

He pensado en la inducción pero no se me ocurre cómo probar el paso. El teorema de Fermat (y sus variantes) tampoco son especialmente útiles. ¡Cualquier pista sería muy apreciada!

Answer 1

Suponga que tiene un $n>1$ para que $2^n \equiv 1 \pmod{n}$ . Tome el divisor primo más pequeño $p$ de $n$ .

Usted tiene $p\;|\;n\;|\;2^n-1$ Por lo tanto $2^n\equiv 1 \pmod{p}$ .

Pero también tiene, de El pequeño teorema de Fermat que $2^{p-1}\equiv 1\pmod{p}$ .

Desde $p-1$ y $n$ son coprimas, se tiene así por La identidad de Bézout , algunos $a,b$ tal que $a(p-1)+bn=1$ y luego

$$1\equiv(2^{p-1})^a\cdot (2^n)^b \equiv 2^{a(p-1)+bn}\equiv 2^1 \pmod{p}$$

Así, $2^1\equiv 1\pmod{p}$ o, por el contrario $p\;|\;1$ pero esto no es posible.

Answer 2

Un contraejemplo $\,n\,$ es decir $\ n\mid 2^n-1\,$ contradice el teorema más general que se expone a continuación.

Teorema $\,\ \ \ m,n>1,\,\ m\mid 2^{\large n}-1\,\Rightarrow\, \ell(m) > \ell(n),\ \ $ $\ell(x) =\,$ factor primo menor de $\,x $

Prueba $\quad\ \, {\rm mod}\,\ p = \ell(m)\!:\,\ 2^{\large n}\equiv 1\equiv\, 2^{\large\color{}{ p-1}}\,$ $\Rightarrow$ $\,\ \ell(m) = p > {\rm ord}\,2\color{#80f}{ \ge \ell(n)}$

Nota: $\,\ $ El $ $ clave dea $ $ es: $\ \ 2^n\equiv 1,\,\ \color{#0a0}{2\not\equiv 1}\,$ implica el orden de $\,2\,$ es $\,\color{#80f}{\ge\ {\rm least\ prime}\,\ q\mid n},\ $ porque la orden debe dividir $\,n,\,$ y es $\color{}{\neq \color{#c00}1}$ (si no $\,\color{#0a0}{2^{\color{#c00}{\large 1}}\equiv 1})$ .