Introduction

Historically, thanks to Gauss, the quadratic reciprocity law marked the beginning of algebraic number theory. Therefore it it deserves a good dose of attention. However, whacking the definition to the beginner would not work pretty well.

We consider the equation

$x^2+by = a,\; (a,b\in \mathbb{Z}),$

one of the simplest non-trivial multi-variable Diophantine equations that can be imagined. Trying to violently search all solutions without any precaution is not wise. Therefore we consider reductions first. In order that $x^2+by=a$ has a solution, it is necessary that

$x^2 \equiv a \pmod{b}.$

Then the Chinese remainder theorem inspires us to first look into the case when $b$ is a prime. The case when $b=2$ is excluded because we are only allowed to study whether $x$ is odd or even.

Therefore we study the equation $x^2=a$ in the finite field of order $p$ where $p \ne 2$. We give a very straightforward characterisation, which is seemingly stupid. For $a \in \mathbf{F}_p^\ast$, define

$\left(\frac{a}{p}\right)=\begin{cases}\;\;\;1 & \text{$x^2=a$ has at least one solution in $\mathbf{F}_p$,} \\-1 & \text{$x^2=a$ has no solution in $\mathbf{F}_p$.}\end{cases}$

It is also convenient to define $\left(\frac{0}{p}\right)=0$.

This post will start with an equivalent form that is easier to compute (although less intuitive). Then we will demonstrate how to do basic computation of it, and finally we try to view it in a view of algebraic number theory.

Elementary Observations

Basic Computation

We begin with a simplified formula for the Legendre symbol.

Proposition 1. $\left(\frac{a}{p}\right) = a^\frac{p-1}{2}$ for $a \in \mathbf{F}_p^\ast$.

N.B. The power on the right hand side is taken in the corresponding finite field. For example, $\left(\frac{2}{3}\right)=2=-1$ in $\mathbf{F}_3$. By abuse of language, we identify integers $1$ and $-1$ with its canonical images in the finite field.

Proof. Notice that $\left(\frac{a}{p}\right)=1$ if and only if $a \in \mathbf{F}_p^{\ast 2}$. The rest comes from the following lemma which deserves to be stated separately in a more general literature. $\square$

Lemma 1. Let $p$ be a prime (it can be $2$ this time) and $K$ a finite field of order $q=p^n$ for some $n>0$. Then
If $p=2$, then all elements of $K$ are squares.
If $p \ne 2$, then the squares $K^{\ast 2}$ of $K^\ast$ form a subgroup of index $2$ in $K^*$; it is the kernel of the map $p:x \mapsto x^{(q-1)/2}$ from $K^\ast $ to $\{-1,1\}$.
To be precise, one has an exact sequence of cyclic groups:
$1 \to K^{\ast 2} \to K^\ast \xrightarrow{p} \{1,-1\} \to 1.$

Proof. The first case is a restatement on the condition of Frobenius endomorphism being an automorphism (see nlab). For the second case, let $\overline{K}$ be an algebraic closure of $K$. If $x \in K^\ast$, let $y \in \overline{K}$ be a square root of $x$, i.e. such that $y^2=x$. We have

$y^{q-1}=x^{(q-1)/2} = \pm 1 \;\text{ since }x^{q-1}=1.$

Since $x \in K^{\ast 2}$ if and only if $y \in K^\ast$, which is equivalent to $y^{q-1}=p(x)=1$, one has $\ker p = K^{\ast 2}$. The rest follows from elementary calculation. $\square$

You need to recall or study basic structures of finite fields. For example, a finite field is always of prime power order. All finite fields of order $p^n$ are isomorphic, uniquely determined as a subfield of an algebraic closure of $\mathbf{F}_p$, being the splitting field of the polynomial $X^{p^n}-X$. Besides, the multiplicative group of a finite field is cyclic.

From proposition 1 it follows that

Corollary 1. For any prime number $p \ne 2$,
The Legendre symbol is multiplicative, i.e. $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.
$\left(\frac{1}{p}\right)=1$
$\left(\frac{-1}{p}\right)=(-1)^{\varepsilon(p)}$ where $\varepsilon(p)=\frac{p-1}{2} \pmod{2}$.

The harder thing to compute is the Legendre symbol when $a=2$.

Proposition 2. One has $\left(\frac{2}{p}\right)=(-1)^{\omega(p)}$ where $\omega(p)=\frac{p^2-1}{8}\pmod{2}$.

