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 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{2}{b}\right) = (-1)^{(b-1)/2} \] \[ \left(\frac{-1}{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$.