# Quadratic Reciprocity (April 29)


:::{.remark}
Last time: quadratic residues mod $p$, and how all of the usual content from a first course in number theory follows immediately from the high-powered machinery of the Frobenius and cyclotomic fields.
The problem we were looking at was the following: given $a\in \ZZ_{\neq 0}$, classify all odd primes $p$ where $\symb{a}{p} = 1$.

For $a=-1$, we saw that this happens iff $p \equiv 1 \mod 4$, and for $a=2$, $p\equiv \pm 1 \mod 8$.
The key facts for the latter were that $\QQ(i) = \QQ(\zeta_4)$  and $\QQ(\sqrt 2) \subseteq \QQ(\zeta_8)$.
Then because the Legendre symbol is multiplicative, we can reduce to the case $a=q$ is an odd prime.


This was solved by Gauss in the early 19th century, which he called the "golden theorem", but is more commonly known now as the law of quadratic reciprocity.
:::

## Quadratic Reciprocity

:::{.definition title="?"}
For an odd prime $p$, define $p^* \da \pm p$ with the sign chosen such that $p^* \equiv 1 \mod 3$.
Explicitly, one can check that $p^* = (-1)^{p-1\over 2}p$.
The law of **quadratic reciprocity** states the following: if $p, q$ are distinct odd primes, then
\[
\symb{q^*}{p} = \symb{p}{q}
.\]
:::

:::{.remark}
This is not the usual formulation, but it can be recovered easily: note that
\[
\symb{q^*}{p}
&=
\symb{(-1)^{q-1 \over 2} q}{p}\\
&=
\symb{-1}{p}^{q-1 \over 2} \symb{q}{p} \\
&= 
\qty{ (-1)^{p-1\over 2} }^{q-1 \over 2} \symb{q}{p} \\
\implies 
(-1)^{ {p-1\over 2}{q-1 \over 2} } 
&= \symb{p}{q} \symb{q}{p}
,\]
where the last step follows from multiplying through by $\symb{q}{p}$ and noting that $\symb{q}{p}^2 = 1$
:::

:::{.proof title="of quadratic reciprocity"}
Let $p\neq q$ be distinct odd primes.
Then $\Gal(\QQ(\zeta_q) / \QQ)\cong (\ZZ/q)\units$.
Since this is a cyclic group of even order, there is a unique index 2 subgroup, which we can take to be the subgroup of square $U(\ZZ/q)^2$.
By Galois theory, the fixed field $\QQ(\zeta_q)^H$ corresponds to a unique quadratic subfield.

:::{.claim}
This subfield is exactly $\QQ(\sqrt{q^*})$.
:::

:::{.proof title="?"}
Let $K\da \QQ(\zeta_q)^H$, so we have a tower $\QQ(\zeta_q)/K/\QQ$.
Suppose $r$ is a prime that ramifies in $K$, then it ramifies in any larger field by multiplicativity of the $e$ values.
So $r$ ramifies in $\QQ(\zeta_q)$, but the only primes that can possibly ramify in any $\QQ(\zeta_m)$ are those that divide $m$.
So $r\divides q$, forcing $r=q$, so the only prime that ramifies is $q$.

Write $K = \QQ(\sqrt d)$ for $d$ squarefree, then every prime dividing $d$ is ramified in $K$.
So $d$ is not divisible by any primes other than $q$.
Thus $d$ could be $\pm q$ or $-1$, noting that the $d=1$ case doesn't yield a quadratic extension, and we'd like to show that $q^*$ is the only viable option.
We can rule out $d=-1$, since 2 ramifies in $\QQ(\sqrt{-1}) = \QQ(i)$ -- but the only prime that can ramify is $q$, which was an *odd* prime.

We can also rule out which ever value of $q$ yields $q\equiv 3 \mod 4$, since again 2 ramifies in this case. 
This was a general fact: for $K=\QQ(\sqrt d)$ with $d\equiv 3 \mod 4$, then 2 automatically ramifies.
So $q\equiv 1\mod 4$, and $d = q^*$.
:::

:::{.remark}
This can also be proved with Gauss sums, but we don't necessarily need that here.
:::

Continuing the proof, consider $\QQ(\zeta_q)/\QQ(\sqrt{q^*})/\QQ$ with primes $Q/R/p$ lying over $p$.
We'll show that $\symb{p}{q} = 1 \iff \symb{q^*}{p} = 1$, making them equal.
Note that $\symb{p}{q} = 1 \iff p$ is a square in $U(\ZZ/q) \iff \Frob_{Q/p} \in H$.
This happens $\iff \ro{\Frob_{Q/p}}{\QQ\sqrt{q^*}} = \id$, which we can write as $\Frob_{R/P} = \id$, or equivalently the symbol $\symb{\QQ(\sqrt{q^*} /\QQ)}{p} = \id$.
Since we can write this as the Legendre symbol $\symb{q^*}{p} = 1$ when we identify $\Gal(\QQ(\sqrt{d^*})/\QQ) \cong \ts{\pm 1}$, which is precisely what we wanted.
:::

## Applying Quadratic Reciprocity: Recovering Classical Results

