Selectivo de Ibero 2004 P2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Selectivo de Ibero 2004 P2

Mensaje sin leer por Ivan »

Hallar todos los primos positivos $p$ tales que$$\frac{2^{p-1}-1}{p}$$es un cuadrado.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Agusanso

OFO - Medalla de Bronce-OFO 2015
Mensajes: 87
Registrado: Mar 20 Mar, 2012 7:56 pm
Medallas: 1
Nivel: 2

Re: Selectivo de Ibero 2004 P2

Mensaje sin leer por Agusanso »

Spoiler: mostrar
Puede que solo ande para "p" cuando es 3 o 7?
Aguante el paco vieja
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Selectivo de Ibero 2004 P2

Mensaje sin leer por jhn »

Spoiler: mostrar
Sí, los únicos que cumplen son 3 y 7.


[math] no cumple, así que supongamos [math] y [math]. Como [math] y los dos factores del miembro derecho son coprimos, debe darse uno de los dos casos siguientes:

(a) [math] y [math] para ciertos enteros positivos [math]. En este caso [math] debe ser impar, digamos [math]. Entonces [math], de donde [math], es decir que [math] es múltiplo de 2 pero no de 4, lo que sólo puede ocurrir si [math], que cumple la condición pues [math].

(b) [math] y [math] para ciertos enteros positivos [math]. En este caso [math] y tanto [math] como [math] deben ser potencias de 2, pero como difieren en 2 esto sólo ocurre si son 2 y 4, es decir si [math]. Entonces de [math] se sigue [math] y [math], que es efectivamente solución pues [math].
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
MathIQ

OFO - Medalla de Bronce-OFO 2023 OFO - Medalla de Plata-OFO 2024
Mensajes: 106
Registrado: Dom 17 Jul, 2022 11:59 pm
Medallas: 2
Nivel: 2

Re: Selectivo de Ibero 2004 P2

Mensaje sin leer por MathIQ »

Spoiler: mostrar
Sabemos que:
$\frac{2^{p-1} -1}{p}$ = $k^2$
Con $p$ primo, de donde sale que:
$2^{p - 1} -1$ = $p . k^2$ y como $2^{p-1}$ $- 1$ = $2. 2^{p-2}$ $-1$ $≡$ $1 (mód 2)$ $\Rightarrow$ $p ≠ 2$.
Veamos que:
$2 ≡ -1 (mód 3)$ $\Rightarrow$ $2^{p-1} ≡ 1 (mód 3)$ $\Rightarrow$ $2^{p-1} -1 ≡ 0 (mód 3)$.
Notemos que:
$2^{p -1} - 1 = p . k^2$ $\Rightarrow$ $p ≡ 0 (mód 3)$ ($p = 3$) o $k^2 ≡ 0 (mód 3)$ $\Rightarrow$ $k ≡ 0 (mód 3)$.
Veamos el el primer caso, $p = 3$ efectivamente funciona, veamos que sucede para el segundo caso:
Como $k ≡ 0 (mód 3)$ $\Rightarrow$ sea $k = 3x$, para algún $x$ perteneciente a los naturales y cero $\Rightarrow$ $k ^ 2 = 9x^2$, veamos que $x ≡ 1 (mód 2)$, por ser $2^{p-1}$ $-1$ impar.
Cómo:
$2^ {p - 1} - 1 = 9x^2$, se tiene que $9 | 2^{p-1} -1$, cómo $p - 1$ es par, se tiene $2^{2r} ≡ 1 (mód 9)$, para algún $r$, de esto sale que $4^r ≡ 1 (mód 9)$, de donde $r$ es de la forma $3t$, para algún $t$.
Es decir sabemos que $2^ {3t} ≡ 1 ≡ 8^t ≡ (-1)^t (mód 9)$, de donde $t ≡ 0 (mód 2)$, es decir $t = 2 . l$, para algún $l$, es decir $r = 6l$ y $p = 6l + 1$.
Remplazando:
$\frac{2^ {6l} -1}{6l + 1}$ = $9x^2$
$64^l -1 = (54l + 9) . x^2$
$\frac{64^l -1}{54l + 9}$ = $x^2$
De donde $\sqrt{\frac{64^l -1}{54l + 9}}$ = $x$ (1)
Es decir $64^l - 1 = 54l + 9$ $\Rightarrow$ $l = 1$ $\Rightarrow$ $p = 7$, o $64^l - 1 ≠ 54l + 9l$ $\Rightarrow$ $l ≠ 1$ $\Rightarrow$ $p ≠7$.
Veamos que el primer caso ($p=7$) funciona, veamos que sucede para el segundo caso:
Notemos que (1) es igual a:
$\frac{\sqrt{64^l -1}}{\sqrt{54l + 9}}$ = $x$
Notemos que $\sqrt{64^l -1}$ = $\sqrt{8^{2l} -1}$, pero como $8^{2l}$ ya es un cuadrado perfecto, entonces al restarle $1$ es imposible que nos dé otro cuadrado perfecto, ya que es lo mismo que suponer que existe un $x^2$, tal que $x^2$ e $x^2 -1$ sean ambos cuadrados perfectos, lo que nos lleva a que $\sqrt{64^l -1}$ no es entero, por ende al dividirlo por $\sqrt{54l + 9}$ el resultado no será entero, ya que un número no entero dividido por otro no entero o entero distinto de si mismo y cero, el resultado será otro no entero, por ende es un absurdo, ya que $x$ es entero, por ende $l = 1$, lo que nos lleva a $p = 7$.
Por lo tanto queda demostrado que los dos únicos $p$ son $p = 3$ y $p = 7$.
Última edición por MathIQ el Sab 17 Jun, 2023 3:00 pm, editado 4 veces en total.
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1136
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Selectivo de Ibero 2004 P2

