Fórmulas para (-1/p) y (2/p).
La Ley de Reciprocidad Cuadrática te da una relación muy potente entre los símbolos de Legendre $(p/q)$ y $(q/p)$ para primos impares distintos $p$ y $q$. Pero, para calcular el símbolo de Legendre $(a/p)$ de cualquier entero $a$, tienes que saber qué hacer con los factores primos de $a$. Aunque la ley general se encarga de los factores primos impares, no aplica para el factor $-1$ ni para el primo $2$. El Primer y Segundo Suplementos de la Ley de Reciprocidad Cuadrática llenan ese hueco, dándote fórmulas directas para saber si $-1$ y $2$ son residuos cuadráticos módulo un primo impar $p$.
Estos suplementos son básicos para el algoritmo de cálculo de los símbolos de Legendre. Cuando calculas $(a/p)$, normalmente usas la propiedad multiplicativa $(ab/p) = (a/p)(b/p)$ para factorizar $a$ en $-1$, potencias de $2$ y primos impares. Luego aplicas los suplementos a las partes con $-1$ y $2$, mientras que usas la ley de reciprocidad general para los primos impares. Sin estos suplementos, el proceso recursivo de "voltear" el símbolo de Legendre se detendría al llegar a números pares o negativos.
De forma intuitiva, el Primer Suplemento determina si la congruencia $x^2 \equiv -1 \pmod p$ tiene solución. Esto tiene mucho que ver con la estructura cíclica del grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^\times$; específicamente, $-1$ es un residuo cuadrático si y solo si hay un elemento de orden 4 en el grupo, lo que requiere que el orden del grupo $p-1$ sea divisible entre 4. El Segundo Suplemento, que trata sobre $x^2 \equiv 2 \pmod p$, es un poco más sutil y depende de cómo se distribuyen los residuos en el intervalo $(0, p/2)$, algo que puedes visualizar usando el Lema de Gauss.
Sea $p$ un primo impar. Escribimos el símbolo de Legendre como $(\cdot/p)$.
El Primer Suplemento (para $-1$): $$ \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 & \text{si } p \equiv 1 \pmod 4 \ -1 & \text{si } p \equiv 3 \pmod 4 \end{cases} $$
El Segundo Suplemento (para $2$): $$ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 & \text{si } p \equiv 1, 7 \pmod 8 \ -1 & \text{si } p \equiv 3, 5 \pmod 8 \end{cases} $$
Uso combinado: Para un entero $a = (-1)^k 2^m \cdot q_1 q_2 \dots$ donde los $q_i$ son primos impares: $$ \left(\frac{a}{p}\right) = \left(\frac{-1}{p}\right)^k \left(\frac{2}{p}\right)^m \left(\frac{q_1}{p}\right) \dots $$
Usa el Criterio de Euler, que dice que para un primo impar $p$ y un entero $a$ que no sea divisible entre $p$: $$ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p $$ Si sustituyes $a = -1$: $$ \left(\frac{-1}{p}\right) \equiv (-1)^{\frac{p-1}{2}} \pmod p $$ Como ambos lados de la congruencia son $1$ o $-1$, y $p > 2$, la congruencia implica que son iguales: $$ \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} $$ Si $p \equiv 1 \pmod 4$, entonces $\frac{p-1}{2}$ es par, así que $(-1)^{\text{par}} = 1$. Si $p \equiv 3 \pmod 4$, entonces $\frac{p-1}{2}$ es impar, así que $(-1)^{\text{impar}} = -1$.
Usa el Lema de Gauss. Toma $S = {1, 2, \dots, \frac{p-1}{2}}$. El Lema de Gauss dice que $\left(\frac{a}{p}\right) = (-1)^\mu$, donde $\mu$ es la cantidad de elementos en el conjunto ${a, 2a, \dots, \frac{p-1}{2}a}$ cuyos residuos positivos mínimos módulo $p$ son mayores que $p/2$.
Toma $a = 2$. Mira el conjunto de los múltiplos: $$ M = \left{ 2(1), 2(2), \dots, 2\left(\frac{p-1}{2}\right) \right} = { 2, 4, \dots, p-1 } $$ Todos los elementos en $M$ son distintos y cumplen que $0 < 2k < p$. Tienes que contar cuántos de estos son mayores que $p/2$. Sea $k$ un entero en $S$. La condición $2k > p/2$ es equivalente a $k > p/4$. Por lo tanto, $\mu$ es la cantidad de enteros $k$ tales que $\frac{p}{4} < k \le \frac{p-1}{2}$. El número de esos enteros es: $$ \mu = \frac{p-1}{2} - \left\lfloor \frac{p}{4} \right\rfloor $$ Analiza $\mu$ módulo 2 para los cuatro casos posibles de $p \pmod 8$:
Caso $p = 8k + 1$: $$ \mu = \frac{8k}{2} - \lfloor 2k + 1/4 \rfloor = 4k - 2k = 2k \equiv 0 \pmod 2 $$ Así que $\left(\frac{2}{p}\right) = (-1)^0 = 1$.
Caso $p = 8k + 3$: $$ \mu = \frac{8k+2}{2} - \lfloor 2k + 3/4 \rfloor = (4k+1) - 2k = 2k+1 \equiv 1 \pmod 2 $$ Así que $\left(\frac{2}{p}\right) = (-1)^1 = -1$.
Caso $p = 8k + 5$: $$ \mu = \frac{8k+4}{2} - \lfloor 2k + 5/4 \rfloor = (4k+2) - (2k+1) = 2k+1 \equiv 1 \pmod 2 $$ Así que $\left(\frac{2}{p}\right) = (-1)^1 = -1$.
Caso $p = 8k + 7$: $$ \mu = \frac{8k+6}{2} - \lfloor 2k + 7/4 \rfloor = (4k+3) - (2k+1) = 2k+2 \equiv 0 \pmod 2 $$ Así que $\left(\frac{2}{p}\right) = (-1)^0 = 1$.
Resumiendo estos resultados, $\left(\frac{2}{p}\right) = 1$ si $p \equiv 1, 7 \pmod 8$ y $-1$ si $p \equiv 3, 5 \pmod 8$. Esta paridad coincide con la fórmula $\frac{p^2-1}{8} \pmod 2$. $\square$