Usando el pequeño teorema de Fermat.
El Criterio de Euler es un resultado fundamental en la teoría elemental de números que te da un método para calcular si un entero es un residuo cuadrático módulo un primo impar. Aunque la definición de residuo cuadrático te pregunta si la congruencia $x^2 \equiv a \pmod p$ tiene solución, checar cada valor posible de $x$ es muy tardado. El Criterio de Euler conecta la idea abstracta de "ser un cuadrado" con la exponenciación modular, y te dice que $a$ es un residuo cuadrático si y solo si $a^{\frac{p-1}{2}} \equiv 1 \pmod p$.
Este teorema es clave para estudiar la reciprocidad cuadrática. Te da la herramienta estándar para calcular el símbolo de Legendre $\left(\frac{a}{p}\right)$ sin que tengas que andar probando al azar. Además, generaliza el Pequeño Teorema de Fermat. Como el Pequeño Teorema de Fermat te dice que $a^{p-1} \equiv 1 \pmod p$, sabes que la raíz cuadrada de $a^{p-1}$ (que es $a^{\frac{p-1}{2}}$) tiene que ser congruente a $1$ o a $-1$. El Criterio de Euler separa de forma elegante los enteros módulo $p$ en dos conjuntos: los residuos cuadráticos se van al $1$, y los no residuos se van al $-1$.