OFO 2020 Problema 16

Problemas que aparecen en el Archivo de Enunciados.
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 394
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

OFO 2020 Problema 16

Mensaje sin leer por jujumas » Mar 21 Ene, 2020 11:54 pm

Decimos que un entero positivo $k$ es buenardo si existen enteros positivos $x$ e $y$ tales que $x^2+y^2 = k$. Si no existen estos enteros positivos, entonces $k$ es malardo.
Demostrar que existen infinitos enteros positivos $n$ tales que $n$ y $n+2020$ son buenardos, pero $n+1,~n+2,~n+3,~\ldots,~n+2018,~n+2019$ son todos malardos.
3  

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 394
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

Re: OFO 2020 Problema 16

Mensaje sin leer por jujumas » Sab 01 Feb, 2020 12:17 am

Aquí vamos a publicar la solución oficial.

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 394
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

Re: OFO 2020 Problema 16

Mensaje sin leer por jujumas » Mié 18 Mar, 2020 1:15 am

En épocas de cuarentena no se pueden poner excusas para seguir sin subir la solución oficial.

Para arrancar este post, primero voy a hacer algunos comentarios sobre este problema:
Spoiler: mostrar
Aunque este problema es muy dificil, no es inencarable. Lo más difícil del problema es saber maniobrar con maquinaria bastante pesada, y saber confiarse en que las cosas salen por el camino que más sentido tiene.

Antes de arrancar con la solución, voy a introducir toda la teoría necesaria para poder seguir la solución. Esto implica nombrar algunos teoremas y dar links a las páginas de wikipedia en donde se podrán encontrar los enunciados correspondientes.

Teoría:
Spoiler: mostrar

$\square$ Teorema Chino del Resto:
$\square$ Teorema de la suma de dos cuadrados:
$\square$ Teorema de Dirichlet sobre primos:
$\square$ Ley de Reciprocidad Cuadrática:

Además, se asume que el lector está familiarizado con los conceptos de divisibilidad, aritmética modular, residuos cuadráticos, y con el símbolo de Legendre (ambas propiedades mencionadas en el artículo se usan).
Y ahora, voy a dar algo de motivación detrás de algunas ideas puntuales que eran útiles para la resolución de este problema:
Spoiler: mostrar
Uno de los teoremas claves para poder empezar a entender lo que queríamos averiguar, era el Teorema de la suma de dos cuadrados. En particular, este teorema nos dice que si logramos que algún entero positivo $m$ sea divisible por $p$ primo congruente a $3$ módulo $4$, pero no sea divisible por $p^2$, entonces tenemos garantía de que $m$ es malardo.

Más aún. Combinando esto con el Teorema Chino del Resto podemos elegir $2019$ primos congruentes a $3$ módulo $4$ $p_1$, $p_2$, $\dots$, $p_{2019}$ y sabemos que existen infinitos $n$ tales que $n \equiv p_k -k$ módulo $(p_k^2)$ para todo $1 \leq k \leq 2019$ (ya que $p_1^2$, $p_2^2$, $\dots$, $p_{2019}^2$ son coprimos dos a dos). Luego, tenemos que para todo $1 \leq k \leq 2019$, $n+k$ será divisible por $p_k$ pero no por $p_k^2$, y como los $p_k$ eran congruentes a $3$ módulo $4$, tenemos que $n+1$, $n+2$, $\dots$, $n+2019$ son todos malardos.

Lo que nos falta entonces es buscar una forma de fortalecer esta idea para poder conseguir que $n$ y $n+2020$ sean buenardos. La solución del problema, aunque sea bastante más difícil que esto, a la larga esta motivada por lo mismo.
Ahora si, damos paso a la Solución Oficial:
Spoiler: mostrar
Parte 1: Llevando el problema a algo más manejable.
Spoiler: mostrar
Vamos a aprovecharnos de la siguiente identidad; Para todo entero positivo $a$ tenemos que:

$$a^2 + (a+1009)^2 + 2020 = (a-1)^2 + (a+1010)^2$$

Sea entonces $P$ el polinomio de grado dos dado por $P(x) = x^2 + (x+1009)^2$, sabemos que para todo $n$ entero positivo mayor a $1$, $P(n)$ y $P(n)+2020$ son buenardos. Luego, nos alcanza con encontrar infinitos $n$ tales que para todo entero positivo $i$ entre $1$ y $2019$, $P(n) + i$ es malardo.

