Aplicaciones olímpicas

Tres patrones de aplicación

Los residuos cuadráticos aparecen en olimpiadas principalmente en tres contextos: (1) demostrar que una ecuación diofántica no tiene solución tomando un módulo conveniente y mostrando que el segundo miembro no es cuadrado módulo ese módulo; (2) determinar todos los primos $p$ para los cuales cierta congruencia tiene solución; (3) problemas de existencia o imposibilidad ligados a la representación de números como sumas o diferencias de cuadrados.

En todos estos contextos, el flujo de trabajo es el mismo: pasar del enunciado entero al enunciado modular, identificar el primo de control, calcular el símbolo de Legendre con las herramientas del capítulo, y concluir.

Patrón 1: imposibilidad diofántica por residuo cuadrático

Problema. Demuestra que la ecuación $x^2 = 3y^2 - 1$ no tiene soluciones enteras.

Solución. Tomamos la ecuación módulo 3: $x^2 \equiv -1 \pmod{3}$, es decir $x^2 \equiv 2 \pmod{3}$. Los cuadrados módulo 3 son $0^2 \equiv 0$ y $1^2 \equiv 2^2 \equiv 1$. Ningún cuadrado es $\equiv 2 \pmod{3}$. Por tanto $\left(\frac{2}{3}\right) = -1$, y la ecuación no tiene soluciones enteras.

La clave es elegir el módulo correcto. Un módulo $m$ es útil si el valor del segundo miembro (aquí $-1$) no es un cuadrado módulo $m$. Con $m = 3$ y $-1 \equiv 2 \pmod{3}$, la imposibilidad es inmediata.

Generalización. Para probar que $x^2 = f(y)$ no tiene soluciones: busca un primo $p$ tal que $f(y) \bmod p$ no tome ningún valor que sea residuo cuadrático módulo $p$ para los valores relevantes de $y \bmod p$.

Patrón 2: determinar primos con propiedades de cuadraticidad

Problema (Cono Sur, estilo). Encuentra todos los primos $p$ para los cuales $p \mid x^2 + x + 1$ para algún entero $x$.

Solución. Completamos el cuadrado: $x^2 + x + 1 = \left(x + \frac{1}{2}\right)^2 + \frac{3}{4}$. Multiplicando por 4: $(2x+1)^2 \equiv -3 \pmod{p}$. La ecuación tiene solución si y solo si $\left(\frac{-3}{p}\right) \ge 0$, es decir $\left(\frac{-3}{p}\right) = 1$ o $p \mid 3$.

Calculamos $\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$. Por reciprocidad y las fórmulas del capítulo, $\left(\frac{-3}{p}\right) = 1$ si y solo si $p \equiv 1 \pmod{3}$.

Verificamos: $p = 7 \equiv 1 \pmod 3$: $x = 2$ da $4 + 2 + 1 = 7$. $p = 13 \equiv 1 \pmod 3$: $x = 3$ da $9 + 3 + 1 = 13$. $p = 3$: $x = 1$ da $3$. La respuesta es $p = 3$ o $p \equiv 1 \pmod{3}$.

Patrón 3: reciprocidad en problemas de forma cuadrática

Problema (Iberoamericana, adaptado). Sea $p$ un primo impar. Demuestra que $p$ divide a algún número de la forma $n^2 + 1$ si y solo si $p \equiv 1 \pmod{4}$.

Solución. $p \mid n^2 + 1$ equivale a $n^2 \equiv -1 \pmod{p}$, es decir a que $-1$ sea residuo cuadrático módulo $p$. Por la fórmula $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$, esto ocurre si y solo si $(p-1)/2$ es par, es decir $4 \mid p-1$, o sea $p \equiv 1 \pmod{4}$.

Ejemplos: $p = 5 \equiv 1 \pmod 4$: $2^2 + 1 = 5$. $p = 13 \equiv 1 \pmod 4$: $5^2 + 1 = 26 = 2 \cdot 13$. $p = 3 \equiv 3 \pmod 4$: módulo 3, $0^2 = 0$, $1^2 = 1$, $2^2 = 1$. Ninguno es $\equiv -1 \equiv 2 \pmod 3$.

Problema de alta dificultad: primos en $x^2 + x + 3$

Problema. Demuestra que hay infinitos primos $p$ tales que $p \equiv 1 \pmod{3}$.

Solución usando residuos cuadráticos. Supongamos que los únicos primos con $p \equiv 1 \pmod{3}$ son $p_1, p_2, \ldots, p_k$. Considera $N = (2 p_1 p_2 \cdots p_k)^2 + 3$. Este número es $\equiv 3 \pmod{4}$ y $> 1$, así que tiene algún factor primo $q$. Se cumple $q \mid N$, luego $(2p_1 \cdots p_k)^2 \equiv -3 \pmod{q}$, así $\left(\frac{-3}{q}\right) = 1$ (o $q = 3$, pero $3 \nmid N$ pues $N \equiv 1 \pmod 3$). Por el cálculo de $\left(\frac{-3}{q}\right)$, esto exige $q \equiv 1 \pmod 3$. Pero $q \nmid 2p_1 \cdots p_k$ (porque $q \mid N$ y $\gcd(N, 2p_1\cdots p_k) = 1$), así $q$ no está en la lista. Contradicción.

Esta es la demostración estándar de infinitud de primos en una progresión aritmética específica, usando residuos cuadráticos en lugar del análisis del Teorema de Dirichlet.

El método de descarte: suma de cuadrados módulo 4 y módulo 8

Una técnica complementaria a los residuos cuadráticos módulo un primo es trabajar módulo potencias de 2.

Lema. Todo cuadrado es $\equiv 0$ o $\equiv 1 \pmod{4}$. En consecuencia, la suma de dos cuadrados es $\equiv 0, 1$ o $\equiv 2 \pmod{4}$, pero **nunca $\equiv 3 \pmod{4}$**. Por tanto, ningún número $\equiv 3 \pmod{4}$ es suma de dos cuadrados.

Módulo 8: los cuadrados son $\equiv 0, 1, 4 \pmod{8}$. La suma de tres cuadrados puede ser $\equiv 0,1,2,3,4,5,6 \pmod 8$, pero **nunca $\equiv 7 \pmod 8$**. Así ningún número $\equiv 7 \pmod 8$ es suma de tres cuadrados (teorema de Legendre).

Estos criterios módulo $4$ y $8$ suelen ser el primer paso antes de aplicar reciprocidad, y permiten descartar candidatos rápidamente en problemas de existencia.

Síntesis: protocolo olímpico para problemas de RC

Al enfrentar un problema que involucra cuadrados y primos, el protocolo es:

Paso 1 — Reducción modular. Reescribe la condición como $x^2 \equiv c \pmod{m}$ para algún módulo $m$ conveniente.

Paso 2 — Identificar el primo de control. Busca un primo $p$ (divisor de $m$ o primo auxiliar) para el cual $\left(\frac{c}{p}\right) = -1$. Si lo encuentras, la ecuación no tiene solución y el resultado de imposibilidad está demostrado.

Paso 3 — Calcular el símbolo. Usa multiplicatividad, $\left(\frac{-1}{p}\right)$, $\left(\frac{2}{p}\right)$ y la ley de reciprocidad para reducir el cálculo a símbolos sobre primos pequeños.

Paso 4 — Concluir. Si el símbolo es $-1$, no hay solución. Si es $1$, hay solución módulo $p$ (pero puede no haberla en los enteros por otras razones). Si el problema pide hallar todos los primos con cierta propiedad, traduce la condición al símbolo y aplica la caracterización modular del resultado.