# Quadratic Reciprocity Law

## The Legendre Symbol
The *Legendre symbol* is a function used in number theory to characterize whether an integer is a quadratic residue modulo an odd prime $p$.

:::info
**Definition** *The Legendre Symbol*
Let $p$ be an odd prime number and let $a$ be an integer. The Legendre symbol $\left(\frac{a}{p}\right)$ is defined as: $$\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if } p \mid a \\ 1 & \text{if } p \nmid a \text{ and } x^2 \equiv a \pmod{p} \text{ is solvable (a quadratic residue)} \\ -1 & \text{if } x^2 \equiv a \pmod{p} \text{ is not solvable (a quadratic non-residue)} \end{cases}$$

* If $\left(\frac{a}{p}\right) = 1$, we say $a$ is a *quadratic residue* modulo $p$.
* If $\left(\frac{a}{p}\right) = -1$, we say $a$ is a *quadratic non-residue* modulo $p$.
:::

The number of incongruent solutions to $x^2 \equiv a \pmod{p}$ is precisely $1 + \left(\frac{a}{p}\right)$ (this gives 1 if $p \mid a$, 2 if $a$ is a residue, and 0 if $a$ is a non-residue).

:::warning
**Examples (Modulo $p=7$)**
| Integer a | Congruence $x^2 \equiv a \pmod{7}$ | Solution(s) | $\left(\frac{7}{a}\right)$ | Classification |
| :---: | :--- | :---: | :---: | :--- |
| 14 | $x^2 \equiv 14 \equiv 0 \pmod{7}$ | $x \equiv 0$ | 0 | Quadratic Residue |
| 4 | $x^2 \equiv 4 \pmod{7}$ | $x \equiv \pm 2$ | 1 | Quadratic Residue |
| 2 | $x^2 \equiv 2 \pmod{7}$ | $x \equiv \pm 3$ | 1 | Quadratic Residue |
| 3 | $x^2 \equiv 3 \pmod{7}$ | Unsolvable | -1 | Non-Residue |
:::

## Properties of the Legendre Symbol
These properties are essential for efficiently computing the Legendre symbol.

:::danger
**Proposition (Euler's Criterion)**
For any odd prime $p$ and any integer $a$, the Legendre symbol is congruent to $a$'s power raised to $(p-1)/2$ modulo $p$: $$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$
:::

:::danger
**Proposition (Basic Properties)**
Given an odd prime number $p$, the following properties hold for integers $a$ and $b$:
* *(Periodicity)* If $a \equiv b \pmod{p}$, then $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$.
* *(Squares)* $\left(\frac{a^2}{p}\right) = 1$ (if $p \nmid a$). In particular, $\left(\frac{1}{p}\right) = 1$.
* *(Multiplicativity)* The Legendre symbol is completely multiplicative with respect to the numerator:$$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right)$$
* *(Square Removal)* If $p \nmid a$, then $\left(\frac{a^2 b}{p}\right) = \left(\frac{b}{p}\right)$.
:::

:::danger
**Proposition (Special Values)**
1. *(Negative One)* The value of $\left(\frac{-1}{p}\right)$ is determined by $p \pmod{4}$:$$\left(\frac{-1}{p}\right) = \begin{cases} 1 & \text{if } p \equiv 1 \pmod{4} \\ -1 & \text{if } p \equiv 3 \pmod{4} \end{cases}$$
2. *(The Value of $\left(\frac{2}{p}\right)$)* The value of the Legendre symbol $\left(\frac{2}{p}\right)$ is determined by $p \pmod{8}$:$$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 & \text{if } p \equiv 1, 7 \pmod{8} \\ -1 & \text{if } p \equiv 3, 5 \pmod{8} \end{cases}$$
:::

:::danger
**Proposition (Summation Property)**
For any odd prime $p$, there are an equal number of quadratic residues and non-residues in the reduced residue system:$$\sum_{i=1}^{p-1} \left(\frac{i}{p}\right) = 0$$This implies there are exactly $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic non-residues in the set $\{1, 2, \dots, p-1\}$.
:::

