Nacional 2017 N2 P4

Avatar de Usuario
BrunoDS

OFO - Medalla de Plata
Mensajes: 63
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 1
Nivel: 2
Ubicación: Martínez

Nacional 2017 N2 P4

Mensaje sin leer por BrunoDS » Sab 18 Nov, 2017 4:18 pm

Hallar todos los enteros positivos $a$ tales que $4x^2 + a$ es primo para todo $x = 0, 1, ..., a-1$.
$B > \frac{1}{n} \sum\limits_{i=1}^n x_i$

Avatar de Usuario
3,14

OFO - Medalla de Plata FOFO 6 años - Medalla Especial OFO - Medalla de Oro
Mensajes: 438
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 5
Nivel: Exolímpico

Re: Nacional 2017 N2 P4

Mensaje sin leer por 3,14 » Sab 18 Nov, 2017 4:56 pm

Espero no haberme olvidado de nada
Spoiler: mostrar
En primer lugar notemos que $a=3$ y $a=7$ son solución. Demostraremos que son las únicas.
En primer lugar demostraremos que si $a$ es solución, entonces $a+1$ es una potencia de dos. Para ello procedamos por el absurdo, y supongamos que no es así. Entonces existe un primo $p$ impar tal que $a+1\equiv 0\pmod p$.
Entonces:
$4x^2+a\equiv 4x^2-1\equiv (2x-1)(2x+1)\pmod p$
Notemos entonces que si $x=\frac {p-1}{2}$ (que se puede calcular porque $p$ es impar), entonces:
$4x^2+a\equiv 0\pmod p$
Y además, como $p\mid a+1\Rightarrow a+1\geq p\Rightarrow \frac {p-1}{2}\leq \frac {a}{2}$, por lo que $x=\frac {p-1}{2}$ entra dentro del rango posible de valores de $x$, ya que $\frac {a}{2}\leq a-1$ para todo $a\geq 2$ (y el caso $a=1$ se descarta en seguida).
Entonces, siempre que $a+1$ no sea potencia de dos, existe un $x$ tal que $4x^2+a$ es divisible por algún primo $p$ impar. Quedaría analizar si es posible que $4x^2+a=p$. Pero notemos que si $x\geq 1$, entonces el lado izquierdo es mayor o igual que $a+4$, que es mayor que $p$ por lo que vimos antes, y es imposible. Y si $x=0$, queda que $a=p$. pero $p\mid a+1$. Imposible! Entonces concluimos que $a+1$ debe ser potencia de dos.
Sea entonces $a=2^k-1$. Vamos a demostrar que si $k\geq 4$ no hay solución:
$4x^2+2^k-1=4(x^2+2^{k-2})-1$
Podemos sacar factor común porque $k\geq 4$.
Si logramos encontrar $y\in \mathbb N$ tal que $x^2+2^{k-2}=y^2$, entonces:
$4x^2+2^k-1=(2y-1)(2y+1)$
Si $y\geq 2$ entonces habremos encontrado una factorización para algún $x$, y ninguno de los factores es $1$, por lo que no es primo.
Veamos que esto siempre es posible:
$x^2+2^{k-2}=y^2$
$(y-x)(y+x)=2^{k-2}$
Vamos a intentar que se cumpla esta igualdad con el siguiente sistema de ecuaciones:
$y-x=2$
$y+x=2^{k-3}$
Veamos que siempre hay solución:
$y=x+2$
$x+2+x=2^{k-3}$
$2x=2^{k-3}-2$
$x=2^{k-4}-1$
Esta última división se puede hacer porque $k\geq 4$.
$y=2^{k-4}+1$
Faltaría analizar únicamente qué pasa si $y=1$. Esto ocurrirá solo si $k=4$. Pero si $k=4$, $a=15$, y eligiendo $x=0$ se ve que este $a$ no funciona.
Entonces probamos que $a$ es de la forma $a=2^k-1$, con $k\leq 3$. Probando se verifica inmediatamente que los únicos valores posibles son $3$ y $7$. $\blacksquare$
[math]

Avatar de Usuario
BrunoDS

OFO - Medalla de Plata
Mensajes: 63
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 1
Nivel: 2
Ubicación: Martínez

