Usando el criterio de Euler.
El símbolo de Legendre $\left(\frac{a}{p}\right)$ es una herramienta fundamental en teoría de números que sirve para determinar si un entero $a$ es un residuo cuadrático módulo un primo impar $p$. Aunque la definición solo pregunta si la congruencia $x^2 \equiv a \pmod{p}$ tiene solución, checar cada valor posible de $x$ es muy ineficiente. Para calcular el símbolo de forma efectiva y sacar sus propiedades, puedes usar el Criterio de Euler. Este criterio da una fórmula explícita para el valor del símbolo de Legendre usando exponenciación modular, conectando la existencia de una raíz cuadrada con las propiedades aritméticas del campo $\mathbb{Z}_p$.
El Criterio de Euler es clave porque transforma la propiedad abstracta de "ser un cuadrado" en un cálculo concreto con potencias. Sirve como la base teórica para demostrar la Ley de Reciprocidad Cuadrática y la propiedad multiplicativa del símbolo de Legendre. En problemas de olimpiada, puedes usar esta técnica seguido no solo para cálculos numéricos, sino para analizar congruencias polinomiales, ver si las ecuaciones tienen solución y establecer condiciones bajo las cuales ciertos números (como el $-1$ o las raíces primitivas) son residuos.
Intuitivamente, el Criterio de Euler se basa en la estructura del grupo multiplicativo de los enteros módulo $p$, que lo escribimos como $\mathbb{Z}_p^*$. Este grupo es cíclico de orden