Para cada $k$ entero positivo entre $1$ y $2019$, definimos el polinomio $Q_k(x)$ como $P(x) + k$.

Notemos ahora que para todo entero positivo impar $r$, tenemos que:

$$r \mid Q_k(m)$$
$$ \Leftrightarrow r \mid m^2 + (m+1009)^2 + k$$
$$ \Leftrightarrow r \mid 2m^2 + 2(m+1009)^2 + 2k$$
$$ \Leftrightarrow r \mid 2m^2 + 2m^2 + 4m \times 1009 + 2 \times 1009^2 + 2k$$
$$ \Leftrightarrow r \mid (2m)^2 + 2(2m \times 1009) + 1009^2 + 1009^2 + 2k$$
$$ \Leftrightarrow r \mid (2m + 1009)^2 + 1009^2 + 2k$$

Luego, lo que vamos a hacer es demostrar que para cada $k$ entero positivo entre $1$ y $2019$ existen infinitos primos $p$ congruentes a $3$ módulo $4$ tales que para cierto $m$, $p \mid (2m + 1009)^2 + 1009^2 + 2k$ pero $p^2 \nmid (2m + 1009)^2 + 1009^2 + 2k$. Aunque no es trivial que esto equivale a terminar de resolver el problema, poder decir algo de esta índole nos dejaría parados en una situación bastante parecida a la planteada en el apartado "ideas" de la sección "comentarios previos".



Parte 2: Sacando la artillería pesada.
Spoiler: mostrar
Vamos a demostrar un Lema pesado.

Lema: Para todo entero positivo impar $n$ que no es un cuadrado perfecto, existen infinitos primos $p$ congruentes a $3$ módulo $4$ tales que $n$ no es un residuo cuadrático módulo $p$.

Demostración: (alerta, esta es la parte más teórica de la solución).
En notación de Legendre, lo que queremos se traduce a $\left(\frac{n}{p}\right)=-1$.
Sea $x^2$ el mayor cuadrado perfecto que divide a $n$, podemos escribir $n=x^2 \times q_1 \times q_2 \times \dots \times q_c$, donde los $q_i$ son primos impares distintos dos a dos (notemos que como $n$ no era un cuadrado perfecto, $c$ es al menos $1$). Como Legendre distribuye, queremos:

$$ \left(\frac{n}{p}\right)= \left(\frac{x^2}{p}\right) \left(\frac{q_1}{p}\right) \left(\frac{q_2}{p}\right) \dots \left(\frac{q_c}{p}\right) = 1$$

Es claro que $\left(\frac{x^2}{p}\right) = 1$ para todos $x$, y $p$. Veamos que existen infinitos $p$ tales que $\left(\frac{q_1}{p}\right)=-1$ y $\left(\frac{q_i}{p}\right) = 1$ para $i$ entre $2$ y $c$ (si $c=1$ solo nos basta la primera condición). Claramente, tener esto equivaldría a demostrar el Lema.

Como los $q_i$ son primos impares y $p$ era congruente a $3$ módulo $4$ y en particular impar, por la Ley de Reciprocidad Cuadrática, sabemos que $\left(\frac{q_i}{p}\right) \left(\frac{p}{q_i}\right) = (-1)^{\frac{q_i - 1}{2} \frac{p - 1}{2}}$. Además, sabemos que $\frac{p - 1}{2}$ es un entero impar y tenemos $\left(\frac{q_i}{p}\right) \left(\frac{p}{q_i}\right) = (-1)^{\frac{q_i + 1}{2}}$. Entonces, separamos en casos:

Si $i=1$ y $q_1 \equiv 1 (4)$, tenemos $\left(\frac{q_1}{p}\right) \left(\frac{p}{q_1}\right) = -1$, por lo que queremos $\left(\frac{p}{q_1}\right) = 1$. Luego, nos basta con tomar $p \equiv 1 (q_1)$ para lograr lo que queremos.

