Nacional 2023 N3 P2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1126
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Nacional 2023 N3 P2

Mensaje sin leer por Matías V5 »

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
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 2274
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 19
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2023 N3 P2

Mensaje sin leer por Gianni De Rico »

Se lo dije a toda la gente que me crucé en el Nacional ese día, así que creo que corresponde que suba esto acá
Spoiler: mostrar
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$.
1  
♪♫ do re mi función lineal ♪♫
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 284
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Nacional 2023 N3 P2

Mensaje sin leer por Fedex »

Spoiler: mostrar
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$.
1  
This homie really did 1 at P6 and dipped.
Avatar de Usuario
Lean

OFO - Medalla de Bronce-OFO 2023 FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Plata-OFO 2024
Mensajes: 176
Registrado: Vie 20 Ene, 2023 10:38 am
Medallas: 3
Nivel: 3
Ubicación: Quilmes

Re: Nacional 2023 N3 P2

Mensaje sin leer por Lean »

Si hay errores por favor remarcar.
Spoiler: mostrar
Sea $n=p_1^{b_1}p_2^{b_2}p_3^{b_3}.....p_k^{b_k}, \forall p, p_i \in \mathbb{P}$

$n=1$ sirve.

$(1)$ $2^n-1 \in \mathbb{P}$
Spoiler: mostrar
$2^n-1=M_n$ es un Numero Primo de Mersenne. Luego, los unicos $M_n\leq 7$ son con $n=2$ y $n=3$.
$(2)$ $2^n-1 \notin \mathbb{P}$
Spoiler: mostrar
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$

$......$
$......$


$2^{p_1^{b_1}p_2^{b_2}p_3^{b_3}.....p_k^{b_k}}-1=\sum_{i=0}^{p_k^{b_k}-1}(2^{\frac{n}{p_k^{b_k}}})^i\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}{n}}-1)\sum_{i=0}^{p_1^{1}-1}(2^{\frac{n}{n}})^i$
$2^{p_1^{b_1}p_2^{b_2}p_3^{b_3}.....p_k^{b_k}}-1=\sum_{i=0}^{p_k^{b_k}-1}(2^{\frac{n}{p_k^{b_k}}})^i\sum_{i=0}^{p_{k-1}^{b_{k-1}}-1}(2^{\frac{n}{p_k^{b_k}p_{k-1}^{b_{k-1}}}})^i...\sum_{i=0}^{p_1^{b_1}-1}(2)^i$

Ahora bien, $\sum_{i=0}^{p_1^{b_1}-1}(2)^i=2^{p_1^{b_1}}-1=(2^{p_1})^{p_1^{b_1-1}}-1=(2^{p_1}-1)\sum_{i=0}^{p_1^{b_1-1}-1}(2^{p_1})^i$


Lema: Si $p \in \mathbb{P} \neq 2, \forall q, q|2^p-1, q=2pk+1$
Spoiler: mostrar
$q\in \mathbb{P}, q|2^p-1 \Rightarrow 2^p \equiv 1(q)$. Por Fermatito, $2^{q-1} \equiv 1 (q)$.

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
"El mejor número es el 73".
Ignacio Daniele

OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Copa-FOFO 13 años OFO - Medalla de Plata-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024
Mensajes: 27
Registrado: Jue 26 May, 2022 8:27 pm
Medallas: 4

Re: Nacional 2023 N3 P2

Mensaje sin leer por Ignacio Daniele »

Spoiler: mostrar
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$.
2  
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Nacional 2023 N3 P2

Mensaje sin leer por usuario250 »

pista
Spoiler: mostrar
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
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024
Mensajes: 791
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 3
Nivel: 3
Contactar:

Re: Nacional 2023 N3 P2

Mensaje sin leer por drynshock »

Fedex escribió: Sab 18 Nov, 2023 12:30 am
Spoiler: mostrar
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.

Acá mi solución:
Spoiler: mostrar
Lema 1:
Spoiler: mostrar
$q | 2^p - 1 \Rightarrow p | q-1$

Este es un lema muy conocido, por lo tanto no voy a hacer su demostración...
Spoiler: mostrar
Fuente: Créanme
1)Es la primera vez que lo uso
2)No tengo idea como se llama
3)Lo encontré en google
4)Ni siquiera pude demostrar que funciona
Lema 2:
Spoiler: mostrar
$$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\}}$
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 284
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Nacional 2023 N3 P2

Mensaje sin leer por Fedex »

Hola Drynshock
Spoiler: mostrar
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$.
1  
This homie really did 1 at P6 and dipped.
Responder