Reciprocity

Lesson

Quadratic Reciprocity

In this lesson, reciprocity refers to the concept of generalizing quadratic reciprocity. Quadratic reciprocity is the study of perfect square residues. It asks when these perfect squares exist and what they are. The law of quadratic reciprocity gives conditions for some residue $a$ mod $n$ to have a square root, or a number $b$ mod $n$ such that $b^2 \equiv a$ mod $n$ . Hence $k$ -th reciprocity is the property of $a$ having a $k$ -th root. In other words, some number $b$ such that $b^k \equiv a$ mod $n$ .

Example: $0$ and $1$ always have $k$ -th roots mod $n$ for any $k,n \in \Z$ because $0^k \equiv 0$ and $1^k \equiv 1$ mod $n$ .

But do $k$ -th roots exist for all remainders and all moduli? The answer is no! The following visualization demonstrates the numbers in the range of the function $x^k$ mod $n$ for a given exponent $k$ and modulus $n$ . If a number $a$ is in the range of the function, that means it has a $k$ -th root mod $n$ , and the roots are the points that map to $a$ .

Example: $0$ , $1$ , and $4$ are the only numbers with square roots mod $5$ . Using the visual, are there any solutions to $x^2 \equiv 4$ mod $5$ ? What are they and how do you know?

Modulus:

Legendre Symbols

As it turns out, there exists a formula to determine whether or not a number is a quadratic residue modulo some number $n$ . This formula starts by finding the prime decomposition of $n$ and determining whether or not a number is a quadratic residue modulo $p$ for some prime $p$ dividing $n$ .

To do this, we use the language of Legendre symbols: for all integers $a$ and odd primes $p$ ,

\Big( \frac{a}{p} \Big) = \begin{cases} 0 &\text{if } a \equiv 0 \text{ mod } p \\ 1 &\text{if } a \not\equiv 0 \text{ mod } p \text{ and } \exists \; x : x^2 \equiv a \text{ mod } p \\ -1 &\text{if } a \not\equiv 0 \text{ mod } p \text{ and there is no such } x \end{cases}.

In other words, for nonzero $a$ , $\big( \frac{a}{p} \big)=1$ means that $a$ is a quadratic residue mod $p$ . Similarly, $\big( \frac{a}{p} \big)=-1$ means that $a$ is not a quadratic residue mod $p$ . In this case, we call $a$ either a quadratic non-residue or a non-quadratic residue.

As with the previous example, $\big( \frac{0}{5} \big)=0$ . Since $1$ and $4$ are quadratic residues mod $5$ , $\big( \frac{1}{5} \big)=\big( \frac{4}{5} \big)=1$ . Since $2$ and $3$ are quadratic non-residues mod $5$ , $\big( \frac{2}{5} \big)=\big( \frac{3}{5} \big)=-1$ .

Euler's Criterion

We can derive Euler's criterion to determine whether $a$ is a quadratic residue modulo $p$ :

a^{\frac{p-1}{2}} \equiv \Big( \frac{a}{p} \Big) \text{ mod } p.

Using this formula, we can determine if $a$ is a quadratic residue mod $p$ in two steps: first, compute $a^{\frac{p-1}{2}}$ mod $p$ , and then check whether it equals $1$ or $-1$ .

The following visual only allows for you to enter a prime modulus $p$ . The mapping is from a remainder $a$ to $a^{\frac{p-1}{2}}$ mod $p$ . If the arrow is on $1$ , the remainder $a$ is a quadratic residue mod $p$ . If the arrow is on $-1$ , the number is a quadratic non-residue mod $p$ .

	Modulus:	5
	Number to map:

Quadratic Reciprocity Law

Finally, we arrive at the quadratic reciprocity law: for any distinct odd primes $p$ and $q$ ,

\Big( \frac{p}{q} \Big) \Big( \frac{q}{p} \Big) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}.

This result allows us to switch the order of Legendre symbols and introduces a parity condition based on the primes themselves. If one of the primes is congruent to $1$ modulo $4$ , we have $\big( \frac{p}{q} \big) = \big( \frac{q}{p} \big)$ . If both of the primes are congruent to $3$ modulo $4$ , we have $\big( \frac{p}{q} \big) = -\big( \frac{q}{p} \big)$ . This dictates whether or not the number is a quadratic residue.

Example: we already saw that $\big( \frac{3}{5} \big)=-1$ . How can we determine $\big( \frac{5}{3} \big)$ ?
1. Since $5 \equiv 1$ mod $4$ , we automatically know $\big( \frac{3}{5} \big)=\big( \frac{5}{3} \big)=-1$
2. If we do it brute-force, notice $5 \equiv 2$ mod $3$ and reduce $\big( \frac{5}{3} \big)$ to $\big( \frac{2}{3} \big)$
3. Check $0^2, 1^2,$ and $2^2$ to see that $2$ is a quadratic non-residue mod $3$ . So, $\big( \frac{2}{3} \big)=-1$

Using the quadratic reciprocity law and the supplementary laws for the Legendre symbol, we can determine whether $a$ is a quadratic residue modulo any odd prime $p$ . Try it yourself. You can even change the exponent to check cubic reciprocity, quartic reciprocity, and more.