## Quadratic Reciprocity

The law of *quadratic reciprocity*, noticed by Euler and Legendre
and proved by Gauss, helps greatly in the computation
of the Legendre symbol.

First, we need the following theorem:

**Theorem**: Let $p$ be an odd prime and $q$ be some integer coprime to $p$.
Let $m = \lfloor q/p \rfloor + \lfloor 2q/p \rfloor +...+ \lfloor ((p-1)/2)q/p \rfloor$.

Then $m = u + (q - 1) \mod 2$, where as in Gauss' Lemma, $u$ is the number of elements of $\{q, 2q,...,q(p-1)/2\}$ which have a residue greater than $p/2$. In particular when $q$ is odd, $m = u \mod 2$.

**Proof**: For each $i = 1,...,(p-1)/2$, the equation
$i q = p \lfloor i q/p \rfloor + r_i$ holds for some $0 \lt r_i \lt p$.
Reading the proof of Gauss' Lemma, we see these are preceisely the $b_i$ and
$c_i$.

Then summing these equations modulo 2 gives

Since $p$ is odd, we have $m = u + q - 1 \mod 2$.∎

**Theorem (Law of Quadratic Reciprocity)**: Let $p, q$ be distinct odd primes.
If $p = q = -1 \pmod {4}$, then

otherwise

which we can state as

**Proof**: From above, we need only show

where $m = \lfloor q/p \rfloor + \lfloor 2q/p \rfloor +...+ \lfloor ((p-1)/2)q/p \rfloor$, and $n$ is similarly defined by swapping $p$ and $q$.

Eisenstein found an elegant geometrical proof. Consider the line $L$ from $(0,0)$ to $(p,q)$, and the rectangle $R$ with corners at $(0,0)$ and $(p/2, q/2)$. How many lattice points lie strictly in $R$?

Simply computing the area of a rectangle gives $(p-1)(q-1)/4$. Alternatively, we can count the number of points above and below $L$ inside $R$, since no lattice points can lie on $L$ in $R$ since $p, q$ are coprime.

Consider the points below $L$ on the line $x = 1$. They have $y$-coordinates of $1, 2, ..., \lfloor q/p \rfloor$. When $x = 2$, there are $\lfloor 2q/p \rfloor$ points, and so on, giving a total of $m$ points below the $L$. Similarly there are $n$ points above $L$ in $R$, proving the result.

We can restate the proof algebraically. Consider the numbers $p y - q x$ for $x = 1,...,(p-1)/2$ and $y = 1,...,(q-1)/2$. There are a total of $(p-1)(q-1)/4$ numbers, not necessarily distinct. None are zero, since $p, q$ are coprime. The result follows after observing that $n$ of them are positive, and $m$ are negative.

**Example**:

since $2 = -5 \pmod{8}$. Next,

Hence $31$ is a quadratic nonresidue modulo $103$.

Note we had to factor a number during this computation, so for large numbers this method is not efficient without a fast factoring algorithm. Of course, to compute the Legendre symbol, we can simply perform a modular exponentiation, but it turns out by extending the Legendre symbol we can salvage the above method.

## The Jacobi Symbol

The *Jacobi symbol* $\left(\frac{a}{b}\right)$ is defined for all odd
positive integers $b$ and all integers $a$. When $b$ is prime,
it is equivalent to the Legendre symbol (which is why we reuse the notation).
If $b = 1$, define $\left(\frac{a}{1}\right) = 1$. Lastly, for other values of $b$,
factor $b$ into primes: $b = p_1^{k_1}...p_n^{k_n}$ and define

Thus for odd positive integers $b, b_1, b_2$ we have

Other properties of the Legendre symbol carry over. By inducting on the number of primes in the factorization of $b$, one can show:

The last property allows us to compute the Jacobi symbol without factoring.

**Example**:

Hence $31$ is a quadratic nonresidue modulo $103$.