## The Law of Quadratic Reciprocity
The *Quadratic Reciprocity Law* is a cornerstone of number theory, providing a relationship between $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$.

:::danger
**Theorem (Gauss Quadratic Reciprocity Law)**
Let $p$ and $q$ be distinct odd prime numbers. The law is expressed as:$$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}$$
:::

This product is $-1$ (meaning $\left(\frac{p}{q}\right) = - \left(\frac{q}{p}\right)$) if and only if both $p$ and $q$ are congruent to $3 \pmod{4}$. Otherwise, the product is $1$ (meaning $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$).

### Computational Examples
The law is used to repeatedly simplify the symbol until the numerator is small and the value can be determined directly.

:::warning
**Example** Determine if $x^2 \equiv 19 \pmod{83}$ is solvable.

* *Goal:* Compute $\left(\frac{19}{83}\right)$.
* *Reciprocity:* Since $19 \equiv 3 \pmod{4}$ and $83 \equiv 3 \pmod{4}$, the sign is $-1$.$$\left(\frac{19}{83}\right) = -1 \cdot \left(\frac{83}{19}\right)$$
* *Reduction:* $83 \equiv 7 \pmod{19}$.$$\left(\frac{19}{83}\right) = -\left(\frac{7}{19}\right)$$
* *Reciprocity Again:* Since $7 \equiv 3 \pmod{4}$ and $19 \equiv 3 \pmod{4}$, the sign is $-1$.$$\left(\frac{19}{83}\right) = - \left( - \left(\frac{19}{7}\right) \right) = \left(\frac{19}{7}\right)$$
* *Final Reduction:* $19 \equiv 5 \pmod{7}$.$$\left(\frac{19}{7}\right) = \left(\frac{5}{7}\right)$$
* *Final Evaluation:* $5$ is a non-residue modulo 7 (by checking $1^2 \equiv 1, 2^2 \equiv 4, 3^2 \equiv 2$).$$\left(\frac{5}{7}\right) = -1$$
* *Conclusion:* Since $\left(\frac{19}{83}\right) = -1$, the congruence $x^2 \equiv 19 \pmod{83}$ is *not solvable*.
:::

:::warning
**Example** Determine if $x^2 \equiv 29 \pmod{101}$ is solvable.

* *Goal:* Compute $\left(\frac{29}{101}\right)$.
* *Reciprocity:* Since $29 \equiv 1 \pmod{4}$ and $101 \equiv 1 \pmod{4}$, the sign is $+1$.$$\left(\frac{29}{101}\right) = 1 \cdot \left(\frac{101}{29}\right)$$
* *Reduction:* $101 \equiv 14 \pmod{29}$.$$\left(\frac{101}{29}\right) = \left(\frac{14}{29}\right)$$
* *Factorization & Properties:* Factor $14 = 2 \cdot 7$.$$\left(\frac{14}{29}\right) = \left(\frac{2}{29}\right) \cdot \left(\frac{7}{29}\right)$$
* *Special Value $\left(\frac{2}{p}\right)$:* Since $29 \equiv 5 \pmod{8}$, we have $\left(\frac{2}{29}\right) = -1$.$$(-1) \cdot \left(\frac{7}{29}\right)$$
* *Reciprocity on $\left(\frac{7}{29}\right)$:* Since $29 \equiv 1 \pmod{4}$, the sign is $+1$.$$-\left(\frac{7}{29}\right) = -\left( 1 \cdot \left(\frac{29}{7}\right) \right) = -\left(\frac{29}{7}\right)$$
* *Final Reduction & Evaluation:* $29 \equiv 1 \pmod{7}$.$$-\left(\frac{29}{7}\right) = -\left(\frac{1}{7}\right) = -(1) = -1$$
* *Conclusion:* Since $\left(\frac{29}{101}\right) = -1$, the congruence $x^2 \equiv 29 \pmod{101}$ is *not solvable*.
:::