Demostrar que cualquier número impar es un factor de $2^n -1$ para algunos $n$

Question

Estoy luchando con una prueba de lo siguiente. Siento que debería ser una línea o algo simple pero no estoy captando la idea:

Supongamos que m es un número natural impar. Demostrar que existe un número natural $n$ tal que $m$ divide $2^n -1$

Cualquier ayuda será muy apreciada, gracias.

Answer 1

Un comienzo: Considere los restos cuando $2$ , $2^2$ , $2^3$ , $2^4$ y así sucesivamente se dividen por $m$ .

Por el Principio de Pigeonhole existen enteros positivos distintos $i\lt j$ tal que $2^i$ y $2^j$ tienen el mismo resto en la división por $m$ .

Demostrar que $m$ divide $2^{j-i}-1$ .

Answer 2

$$(2k+1) \mid 2^{\phi(2k+1)} -1 $$ por http://en.wikipedia.org/wiki/Euler%27s_theorem

Answer 3

Quieres encontrar $n$ tal que $$2^n\equiv1\mod m$$ Está claro que los valores de $2^n\text{ mod } n$ comienzan a repetirse después de un tiempo. ¿Puede ocurrir que $1$ ¿se excluye del ciclo? No porque $2$ tiene un inverso $\text{mod }m$ , a saber $(m+1)/2$ , por lo que puede ir a la inversa y debe alcanzar $1$ finalmente.

Answer 4

Dejemos que

$$m=\prod_{k=1}^r p_k^{\alpha_k},\qquad p_k\ne2$$ la descomposición primaria de $m$ y como $\gcd(2,p_k^{\alpha_k})=1$ entonces $\overline 2$ es invertible en $\Bbb Z_{p_k^{\alpha_k}}$ por lo que hay $\mu_k\in\Bbb N$ tal que

$$2^{\mu_k}\equiv 1\pmod {p_k^{\alpha_k}}$$

Ahora concluimos usando el teorema del resto chino y tomamos $n=\sum\limits_{k=1}^r \mu_k$ .