Si $i=1$ y $q_1 \equiv 3 (4)$, tenemos $\left(\frac{q_1}{p}\right) \left(\frac{p}{q_1}\right) = 1$, por lo que queremos $\left(\frac{p}{q_1}\right) = -1$. Luego, nos basta con tomar $p \equiv t_1 (q_1)$ donde $t_1$ es un no-residuo cuadrático módulo $q_1$, para lograr lo que queremos.

Si $i \geq 2$ y $q_i \equiv 1 (4)$, tenemos $\left(\frac{q_i}{p}\right) \left(\frac{p}{q_i}\right) = -1$, por lo que queremos $\left(\frac{p}{q_i}\right) = -1$. Luego, nos basta con tomar $p \equiv t_i (q_i)$ donde $t_i$ es un no-residuo cuadrático módulo $q_i$, para lograr lo que queremos.

Si $i \geq 2$ y $q_i \equiv 3 (4)$, tenemos $\left(\frac{q_i}{p}\right) \left(\frac{p}{q_i}\right) = 1$, por lo que queremos $\left(\frac{p}{q_i}\right) = 1$. Luego, nos basta con tomar $p \equiv 1 (q_i)$ para lograr lo que queremos.

Luego, caigamos en los casos que caigamos, nos alcanza con que $p$ tenga cierta congruencia módulo $4$, cierta congruencia módulo $q_1$, cierta congruencia módulo $q_2$, y siguiendo hasta pedir que tenga cierta congruencia módulo $q_c$. Como los $q_i$ eran impares y distintos, los números $4$, $q_1$, $q_2$, $\dots$, $q_c$ son coprimos dos a dos y por el Teorema Chino del Resto, existe una congruencia $h$ módulo $M = 4q_1q_2\dots q_c$ que es equivalente a pedir todas estas congruencias en simultáneo.

Como ninguna de las congruencias módulo $4$ o los $q_i$ era cero, $h$ es coprimo con $M$. Luego, queremos ver que existan infinitos primos congruentes a $h$ módulo $M$, pero el Teorema de Dirichlet nos dice exactamente esto. Luego, la demostración de nuestro lema está completa.



Parte 3: Resolviendo lo último que planteamos en la parte 1.
Spoiler: mostrar
Notemos que para todo $k$ entero positivo entre $1$ y $2019$, $1009^2 + 2k$ es un entero positivo impar que no es un cuadrado perfecto (ya que $1009^2 + 2k$ está entre $1009^2$ y $1011^2$ (para $k$ entre $1$ y $2019$) y $1010^2$ es par). Luego, podemos aplicar el Lema que acabamos de demostrar para llegar a que, para cada $k$, existen infinitos primos $p$ congruentes a $3$ módulo $4$ tales que $1009^2 + 2k$ no es un residuo cuadrático módulo $p$.

En notación de Legendre, esto quiere decir que para infinitos $p$ congruentes a $3$ módulo $4$, $\left(\frac{1009^2+2k}{p}\right)=-1$. Como el símbolo de Legendre distribuye, tenemos que $\left(\frac{-1009^2-2k}{p}\right) = \left(\frac{1009^2+2k}{p}\right) \left(\frac{-1}{p}\right)$. Como $p$ es congruente a $3$ módulo $4$, es conocido que $\left(\frac{-1}{p}\right) = -1$, de donde tenemos que $\left(\frac{-1009^2-2k}{p}\right) = 1$.

Luego, para cada $k$ tenemos que existen infinitos $p$ congruentes a $3$ módulo $4$ tales que existe un entero positivo $y$ que cumple $y^2 \equiv -1009^2-2k (p)$, de donde $p \mid y^2 + 1009^2 + 2k$. Esto implica que, fijado $k$, existen infinitos $p$ congruentes a $3$ módulo $4$ mayores a $1011^2$ tales que para cierto entero positivo $y$, $p \mid y^2 + 1009^2 + 2k$.

Supongamos entonces $p \mid y^2 + 1009^2 + 2k$. Claramente, $p \mid (y+p)^2 + 1009^2 + 2k$. Notemos que o bien $p^2 \nmid y^2 + 1009^2 + 2k$ o bien $p^2 \nmid (y+p)^2 + 1009^2 + 2k$, ya que de lo contrario, $p^2 \mid y^2 + 2yp + p^2 + 1009^2 + 2k - (y^2 + 1009^2 + 2k)$ y $p^2 \mid 2yp + p^2$, de donde $p^2 \mid 2yp$ y $p \mid 2y$. Como $p$ era mayor a $1011^2$, esto implica que $p \mid y$, pero sabíamos de antes que $p \mid y^2 + 1009^2 + 2k$. Luego, como $p \mid y^2$, $p \mid 1009^2 + 2k$, pero $1009^2 + 2k$ es un entero positivo menor a $1011^2$, que es menor a $p$. Absurdo.