Mensaje sin leer por Fran5 »

@MathIQ para usar módulo en LaTeX podes usar el comando \pmod

4 \equiv 1 \pmod{3}

que te queda

$4 \equiv 1 \pmod{3}$

:D
1  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
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: Selectivo de Ibero 2004 P2

Mensaje sin leer por Lean »

Spoiler: mostrar
Si $p=2$, vemos que no funciona. Entonces, para todo $p, 2|p-1$

$2^{p-1}-1 \Rightarrow (2^{(p-1)/2}-1)(2^{(p-1)/2}+1)$. Por Fermatito, $2^{p-1} \equiv 1$(mod p), luego $2^{(p-1)/2} \equiv 1$(mod p).

$(1)$ Sea $(p-1)/2=t$, entonces $p|2^t-1$.

$(2)$ Pero si $(p-1)/2=1$, nos resulta que $p=3$ y $2^1 \equiv 2$(mod 3). Es decir, en este caso, $p|2^{(p-1)/2}+1$.

$(1)$ $mcd((2^{(p-1)/2}-1),(2^{(p-1)/2}+1))=1$, ya que si hubiera otro $p>1$ tal que divide a los dos, $p|(2^{(p-1)/2}+1)-(2^{(p-1)/2}-1)=2$
y $p \neq 2$.

Es decir que los dos terminos no comparten ningun primo en su factorizacion.

Si $p|2^t-1$, necesariamente tiene que ser $p*a^2$ y $2^t+1=b^2$.
$2^t=b^2-1 \Rightarrow (b-1)(b+1)$, como tanto $(b-1)$ y $(b+1)$ son potencias de 2 y $mcd(b-1,b+1)=2$, $b-1=2$ y $b+1=4 \Rightarrow b=3 \Rightarrow t=3 \Rightarrow p=7$.

$(2)$ Vemos que en el caso que $p|2^{(p-1)/2}+1$, $p$ es necesariamente $3$. Como funciona, $p=3$, ya los tenemos. $\blacksquare$
"El mejor número es el 73".
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: Selectivo de Ibero 2004 P2