Re: Nacional 2017 N2 P4

Mensaje sin leer por BrunoDS » Sab 18 Nov, 2017 5:33 pm

Otra forma de ver el caso en que $a + 1$ es una potencia de $2$:
Spoiler: mostrar
Notemos que si $a + 1$ y $a + 9$ son ambas potencias de $2$, entonces deben ser $8$ y $16$ respectivamente. Esto sólo ocurre cuando $a =7$, así que supongamos que $a \geq 11$.

Luego, como $a + 9$ no es una potencia de $2$, notemos que existe un primo $p \not= 2$ tal que $p \mid a + 9 \Leftrightarrow a \equiv -9$ $(mod$ $p)$. Además, como $a$ es impar, $a + 9$ es par, por lo que $p \le \frac{a + 9}{2}<a \Leftrightarrow 9<a$, lo cual es cierto.

Entonces, elegimos el número $x = \frac {p - 3}{2}$. Notemos que como $p$ es impar, $x$ es un número entero. Además, como $3 \le p < a$ entonces $0 \le \frac {p - 3}{2}< a$, por lo que $\frac {p - 3}{2}$ es un posible valor de $x$.

Reemplacemos $x = \frac {p - 3}{2}$ en la expresión y mirémosla módulo $p$ (recordemos que $a \equiv -9$ $(mod$ $p)$):

$4x^2 + a = 4 (\frac {p - 3}{2})^2 + a = p^2 - 6p + 9 + a \equiv 9 - 9 \equiv 0$ $(mod$ $p)$

Luego, como $4x^2 + a$ es primo y $p \mid 4x^2 + a$, entonces $4x^2 + a = p$. Pero $4x^2 \geq 0$ y $a > p$. Absurdo.
Última edición por BrunoDS el Mar 12 Dic, 2017 1:46 pm, editado 2 veces en total.
$B > \frac{1}{n} \sum\limits_{i=1}^n x_i$

fibonacci
Mensajes: 7
Registrado: Jue 22 Jun, 2017 4:40 pm
Nivel: 2

Re: Nacional 2017 N2 P4

Mensaje sin leer por fibonacci » Sab 18 Nov, 2017 6:16 pm

Se puede usar congruencia módulo 4?

Avatar de Usuario
BrunoDS

OFO - Medalla de Plata
Mensajes: 63
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 1
Nivel: 2
Ubicación: Martínez

Re: Nacional 2017 N2 P4

Mensaje sin leer por BrunoDS » Sab 18 Nov, 2017 6:27 pm

fibonacci escribió:
Sab 18 Nov, 2017 6:16 pm
Se puede usar congruencia módulo 4?
Hay una solución mirando módulo $4$, $8$ y $16$.
$B > \frac{1}{n} \sum\limits_{i=1}^n x_i$

guillermovil
Mensajes: 1
Registrado: Jue 23 Nov, 2017 3:52 pm
Nivel: Otro

Re: Nacional 2017 N2 P4

Mensaje sin leer por guillermovil » Jue 30 Nov, 2017 5:11 pm

Hola! No soy olimpico, ni matemático, ni profe, solo acompañante de las oma '17.
Me pregunto, no hay una solución teniendo en cuenta el teorema fundamental de la aritmética? Intenté armar algo, pero no me sale.
Saludos.

Avatar de Usuario
Marco V

OFO - Medalla de Bronce
Mensajes: 44
Registrado: Lun 07 Nov, 2016 3:08 pm
Medallas: 1
Nivel: 2

Re: Nacional 2017 N2 P4

Mensaje sin leer por Marco V » Sab 02 Dic, 2017 1:48 pm

guillermovil escribió:
Jue 30 Nov, 2017 5:11 pm
Hola! No soy olimpico, ni matemático, ni profe, solo acompañante de las oma '17.
Me pregunto, no hay una solución teniendo en cuenta el teorema fundamental de la aritmética? Intenté armar algo, pero no me sale.
Saludos.
Justamente lo que se trata de ver en las soluciones es para qué casos se cumple el enunciado y el resto demostrar que el número es divisible por un primo distinto de sí mismo, luego de lo cual no puede ser primo

Responder