We want to find a square root of $2$, i.e. an element $y$ satisfying $y^2=2$ so that computing $2^{(p-1)/2}$ becomes computing $y^{p-1}$. This is not a easy job, and we do not expect to find it inside the field. For example, $\left(\frac{2}{3}\right)=2=-1$ and $\left(\frac{2}{5}\right)=4=-1$, meaning there is not such a $y$ in $\mathbf{F}_3$ and $\mathbf{F}_5$. However, there is an easy way to generate a $2$. Consider $y=\alpha+\alpha^{-1}$, then $y^2=2+\alpha^2+\alpha^{-2}$. If we have $\alpha^2+\alpha^{-2}=0$ then we are done. To find such an $\alpha$, notice that $\alpha^2+\alpha^{-2}=0$ implies that $\alpha^4+1=0$. Therefore $\alpha^8=1$. It suffices to use a primitive $8$th root of unity.

Proof. Let $\alpha$ be a primitive $8$th root of unity in a algebraic closure $\Omega$ of $\mathbf{F}_p$. Then $y=\alpha+\alpha^{-1}$ verifies $y^2=2$. Since $\Omega$ has characteristic $p$, we have

$y^p=\alpha^p+\alpha^{-p}.$

Observe that if $p \equiv 1 \pmod{8}$, then $y^p=\alpha+\alpha^{-1}=y$ (we used the fact that $\alpha$ is an $8$th root of unity). Therefore $y^{p-1}=\left(\frac{2}{p}\right)=1$. This inspires us to determine $y^{p-1}$ through the relation between $p$ and $8$. As $p$ is odd, there are four possibilities: $p\equiv 1,3,5,7 \pmod{8}$.

If $p \equiv 7 \pmod{8}$, i.e. $p \equiv -1 \pmod{8}$, we still have $y^p=\alpha^{-1}+\alpha=y$. Therefore $\left(\frac{2}{p}\right)=1$ whenever $p \equiv \pm 1 \pmod{8}$. This discovery inspires us to study $p \equiv \pm 5 \pmod{8}$ together. When this is the case, one finds $y^p=\alpha^5+\alpha^{-5}$. Since $\alpha^4=\alpha^{-4}=-1$ (the primitivity of $\alpha$ matters here), $y^p$ becomes $-(\alpha+\alpha^{-1})=-y$. Cancelling $y$ on both sides, we obtain $y^{p-1}=\left(\frac{2}{p}\right)=-1$. To conclude,

$\left(\frac{2}{p}\right)=\begin{cases}1 &p\equiv \pm 1\pmod{8} \\-1 & p\equiv \pm 5 \pmod{8}\end{cases}$

It remains to justify the $\omega$ function as above. We need to find a function $\omega(n)$ such that $\omega(n) \equiv 0 \pmod 2$ when $p \equiv \pm 1 \pmod 8$ and $\omega(n) \equiv 1 \pmod 2$ when $p \equiv \pm 5 \pmod 8$. If we square $p$, we can ignore the difference of the signs:

$\begin{aligned}p&=8k \pm 1 \implies p^2=64k^2\pm 16k+1 \implies p^2-1=8 \cdot 2 \cdot (4k^2\pm k), \\p&=8k \pm 5 \implies p^2=64k^2\pm 80k +25 \implies p^2-1 = 8 \cdot (8k^2\pm10k+3).\end{aligned}$

Therefore, whether $(p^2-1)/8$ is odd or even is completely determined by the remainder of $p$ modulo $8$. We therefore put $\omega(p)=(p^2-1)/8$ and this concludes our proof. $\square$

To conclude in simpler form, we have

$1$ is always a square root in a finite field.
$-1$ is a square root in $\mathbf{F}_p$ if and only if $\frac{p-1}{2}$ is even, i.e., $p \equiv 1 \pmod{4}$.
$2$ is a square root in $\mathbf{F}_p$ if and only if $\frac{p^2-1}{8}$ is even, i.e. $p \equiv \pm 1 \pmod{8}$.

Gauss’s Quadratic Reciprocity Law

Nevertheless, you do not want to compute $\left(\frac{37}{53}\right)$ by hand in the basic way as above. However, granted the following law, things is much easier.