Mensaje sin leer por drynshock »

Lean escribió: Sab 17 Jun, 2023 12:06 pm
Spoiler: mostrar
Por Fermatito, $2^{p-1} \equiv 1$(mod p), luego $2^{(p-1)/2} \equiv 1$(mod p).
De donde sale esa implicación? Es decir hasta lo que tengo entendido
Spoiler: mostrar
No se puede aplicar raíz cuadrada a ambos miembros, un contraejemplo seria:

$2^2 \equiv 1 \pmod 3 \Rightarrow \sqrt{2^2} \equiv \sqrt{1} \pmod 3 \Rightarrow 2 \not\equiv 1 \pmod 3$
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
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: Selectivo de Ibero 2004 P2

Mensaje sin leer por drynshock »

Spoiler: mostrar
Simplemente probando con los casos chicos podemos ver que $p = 3$ y $p = 7$ funcionan, a partir de ahora $p > 7$.

$\frac{2^{p-1}-1}{p} = a^2 \Rightarrow 2^{p-1}-1 = a^2.p \Rightarrow (2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1) = a^2.p$

Esta claro que $\frac{p-1}{2}$ es entero, entonces tanto $2^{\frac{p-1}{2}}-1$ y $2^{\frac{p-1}{2}}+1$ son enteros y lo mas importante es que son coprimos ya que difieren en $2$ y además son impares. Entonces, si tomamos un primo $q$ tal que $q | 2^{\frac{p-1}{2}} +1$ entonces $q \not| 2^{\frac{p-1}{2}}+1$ y viceversa. Sabiendo esto, podemos tomar $a = x.y$, tal que $x | 2^{\frac{p-1}{2}}-1$ e $y | 2^{\frac{p-1}{2}}+1$. Luego, podemos plantear los siguientes sistemas de ecuaciones.

$$\left\{ 2^{\frac{p-1}{2}}-1 = x^2 \atop 2^{\frac{p-1}{2}}+1 = y^2.p \right.$$

$$\left\{ 2^{\frac{p-1}{2}}-1 = x^2.p \atop 2^{\frac{p-1}{2}}+1 = y^2 \right.$$

El primero lo podemos descartar fácilmente ya que $2^{k}-1 \equiv 3 \pmod 4$ cuando $k \geq 2$, entonces $2^{\frac{p-1}{2}}-1 \equiv 3 \pmod 4$ cuando $\frac{p-1}{2} \geq 2 \Rightarrow p \geq 5$. Como ya habíamos analizado antes todos los casos hasta el $7$, descartamos este caso.

Ahora, siguiendo con el segundo sistema, podemos ver que si despejamos la segunda ecuación obtenemos: $2^{\frac{p-1}{2}} = (y-1)(y+1)$ entonces se cumple que:

$$\left\{ 2^m = y-1 \atop 2^n = y+1 \right.$$

Para $m, n \in \mathbb Z^+_0$. Despejando $y$ obtenemos $y = 2^m +1 = 2^n -1 \Rightarrow 2^m + 2 = 2^n \Rightarrow 2(2^{m-1}+1) = 2^n$. Y claramente $m = 1 \Rightarrow n = 2 \Rightarrow y = 3$ de lo cual se sigue que $2^{\frac{p-1}{2}}+1 = 3^2 \Rightarrow 2^{\frac{p-1}{2}} = 2^3 \Rightarrow \frac{p-1}{2} = 3 \Rightarrow p = 7$ y como ya habíamos visto, $p = 7$ es solución.

Concluimos que $p = 7$ y $p = 3$ son las únicas soluciones al problema.

$\blacksquare$
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
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: Selectivo de Ibero 2004 P2

Mensaje sin leer por drynshock »

Dato, es el mismo problema que el que tomaron en 1995 en la olimpiada nacional de India.

Video: https://www.youtube.com/watch?v=AmoR8uD ... ichaelPenn
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Responder