Para ver si a es un residuo cuadrático mod p.
El Criterio de Euler es un teorema fundamental en teoría de números que te da un método de cálculo directo 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 esto por fuerza bruta no es nada eficiente. El Criterio de Euler conecta el carácter cuadrático de un número con la exponenciación modular, y dice que el símbolo de Legendre $\left(\frac{a}{p}\right)$ es congruente a $a^{\frac{p-1}{2}} \pmod p$.
Esta herramienta es indispensable en las matemáticas de competencia por varias razones. Primero, sirve como el paso fundamental para demostrar la Ley de Reciprocidad Cuadrática. Segundo, te permite determinar de volada el carácter cuadrático de ciertos enteros, sobre todo del $-1$, lo que te deja clasificar a los primos dependiendo de si $-1$ es un cuadrado módulo $p$. Finalmente, transforma preguntas sobre la existencia de raíces en preguntas sobre divisibilidad y aritmética modular, permitiéndote aplicar las propiedades del grupo multiplicativo de los enteros módulo $p$.
Intuitivamente, el Criterio de Euler se basa en la estructura del grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^\times$, que es un grupo cíclico de orden $p-1$. Por el Pequeño Teorema de Fermat, $