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) \pmod 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 \pmod 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 < r_i < p$$. Reading the proof of Gauss' Lemma, we see these are precisely 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 \pmod 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$$.

This method is flawed because it relies on factoring, so we might think we should stick to our original modular exponentiation for computing the Legendre symbol. But it turns out all is well once we extend the Legendre symbol.

## 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. 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$$.

Ben Lynn blynn@cs.stanford.edu 💡