# Reciprocity

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

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$ arequadratic residuesmod $5$, $\big( \frac{1}{5} \big)=\big( \frac{4}{5} \big)=1$. Since $2$ and $3$ arequadratic non-residuesmod $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$:

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$,

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.

Modulus: | |||

Exponential mapping: |