Criterio de Euler

Teoría

El Criterio de Euler es un resultado fundamental en la teoría de números elemental que te da un método computacional para determinar si un entero $a$ es un residuo cuadrático módulo un primo impar $p$. Aunque la definición de residuo cuadrático pregunta si la congruencia $x^2 \equiv a \pmod p$ tiene solución, checar cada valor posible de $x$ es muy ineficiente. El Criterio de Euler cierra la brecha entre la existencia de una raíz cuadrada y la exponenciación modular, transformando una pregunta de existencia en un cálculo directo.

Este teorema es el motor computacional detrás del Símbolo de Legendre y sirve como un lema crítico en la demostración de la Ley de Reciprocidad Cuadrática. En las olimpiadas de matemáticas, lo vas a usar seguido para determinar si las congruencias cuadráticas tienen solución, especialmente para valores específicos como $a = -1$ o $a = 2$. También ayuda a clasificar los divisores primos de expresiones de la forma $n^2 + a$.

La intuición detrás del criterio se basa en el Pequeño Teorema de Fermat, que dice que para cualquier $a$ que no sea divisible por $p$, $a^{p-1} \equiv 1 \pmod p$. Si factorizas esta expresión, obtienes $(a^{\frac{p-1}{2}} - 1)(a^{\frac{p-1}{2}} + 1) \equiv 0 \pmod