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

\begin{aligned} q(p^2-1)/8 &=& p m &+ b_1 + ... + b_t + c_1 + ... + c_u \\ &=& p m &+ b_1 + ... + b_t + u p + (p - c_1) + ... + (p - c_u) \\ &=& p m &+ u p + 1 + 2 +...+ (p-1)/2 \\ &=& p m &+ u p + (p^2-1)/8 \end{aligned}

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

$\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$

otherwise

$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right) .$

which we can state as

$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

Proof: From above, we need only show

$m + n = (p-1)(q-1)/4$

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:

$\left(\frac{31}{103}\right) = -\left(\frac{103}{31}\right) = -\left(\frac{10}{31}\right) = -\left(\frac{2}{31}\right) \left(\frac{5}{31}\right) = -(-1)\left(\frac{5}{31}\right)$

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

$\left(\frac{5}{31}\right) = -\left(\frac{31}{5}\right) = -\left(\frac{1}{5}\right) = -1 .$

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

$\left(\frac{a}{b}\right) = \left(\frac{a}{p_1}\right)^{k_1} ... \left(\frac{a}{p_n}\right)^{k_n}$

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

$\left(\frac{a}{b_1 b_2}\right) = \left(\frac{a}{b_1} \right) \left(\frac{a}{b_2}\right)$

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

$\left(\frac{-1}{b}\right) = (-1)^{(b-1)/2}$
$\left(\frac{2}{b}\right) = (-1)^{(b^2-1)/8}$
$\left(\frac{a}{b}\right) \left(\frac{b}{a}\right) = (-1)^{\frac{a-1}{2}\frac{b-1}{2}}$

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

Example:

$\left(\frac{31}{103}\right) = -\left(\frac{103}{31}\right) = -\left(\frac{-21}{31}\right) = -\left(\frac{-1}{31}\right) \left(\frac{21}{31}\right)$
$= \left(\frac{31}{21}\right) = \left(\frac{-11}{21}\right) = \left(\frac{-1}{21}\right) \left(\frac{11}{21}\right) = \left(\frac{21}{11}\right) = \left(\frac{-1}{11}\right) = -1 .$

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