Debido a esto, para infinitos primos $p$ congruentes a $3$ módulo $4$ existe un $y_0$ tal que $p \mid y_0^2 + 1009^2 + 2k$ pero $p^2 \nmid y_0^2 + 1009^2 + 2k$. Notemos además que cualquier $y_t = y_0 + tp^2$, con $t$ entero positivo, satisface $p \mid y_t^2 + 1009^2 + 2k$ y $p^2 \nmid y_t^2 + 1009^2 + 2k$, ya que la expresión $y^2 + 1009^2 + 2k$ es un polinomio y por lo tanto periódica módulo $p^2$.

Como $2m+1009$ puede ser cualquier entero positivo impar mayor a $1009$ al variar $m$, y hay infinitos $y_t$ de cada paridad (ya que $p^2$ es impar), en particular existe algún $j$ tal que $y_j$ es un entero impar mayor a $1009$, y en particular, existe un $m_0$ tal que $2m+1009 = y_j$. Luego, esto quiere decir que, fijado $k$, existen infinitos primos $p$ congruentes a $3$ módulo $4$ tales que para cierto $m_0$ entero positivo, $p \mid (2m_0 + 1009)^2 + 1009^2 + 2k$ pero $p^2 \nmid (2m_0 + 1009)^2 + 1009^2 + 2k$.



Parte 4: El final.
Spoiler: mostrar
En la parte $1$, planteamos que si $r$ es un entero positivo impar, $r \mid Q_k(m) \Leftrightarrow r \mid (2m + 1009)^2 + 1009^2 + 2k$. Luego, tenemos que para cada $k$, existen infinitos primos $p$ congruentes a $3$ módulo $4$ tales que para cierto $m_0$ entero positivo, $p \mid Q_k(m_0)$ pero $p^2 \nmid Q_k(m_0)$. Debido a esto, podemos elegir una sucesión de primos distintos $p_1$, $p_2$, $\dots$, $p_{2019}$ congruentes a $3$ módulo $4$ y una sucesión de enteros positivos $b_1$, $b_2$, $\dots$, $b_{2019}$ tal que para cada $k$ entre $1$ y $2019$, $p_k \mid Q_k(b_k)$ pero $p_k^2 \nmid Q_k(b_k)$.

Y de acá nos falta sorprendentemente poco para terminar. Debido al Teorema de la suma de dos cuadrados, todo entero positivo $u$ tal que $p \mid u$ pero $p \nmid u$, con $p$ primo congruente a $3$ módulo $4$, es malardo. Por otro lado, lo que queríamos era que para infinitos enteros positivos $n$, $Q_k(n)$ sea malardo para todo $k$ entre $1$ y $2019$. Pero notemos que si $n \equiv b_k (p_k^2)$, como los polinomios son periódicos módulo $p_k^2$ tenemos que $p_k \mid Q_k(n)$ pero $p_k^2 \nmid Q_k(n)$, con $p_k$ congruente a $3$ módulo $4$. Luego, esto implicaría que $Q_k(n)$ es malardo.

Debido a esto, para terminar la solución nos basta demostrar que existen infinitos enteros positivos $n$ tales que $n \equiv b_k (p_k^2)$ para cada $k$ entre $1$ y $2019$, y como $p_1$, $p_2$, $\dots$, $p_{2019}^2$ son coprimos dos a dos, por el Teorema Chino del Resto existe un $l$ tal que si $N = p_1^2 \times p_2^2 \times \dots \times p_{2019}^2$ y $n \equiv l (N)$, entonces tenemos todas las congruencias necesarias y $Q_k(n)$ es malardo para todo $k$ entre $1$ y $2019$.

Luego, para todo $z$ entero positivo, cualquier $n$ de la forma $n = P(Nz + l)$ cumple lo que pide el problema, y es claro que estos son infinitos.
4  

Responder