Para saber si a es un residuo cuadrático mód p.
La Reciprocidad Cuadrática es uno de los teoremas más famosos de la teoría de números; sirve como una herramienta de cálculo muy poderosa y te da una visión profunda sobre la naturaleza de los números primos. En esencia, la Ley de Reciprocidad Cuadrática establece una relación entre si la congruencia $x^2 \equiv p \pmod{q}$ tiene solución y si la congruencia $x^2 \equiv q \pmod{p}$ también la tiene, donde $p$ y $q$ son primos impares distintos. Aunque el Criterio de Euler teóricamente te permite determinar si un número es un residuo cuadrático, requiere elevar números grandes a potencias. La Reciprocidad Cuadrática, combinada con las propiedades del símbolo de Legendre, convierte este proceso en un algoritmo eficiente parecido al algoritmo de Euclides para encontrar el máximo común divisor.
La aplicación principal de este teorema en matemáticas de olimpiada es evaluar el símbolo de Legendre $\left(\frac{a}{p}\right)$. Si usas la propiedad multiplicativa del símbolo, puedes factorizar $a$ en primos y evaluar el símbolo para cada factor primo. La Reciprocidad Cuadrática te permite "voltear" el símbolo $\left(\frac{q}{p}\right)$ a $\pm\left(\frac{p}{q}\right)$, y así reduces el módulo. Al aplicar la ley repetidamente y reducir el número módulo el nuevo denominador, puedes determinar si $a$ es un