:::{.example title="of applying quadratic reciprocity"}
Let $a = 6$, then for odd primes $p$ not dividing $6$,
\[
\symb 6 p = 1 \iff p = 1,5,19,23\mod 24
.\]
Note that $6\divides 24$, and importantly $\phi(24) = 8$ and this allowed list is 4 elements, so exactly half are squares.
:::

:::{.theorem title="?"}
Let $a\in \ZZ_{\neq 0}$ with $a$ not a square, then

1. If $p, p'$ are distinct odd primes not dividing $a$ with $p\equiv p' \mod 4\abs{a}$, then $\symb a p = \symb a {p'}$.
  So $\symb a p = 1$ is entirely a function of the equivalence class of $p \mod 4\abs{a}$.

2. The number of allowable residue class modulo $4\abs{a}$ is precisely ${1\over 2}\phi(4\abs a)$.

:::

:::{.remark}
For odd $p$ not dividing $a$, we have $\symb a p = \symb {\QQ(\sqrt a) / \QQ}{p}$ where we identify $\Gal(\QQ(\sqrt a)/\QQ)= \ts{\pm 1}$.
We did this for $a$ squarefree, but we can generally write $a = a_0 a_1^2$ with $a_0$ squarefree, and the claim is that replacing $a$ with $a_0$ doesn't change either side of this equality.
The right-hand side doesn't change since $\QQ(\sqrt a) \cong \QQ(\sqrt{a_0})$, and the left-hand side doesn't change because 
\[
\symb a p = \symb {a_0}{p} \symb {a_1}{p}^2 = \symb{a_0} p \cdot 1 = \symb {a_0} p
.\]

:::

:::{.lemma title="?"}
The proportion of primes $p$ with $\symb a p = 1$ is exactly $1/2$.
:::

:::{.proof title="of lemma"}
If $p$ is odd and doesn't divide $a$, so $p$ doesn't divide $2a$, then $\symb a p = \symb{ \QQ(\sqrt a) / \QQ}{p}$.
Applying Chebotarev's density to this Frobenius yields that the proportion of $p$ for which the right-hand side equals 1 is $\#\ts{\id}/2 = 1/2$, noting that the denominator is just the degree of the extension, which is quadratic.
:::

:::{.exercise title="A fun one"}
For what proportion of $p$ is 2 a cube mod $p$?
:::

:::{.proof title="of theorem, part 1"}
Suppose $p\equiv p' \mod 4\abs a$ with $p\notdivides 2a$. 
From a homework problem, $\QQ(\sqrt a) \subseteq \QQ(\zeta_{4\abs a})$.
So we have a tower $\QQ(\zeta_{4\abs a})/\QQ(\sqrt a)/\QQ$, and corresponding towers of primes $Q/R/p$ and $Q'/R'/p'$.
Since we're assuming $p\equiv p' \mod 4\abs a$, we have $\Frob_{Q/p} = \Frob_{Q'/p'}$.
Restricting both to $\QQ(\sqrt a)$ we get 

- $\Frob_{R/p} = \symb{ \QQ(\sqrt a) / \QQ} p = \symb a p$,
- $\Frob_{R'/p'} = \symb{ \QQ(\sqrt a) / \QQ} {p'} = \symb a {p'}$,

so the two Legendre symbols are equal.
:::

:::{.proof title="of theorem, part 2"}
List the coprime residue classes $\mod 4\abs a$ corresponding to $\symb a p = 1$, say $a_1, \cdots, a_k \mod 4\abs a$.
By Dirichlet's theorem on prime progressions (or Chebotarev density on $\QQ(\zeta_{4\abs a})$), we know that the proportion of $p$ with $p\equiv a_i \mod 4\abs a$ is $1/\phi(4\abs a)$.
Adding these up yields $k/\phi(4\abs a)$.
But we just computed this proportion alternatively and found it to be $1/2$, so this forces $k = (1/2) \phi(4\abs a)$.
:::

:::{.exercise title="?"}
Think about the theorem of Hasse which stated that the primes $p$ for which $2$ has an even order $\mod p$ has density $17/24$.
A way to start: divide up the primes according to the largest power of 2 that divides $p-1$.
For $2^1\divides p-1$ but $2^2$ does not, these are primes $p\equiv 3\mod 4$, $a$ has even order precisely when $a$ is not a square $\mod p$, since otherwise if $a$ is a square then the order will divide $p-1\over 2$, which is odd, and the order will be odd.
So one should think about which primes $p\equiv 3\mod 4$ for which (for example) $2$ is not a square $\mod p$, and these ideas will apply.

For $2^2 \divides p-1$ but $2^3$ does not, such primes are of the form $p\equiv 5 \mod 8$.
When does 2 have even order?
Now one needs 2 not to be a *fourth* power, and one can find the density of primes for which $2$ is not a 4th power $\mod p$ and $p\equiv 5\mod 8$ using these ideas, but it's harder.

For $2^3$, one gets $p\equiv 9\mod 16$ and needs $2$ to not be an eighth power.

Doing this for every $k$ and summing all of the densities will yield $17/24$.
:::