Proposition 3 (Gauss’s Quadratic Reciprocity Law). For two distinct odd prime numbers $p$ and $\ell$, the following identity holds:
$\left(\frac{\ell}{p}\right)\left(\frac{p}{\ell}\right)=(-1)^{\varepsilon(p)\varepsilon(\ell)}.$
Alternatively,
$\left(\frac{\ell}{p}\right)=\left(\frac{p}{\ell}\right)(-1)^{\varepsilon(\ell)\varepsilon(p)}.$

Instead of computing $37^{(53-1)/2}$ modulo $53$, we obtain $\left(\frac{37}{53}\right)$ in a much easier way

$\left(\frac{37}{53}\right)=\left(\frac{53}{37}\right)=\left(\frac{16}{37}\right)=\left(\frac{2}{37}\right)^4=1.$

In other words, there exist solutions of the equation $x^2+53y=37$.

The proof is carried out by Gauss sum. The proof looks contrived, but one can see a lot of important tricks. We will use corollary 1.1 frequently.

Proof. Again, let $\Omega$ be an algebraic closure of $\mathbf{F}_p$, and let $\omega \in \Omega$ be a primitive $\ell$-th root of unity. If $x \in \mathbf{F}_\ell$, then $\omega^x$ is well-defined. Thus it is legitimate to write the “Gauss sum”:

$y = \sum_{x \in \mathbf{F}_\ell}\left(\frac{x}{\ell}\right)\omega^x.$

Following the inspiration of what we have done in proposition 2, we study $y^2$ and $y^{p-1}$ again. The second one is quick.

Claim 1. $y^{p-1}=\left(\frac{p}{\ell}\right)$.

To show claim $1$, we notice that, as $\Omega$ is of characteristic $p$, we have

$y^p = \sum_{x \in \mathbf{F}_\ell}\left(\frac{x}{p}\right)\omega^{xp}=\sum_{z \in \mathbf{F}_\ell}\left(\frac{zp^{-1}}{\ell}\right)\omega^z=\left(\frac{p^{-1}}{\ell}\right)\sum_{z \in \mathbf{F}_\ell}\left(\frac{z}{\ell}\right)\omega^z = \left(\frac{p^{-1}}{\ell}\right)y$

and therefore

$y^{p-1}=\left(\frac{p^{-1}}{\ell}\right)=\left(\frac{p}{\ell}\right).$

Claim 2. $y^2 = \left(\frac{-1}{\ell}\right)\ell$ (by abuse of language, $\ell$ (the one outside the Legendre symbol) is used to denote the image of $\ell$ in the field $\mathbf{F}_p$.)

Notice that

$y^2= \sum_{x,z \in \mathbf{F}_\ell}\left(\frac{xz}{\ell}\right)\omega^{x+z}=\sum_{u \in \mathbf{F}_\ell}\omega^u\left(\sum_{t \in \mathbf{F}_\ell}\left(\frac{t(u-t)}{\ell}\right)\right)=\sum_{u \in \mathbf{F}_\ell}\omega^u\left(\sum_{t \in \mathbf{F}_\ell^\ast}\left(\frac{t(u-t)}{\ell}\right)\right).$

Terms where $t=0$ are ignored safely. Then we notice that

$\left(\frac{t(u-t)}{\ell}\right)=\left(\frac{-t^2}{\ell}\right)\left(\frac{1-ut^{-1}}{\ell}\right)=\left(\frac{-1}{\ell}\right)\left(\frac{t^2}{\ell}\right)\left(\frac{1-ut^{-1}}{\ell}\right)=\left(\frac{-1}{\ell}\right)\left(\frac{1-ut^{-1}}{\ell}\right).$

For this reason we put

$C_u=\sum_{t \in \mathbf{F}_\ell^\ast}\left(\frac{1-ut^{-1}}{\ell}\right).$

It follows that

$y^2 = \left(\frac{-1}{\ell}\right)\sum_{u \in \mathbf{F}_\ell}C_u\omega^u.$

It remains to compute the coefficients $C_u$. We see

$C_0 = \sum_{t \in \mathbf{F}_\ell^{\ast}}\left(\frac{1}{\ell}\right)=\sum_{t \in \mathbf{F}_\ell^\ast}1=\ell-1.$

When $u \ne 0$, the term $s=1-ut^{-1}$ runs over all of $\mathbf{F}_\ell$ except $1$. Therefore

