Hallar todos los enteros positivos $n$ tales que todos los factores primos de $2^n - 1$ son menores o iguales que $7$.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Por el Teorema de Zsigmondy tenemos que para cada $n\geq 7$ el número $2^n-1$ tiene un divisor primo que no divide a ningún número de la forma $2^k-1$, con $k<n$, en particular no divide a $2^3-1=7$ ni $2^4-1=3\cdot 5$. Se sigue que ningún $n\geq 7$ funciona. Veamos los demás.
$2^1-1=1$. Funciona.
$2^2-1=3$. Funciona.
$2^3-1=7$. Funciona.
$2^4-1=3\cdot 5$. Funciona.
$2^5-1=31$. No funciona.
$2^6-1=63=3^2\cdot 7$. Funciona.
Los $n$ que funcionan son $1$, $2$, $3$, $4$ y $6$.
Es claro que $2^n -1$ no puede tener factores $2$ porque es impar. Los órdenes de $2$, módulo $3$, $5$ y $7$ son $ord_3(2) = 2$, $ord_5(2) = 4$, $ord_7(2) = 3$. De esto se sigue que para un primo $p \geq 5$ (que no es divisible por $2$, $4$ o $3$), $2^p -1$ no es divisible por $3, 5$ o $7$ por lo que en su factorización tiene un primo que no es ninguno de estos. En general para cualquier $n$ divisible por un primo $p \geq 5$, no se verifica el enunciado ya que $2^p -1 | 2^n -1$ al ser:
$$2^p \equiv 1 \; (2^p-1) \Rightarrow 2^n \equiv (2^p)^{\frac{n}{p}} \equiv 1^{\frac{n}{p}} \equiv 1 \; (2^p-1)$$
Luego $n$ debe estar conformado solo por factores primos $2$ y $3$. Si $n$ es divisible por $8$ resulta $17 | 2^8-1 | 2^n-1$ mientras que si $n$ es divisible por $9$ resulta $73 | 2^9 -1 | 2^n -1$ luego $n$ sólo puede ser $n = 1, 2, 3, 4, 6, 12$ que de estos funcionan todos menos el $12$ ya que $13 | 2^{12} -1$.
Tenemos que $2^{p_1^{b_1}p_2^{b_2}p_3^{b_3}.....p_k^{b_k}}-1=(2^{\frac{n}{p_k^{b_k}}}-1)\sum_{i=0}^{p_k^{b_k}-1}(2^{\frac{n}{p_k^{b_k}}}))^i$
$(2^{\frac{n}{p_k^{b_k}}}-1)=(2^{\frac{n}{p_k^{b_k}p_{k-1}^{b_{k-1}}}}-1)\sum_{i=0}^{p_{k-1}^{b_{k-1}}-1}(2^{\frac{n}{p_k^{b_k}p_{k-1}^{b_{k-1}}}})^i$
$(2^{\frac{n}{p_k^{b_k}p_{k-1}^{b_{k-1}}}}-1)=(2^{\frac{n}{p_k^{b_k}p_{k-1}^{b_{k-1}}p_{b_{k-2}}^{k-2}}}-1)\sum_{i=0}^{p_{k-2}^{b_{k-2}}-1}(2^{\frac{n}{p_k^{b_k}p_{k-1}^{b_{k-1}}p_{k-2}^{b_{k-2}}}})^i$
Supongamos que $p$ no divide a $q-1 \Rightarrow mcd(p,q-1)=1 \Rightarrow (q-1)^{p-1}\equiv 1 (p)$. Entonces, $\exists x \equiv (q-1)^{p-2}$ tal que $(q -1)x \equiv 1 (p)$, y $k$ tal que $(q- 1)x-1 = kp$.
Despues, $2^{(q-1)x}\equiv 1(q)$, y como $2^{p}\equiv 1 (q), 2^{pk} \equiv 1(q)$. Entocnes, $\frac {2^{(q-1)x}}{2^{pk}}\equiv 2^{(q-1)x-pk}\equiv 1(q)$. Como $(q- 1)x-1 = kp \Rightarrow (q-1)x-kp=1$, entonces, $q|1$.
Luego, $q=np+1$. Ademas, $n=2k$, ya que $2^{p}-1$ es impar y sus divisores tambien.
Finalmente, $q=2kp+1$.
Entonces, si $n$ contiene algun $p_i, p \in \mathbb{P}, p\geq 5$, lo podemos extraer como hicimos arriba y llegar a que no cumple con las condiciones del enunciado. Si $q|2^5-1$, $q$ es al menos $11$, pero $11>7$.
Aclaracion: $p_1$ lo podemos determinar como aquel primo $> 3$, ya que no necesariamente si $i<j, p_i<p_j$.
Luego, $n=2^a3^b$. Si $a>2, b>1$, es rapido ver que para $a=3$ y $b=2$ esto es imposible.
Entonces, si $a>3,b>2$, "extraemos" $2^33^2$ y $2^n-1$ tiene primos mayores que $7$.
Finalmente, los ejemplos son los que puso @Gianni De Rico
Notemos que $2^n-1$ es impar, entonces $2$ no es uno de los factores primos de $2^n-1$.
Notemos que $2^n-1=\sum^{n-1}_{i=0}2^i$, por lo que si hay un número $d/d|n$, se puede separar los n términos presentes en la suma previamente mencionada en una cantidad entera de grupos, cada uno con d números, y cada uno de los números en el mismo grupo forman una cadena de potencias de 2 consecutivas. Es decir, habrá un grupo con los números $2^0;2^1;2^2;...;2^{d-2};2^{d-1}=2^d-1$ y otros $\frac{n}{d}-1$ grupos más, siendo $\frac{n}{d}$ grupos en total, y cada uno de esos grupos es múltiplo de $2^d-1$, pues los elementos de cada uno de esos grupos son los elementos del primero de los grupos multiplicado por $2^{x.d}$ siendo $x$ entero. Entonces, se puede sacar factor común $2^d-1$ y afirmar que $2^d-1|2^n-1$ si $d|n$, y no sólo eso, sino que si quiero que un primo $p$ sea divisor de $2^n-1$, debo encontrar el menor $d/p|2^d-1$ de forma que todo $n$ múltiplo de $d$ cumplirá (y es fácil ver que si $n$ no es múltiplo de $d$ eso no sucede, pues se tiene un múltiplo de $p$ al que se le suma una potencia de $2$ multiplicada por un número que no es múltiplo de $p$ al ser una suma de potencias de $2$ consecutivas con menos de $d$ términos). Sabiendo esto, encontramos los valores de $d$ para $p=3; p=5$ y $p=7$. Dichos valores serían $2; 4=2^2$ y $3$ respectivamente. Hay algo importante que se puede ver, si $n$ es múltiplo de un primo $q>3$, $2^q-1$ no va a ser múltiplo de $3; 5$ ni $7$, pero va a ser más grande que $1$, entonces tendrá un divisor primo mayor que $7$, por lo que no cumplirá. Luego $n=2^a.3^b$.
Notemos que $17|2^8-1$ y $73|2^9-1$, por lo que $a<3$ y $b<2$, entonces las posibilidades para $n$ son $1; 2; 3; 4; 6$ y $12$, pero probando a mano se ve que $12$ no cumple.
Entonces, los valores de $n$ que cumplen son $1; 2; 3; 4$ y $6$.
1) para n=p primo >3, 2^p - 1 no es divisible ni por 3 ni por 5 ni por 7, por lo que es divisible por algún q primo mayor que 7.
2) si n tiene un divisor primo p > 3, 2^n - 1 es divisible por el q relacionado a p de 1.
3) luego, los divisores primos de n son 2 y 3.
4) por otra parte, viendo casos específicos, n no es divisible ni por 8 (2^n - 1 sería divisible por 17) ni por 9 (2^n - 1 sería divisible por 73) ni por 12 (2^n - 1 sería divisible por 13).
Los casos son 2,3,4,6 (no se si se considera n=1). Notar que para estos casos se cumple
Es claro que $2^n -1$ no puede tener factores $2$ porque es impar. Los órdenes de $2$, módulo $3$, $5$ y $7$ son $ord_3(2) = 2$, $ord_5(2) = 4$, $ord_7(2) = 3$. De esto se sigue que para un primo $p \geq 5$ (que no es divisible por $2$, $4$ o $3$), $2^p -1$ no es divisible por $3, 5$ o $7$ por lo que en su factorización tiene un primo que no es ninguno de estos. En general para cualquier $n$ divisible por un primo $p \geq 5$, no se verifica el enunciado ya que $2^p -1 | 2^n -1$ al ser:
$$2^p \equiv 1 \; (2^p-1) \Rightarrow 2^n \equiv (2^p)^{\frac{n}{p}} \equiv 1^{\frac{n}{p}} \equiv 1 \; (2^p-1)$$
Luego $n$ debe estar conformado solo por factores primos $2$ y $3$. Si $n$ es divisible por $8$ resulta $17 | 2^8-1 | 2^n-1$ mientras que si $n$ es divisible por $9$ resulta $73 | 2^9 -1 | 2^n -1$ luego $n$ sólo puede ser $n = 1, 2, 3, 4, 6, 12$ que de estos funcionan todos menos el $12$ ya que $13 | 2^{12} -1$.
Hola, ¿Que significa orden? ¿Es realmente importante saberlo? Es la primera vez que lo escucho.
$$a | b \land a, b \in \mathbb Z^+ \Rightarrow 2^{a}-1 | 2^b -1$$
Demostración:
Dada la hipótesis $a | b \iff a.k = b, k \in \mathbb Z^+$, ahora veamos que $2^{a} \equiv 1 \pmod{2^{a}-1} \Rightarrow 2^{a.k} - 1 \equiv 0 \pmod{2^{a}-1} \Rightarrow 2^{a}-1 | 2^{a.k}-1 \Rightarrow 2^{a}-1 | 2^b-1$
$\blacksquare$
Ahora si con la solución. Consideremos el mayor primo $p$ tal que $p | n \Rightarrow 2^p-1 |2^n-1$ por lema 2. Ahora consideremos un primo $q$ tal que $q | 2^p-1 \Rightarrow p | q-1$ por lema 1. Entonces por transitividad se cumple que $q | 2^p-1 | 2^n-1$ Pero si $2^n-1$ tiene todos sus factores primos menores o iguales a $7$, entonces lo mismo pasa con $2^p-1$ y $q$, por lo tanto $q \in \{2, 3, 5, 7\}$ y como $p | q-1 \Rightarrow p | 1, 2, 4, 6 \Rightarrow p \in \{2, 3\}$ Lo cual concluye que $\boxed{n = 2^{\alpha_1}.3^{\alpha_2}}$
Ahora es fácil ver que $2^{2^3} \equiv 1 \pmod {17} \Rightarrow 2^{2^3.k} \equiv 1 \pmod {17}$ y $2^{3^2} \equiv 1 \pmod{73} \Rightarrow 2^{3^2.k} \equiv 1 \pmod {73}$. Por lo tanto $n \in \{1, 2, 3, 4, 6, 12\}$, simplemente nos ponemos a probar que valores cumplen y vemos que las soluciones al problema son $\boxed{n \in \mathbb \{1, 2, 3, 4, 6\}}$
El orden de un número $n$ módulo $m$ (que lo denoto como $ord_m(n)$) es el menor entero positivo $k$ que verifica $n^k \equiv 1 \; (m)$, este existe si y solo sí $\gcd(m,n) = 1$.
Es claro que si existe, entonces $\gcd(m,n) = 1$ dado que si compartieran un divisor común $d$ entonces tomando módulo $d$ resultaría $0 \equiv 1 \; (d)$ que es absurdo. La vuelta es menos directa y hay un montón de formas de probarlo, una que me gusta que es muy cortita es así: Sea $A$ el conjunto de restos módulo $m$ que son coprimos con $m$, es claro que $nA$ (o sea el conjunto formado por todos los productos de la forma $na$ con $a \in A$) mirado módulo $m$ es igual a $A$ (ya que multiplicar por $n$ coprimo con $m$ permuta estos elementos módulo $m$) luego:
$$\prod_{a \in A} a \equiv \prod_{a \in A} na = n^{\phi(m)} \prod_{a \in A} a \; (m) \Rightarrow n^{\phi(m)} \equiv 1 \; (m)$$
Por lo que existe algún número que verifica tal cosa, por lo que entre los enteros positivos debe existir alguno que lo verifique y sea mínimo.
La propiedad clave que uso en el problema (y se usa en muchos otros) es que $k$ verifica $n^k \equiv 1 \; (m)$ sí y solo sí $ord_m(n) | k$. Una dirección es trivial y para la otra si $n^k \equiv 1 \; (m)$ entonces si $k$ no fuera divisible por este número podemos escribirlo por algoritmo de la división como $k = ord_m(n) \cdot c + r$ con un $0 < r < ord_m(n)$ y así se verifica $1 \equiv n^k = (n^{ord_m(n)})^c n^r \equiv n^r \; (m)$ pero eso es absurdo porque habíamos dicho que $ord_m(n)$ era el menor entero positivo que verificaba esto, luego $ord_m(n) | k$.
