IMO SL 1998 N5 - Muy Lindo

Avatar de Usuario
Nacho

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

IMO SL 1998 N5 - Muy Lindo

Mensaje sin leer por Nacho » Mié 30 May, 2012 12:14 am

Determinar todos los enteros positivos [math] para los cuales existe algún entero [math] tal que [math] divide a [math].
"Though my eyes could see I still was a blind man"

Avatar de Usuario
Nacho

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Re: IMO SL 1998 N5 - Muy Lindo

Mensaje sin leer por Nacho » Jue 31 May, 2012 3:16 pm

Spoiler: mostrar
Vamos a recordar un lema: Si [math] es un primo de la forma [math] y [math] entonces [math] y [math].

Si [math] no hay nada que demostrar. Si [math] entonces [math] entonces, tiene algún divisor primo de la forma [math]. Sea [math] un primo de esa pinta tal que [math]. Luego, como [math] se sigue que [math]. Por nuestro lema, se sigue que [math] y [math], de donde [math] y [math]. Se ve entonces que el único divisor que puede tener de esta forma es [math].

Entonces, [math]. Se sigue fácilmente que [math] es par. Si escribimos [math] con [math] impar y hacemos diferencias de cuadrados, nos queda [math].

Supongamos que [math], entonces [math]. Luego, tiene algún divisor primo [math] de la forma [math]. Entonces, por lo que dijimos antes, [math] debe ser [math]. Pero notemos que [math] es impar, entonces [math]. Absurdo.

Se sigue así que [math], y si [math] anda entonces debe ser una potencia de [math].

Ahora demostremos que para todo [math] que sea potencia de [math] entonces existe algún [math] tal que [math].

Vamos a demostrar que el único primo de la forma [math] que aparece en estos números es [math].

Denotamos [math]. Tenemos que [math] por la Propiedad 1 sobre polinomios ciclotómicos y lo evaluamos en [math].

Sea [math] un primo tal que [math]. Por el Teorema 1 tenemos que [math] o [math], de donde si [math] tenemos que es de la forma [math]. Consideramos entonces [math]. Por la propiedad 1, eso es igual a [math]. De donde si [math] es de la forma [math] debe ser [math]. Se ve de esta forma también que [math].

Ahora, sea [math] la factorización en primos de [math]. Quiero que [math], es decir [math] (pues es coprimo con [math]).

Notemos que [math] es residuo cuadrático módulo [math] primo sii es de la forma [math]. Como todos los primos [math] son de esa forma, se sigue que [math] donde [math] es el símbolo de Legendre. El símbolo de Jacobi nos dice [math].

Luego [math] es residuo cuadrático módulo [math]. Por la definición, se sigue que existe un [math] tal que [math] y estamos. [math]
"Though my eyes could see I still was a blind man"

Squee
Mensajes: 139
Registrado: Lun 05 Dic, 2011 1:55 pm
Nivel: Exolímpico
Ubicación: Bariloche

Re: IMO SL 1998 N5 - Muy Lindo

Mensaje sin leer por Squee » Jue 20 Sep, 2012 4:51 am

Desvirtuo un poco, pero me parece interesante el simbolo de Jacobi, lei un poco sobre que servia para algoritmos de primalidad no deterministicos cuando me puse a investigar como funcionaba el algoritmo RSA, que de hecho es un algoritmo que me parece muy simple para el uso que tiene, bello en pocas palabras :p
Dan miedo algunos de los problemas de la IMO :p

Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce OFO - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 99
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: IMO SL 1998 N5 - Muy Lindo

Mensaje sin leer por AgusBarreto » Jue 27 Dic, 2018 5:34 pm

El inicio es el mismo:
Spoiler: mostrar
Nacho escribió:
Jue 31 May, 2012 3:16 pm
Vamos a recordar un lema: Si $p$ es un primo de la forma $4k+3$ y $p \mid a^2 + b^2$ entonces $p\mid a$ y $p \mid b$.

Si $n=1$ no hay nada que demostrar. Si $n\geq 2$ entonces $2^n -1 \equiv 3 \pmod{4}$ entonces, tiene algún divisor primo de la forma $4k+3$. Sea $p$ un primo de esa pinta tal que $p\mid 2^n - 1$. Luego, como $2^n - 1 \mid m^2 + 3^2$ se sigue que $p\mid m^2 + 3^2$. Por nuestro lema, se sigue que $p\mid m$ y $p\mid 3$, de donde $p=3$ y $3\mid m$. Se ve entonces que el único divisor que puede tener de esta forma es $3$.

Entonces, $2^n - 1 \equiv 0 \pmod{3}$. Se sigue fácilmente que $n$ es par. Si escribimos $n=2^i k$ con $k$ impar y hacemos diferencias de cuadrados, nos queda $2^{2^i k} - 1 = (2^k - 1)(2^k+1)(2^{2k}+1)\cdots (2^{2^{i-1}k}+1)$.

Supongamos que $k>1$, entonces $2^k -1 \equiv 3 \pmod{4}$. Luego, tiene algún divisor primo $q$ de la forma $4k+3$. Entonces, por lo que dijimos antes, $q$ debe ser $3$. Pero notemos que $k$ es impar, entonces $2^k - 1 \equiv 1 \pmod{3}$. Absurdo.

Se sigue así que $k=1$, y si $n$ anda entonces debe ser una potencia de $2$.

Ahora demostremos que para todo $n$ que sea potencia de $2$ entonces existe algún $m$ tal que $2^{n}-1 \mid m^2 +9$.
Doy una forma de terminarlo un poco diferente (aunque en el fondo es lo mismo usando menos nombres nuevos):
Spoiler: mostrar
Vamos a usar dos lemas, el usado en la solución anterior que llamaremos Lema 1 y otro que será el Lema 2 (es el Lema 3 del post).
Recordemos que aplicando reiteradas veces diferencia de cuadrados obtenemos
$2^n - 1 = 2^{2^i} - 1 = (2 - 1)(2+1)(2^2+1)(2^{4}+1)\cdots (2^{2^{i-1}}+1)=3\cdot(2^2+1)(2^{4}+1)\cdots (2^{2^{i-1}}+1)$
Supongamos que existe un divisor primo $p$ de $2^{2i}-1$ de la forma $4k+3$ y que $p\neq 3$. Observamos que $p$ debe dividir a alguno de los factores de la pinta $(2^{2^b}+1)$ con $1 \leq b \leq i$, pero por el Lema 1 tenemos que $p \mid 1$ lo cual es absurdo. Luego el único divisor primo de la forma $4k+3$ de $2^n - 1$ es $p=3$. Notemos además que los factores de la pinta $(2^{2^b}+1)$ son impares y coprimos con $3$ ya que $2^{2^b} + 1\equiv 1 + 1 \equiv 2 \pmod 3$. Entonces $2^n-1 = 3 \cdot b$ donde $b$ es un número cuyos divisores primos son todos de la forma $4k+1$ y como consecuencia del Lema 2 tenemos que $-1$ es residuo cuadrático módulo $b$, es decir que existe un $b'$ tal que $b \mid (b')^2 + 1$. Concluímos que
$2^n -1 \mid 3 \cdot (2^n-1) \mid 9 \cdot ((b')^2+1) = (3b')^2 + 9$
y tomando $m=3b'$ ganamos. ■

Responder