$C_u=\sum_{s \in \mathbf{F}_\ell}\left(\frac{s}{\ell}\right)-\left(\frac{1}{\ell}\right)=-\left(\frac{1}{\ell}\right)=-1,$

since $[\mathbf{F}_\ell:\mathbf{F}_\ell^2]=2$ (read: exactly half of the elements of $\mathbf{F}_\ell$ are squares, the rest are not). Therefore

$y^2=\left(\frac{-1}{\ell}\right)(\ell-1-w-w^2-\dots-w^{\ell-1})$

Recall that $1-\omega^\ell=(1-\omega)(1+\omega+\dots+\omega^{\ell-1})=0$. As $\omega$ is a primitive root, we see $\omega \ne 1$ and therefore $1+\omega+\dots+\omega^{-\ell-1}=0$. The result follows.

Finally, the reciprocity follows because

$y^{p-1}=(y^2)^{\frac{p-1}{2}}=\left(\frac{\left(\frac{-1}{\ell}\right)\ell}{p}\right)=\left(\frac{p}{\ell}\right).$

We invite the reader to expand the identity above using corollary 1 and see the result. $\square$

Observation from Algebraic Number Theory

In this section we introduce some observation from a point of view of algebraic number theory without complete proofs.

Let $p$ be an odd prime, and $\zeta_p$ a primitive $p$-th root of unity. We have seen that the Gauss’s sum

$S_p = \sum_{x \in \mathbf{F}_p}\xi_p^x$

satisfies the relation

$S^2_p=\left(\frac{-1}{p}\right)p \implies \sqrt{p}=\sqrt{\left(\frac{-1}{p}\right)}S_p.$

Therefore the field $\mathbb{Q}(\sqrt{p})$ is contained in $\mathbb{Q}(\zeta_p)$ or $\mathbb{Q}(\zeta_p,i)$, depending on the sign of $\left(\frac{-1}{p}\right)$. The first one is a cyclotomic extension of $\mathbb{Q}$ by definition. The second one is not, but is a finite abelian extension of $\mathbb{Q}$. However, every finite abelian extension of $\mathbb{Q}$ is a subfield of a cyclotomic field. See this note. To conclude,

Every field of the form $\mathbb{Q}(\sqrt{p})$ lies in a subfield of $\mathbb{Q}(\zeta_m)$ for some $m>1$.

Solving the equation $x^2 \equiv a \pmod p$ also inspires us to look at the quadratic field $K=\mathbb{Q}(\sqrt{a})$. For simplicity we assume that $a$ is square free. If $\left(\frac{a}{p}\right)=1$, then there exists $\alpha \in \mathbb{Z}$ such that

$x^2-a \equiv (x-\alpha)(x+\alpha)\pmod p.$

This equation is interesting because on the left hand side we actually have the minimal polynomial of $K$, namely $p(x)=x^2-a$. The equation split completely modulo $p$. The relation above actually signifies that there exists prime ideals $\mathfrak{P}_1,\mathfrak{P}_2\subset \mathfrak{o}_k$ such that

$(p)=\mathfrak{P}_1^{e_1}\mathfrak{P}_2^{e_2}$

where the ramification indices $e_1=e_2=1$. This says the prime ideal $(p)$ is totally split in $\mathbb{Q}(\sqrt{a})$. Conversely, if $(p)$ is totally split in $\mathbb{Q}(\sqrt{a})$ (where $(a,p)=1$ for sure), then $\left(\frac{a}{p}\right)=1$. To conclude,

The Legendre symbol $\left(\frac{a}{p}\right)=1$ if and only if $(p)$ totally splits in $\mathbb{Q}(\sqrt{a})$.

In fact, one can have a more profound observation of number fields which will imply the quadratic reciprocity law:

Let $\ell$ and $p$ be two distinct odd primes, $S_\ell=\left(\frac{-1}{\ell}\right)\ell$, then $(p)$ is totally split in $\mathbb{Q}(S_\ell)$ if and only if $(p)$ splits totally into two an even number of prime ideals in $\mathbb{Q}(\zeta_\ell)$.

Besides you may want to know about Artin’s reciprocity which generalised Gauss’s reciprocity, but that’s quite advanced topic (class field theory). This also shows the significance of quadratic reciprocity law.

References

Jean-Pierre Serre, A Course in Arithmetic
Jürgen Neukirch, Algebraic Number Theory
Serge Lang, Algebraic Number Theory