a^((p-1)/2) ≡ (a/p) (mod p).
El Criterio de Euler es un resultado fundamental en la teoría elemental de números que te da un método directo para determinar si un entero 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 esto elevando al cuadrado cada entero desde $1$ hasta $(p-1)/2$ es muy ineficiente cuando $p$ es grande. El Criterio de Euler cierra la brecha entre la propiedad abstracta de ser un "cuadrado" y las propiedades aritméticas del campo $\mathbb{Z}_p$, relacionando específicamente el símbolo de Legendre con la exponenciación modular.
El criterio es esencial tanto para cálculos como para demostraciones teóricas. Te sirve como herramienta principal para calcular símbolos de Legendre antes de introducir la Ley de Reciprocidad Cuadrática; de hecho, se usa seguido para demostrar la Reciprocidad Cuadrática. Además, te permite determinar si una congruencia cuadrática tiene solución sin tener que encontrar las raíces realmente.
Intuitivamente, el Criterio de Euler es un refinamiento del Pequeño Teorema de Fermat. El Pequeño Teorema de Fermat dice que para cualquier entero $a$ que no sea divisible entre $p$, $a^{p-1} \equiv 1 \pmod p$. Puedes factorizar la expresión $a^{p-1} - 1$ como $(a^{(p-1)/