Reduction of quadratic congruences to those with prime modulus
The theory of quadratic residues concerns the existence of solutions to the congruence $x^2\equiv a \pmod m$. Any quadratic congruence $Ax^2+Bx+C\equiv 0 \pmod m$ can be transformed easily into this form (or into a linear congruence). The number $a$ is called a quadratic residue if the congruence is solvable. The following proposition shows that it is enough to consider the congruence when $m$ is prime or $m=4$.
Proposition 1. Let $m=2^{d}p_1^{\alpha_1}...p_k^{\alpha_k}$, where $p_i$ are distinct odd primes. Then the congruence $x^2\equiv a \pmod m$ has a solution if and only if each of the congruences $x^2\equiv a \pmod{p_i}$, $i=1,...,k$ and $x^2\equiv a \pmod{2^{d'}}$ has a solution. Here $d'=2$ if $d\geq 2$, $d'=1$ if $d=1$ and $d'=0$ otherwise.
Proof. The only if part is trivial, so we prove the if part. By the Chinese remainder theorem, $x^2\equiv a \pmod m$ has a solution if and only if each of the congruences $x^2\equiv a \pmod{p_i^{\alpha_i}}$, $x^2\equiv a \pmod{2^d}$ has a solution. First let $p$ be odd. Now if $x^2\equiv a \pmod p$ has a solution, so does $x^2\equiv a \pmod{p^{\alpha}}$. To see this, we use induction on $\alpha$; the case $\alpha=1$ is trivial. Let $x_0^2\equiv a \pmod{p^{\alpha-1}}$. Now $(x_0+kp^{\alpha-1})^2\equiv x_0^2+2kp^{\alpha-1}\pmod{p^{\alpha}}.$ We have $x_0^2=a+r\cdot p^{\alpha-1}$ for some integer $r$, so it suffices to choose $k$ such that $2k\equiv -r \pmod p$, which is possible as $p$ is odd.
Next let $p=2$. We show that if $x^2\equiv a \pmod 4$ is solvable, then so is $x^2\equiv a\pmod{2^{\alpha}}$. We use induction and assume $x_0^2\equiv a \pmod{2^{\alpha-1}}$. We may assume $x_0=a+r\cdot 2^{\alpha-1}$, where $r$ is odd, as otherwise we are done. Now $(x_0+2^{\alpha-2})^2\equiv a+(r+1)2^{\alpha-1}+2^{2\alpha-2}\equiv a \pmod{2^{\alpha}}$ since $\alpha\geq 2$. ■
Now the study of quadratic congruences has been reduced to solving $x^2\equiv a \pmod p$ where $p$ is a prime. To study this, we define the Legendre symbol, which makes determining the solvability of quadratic congruences much easier.
Definition. Let $a$ be an integer and $p$ an odd prime. Then we define the Legendre symbol as
\[\begin{eqnarray}\left(\frac{a}{p}\right)=\begin{cases}1\quad \text{if}\quad x^2\equiv a \pmod p\quad \text{for some}\quad x\not \equiv 0\pmod p,\\0 \quad \text{if}\quad p\mid a,\\-1\quad\text{otherwise.}\end{cases}\end{eqnarray}\]
Euler's criterion shows that the symbol is multiplicative.
Theorem 2 (Euler's criterion). We have $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$.
Proof. Suppose $a\neq 0\pmod p$, since that case is trivial. If $a\equiv x^2\pmod p$, then clearly both sides are $1\pmod p$. Since $a^{p-1}\equiv 1 \pmod p,$ we have $a^{\frac{p-1}{2}}\equiv \pm 1\pmod p$. The congruence $a^{\frac{p-1}{2}}\equiv 1$ holds for the $\frac{p-1}{2}$ numbers $1^2,2^2,...,\left(\frac{p-1}{2}\right)^2$, so it cannot hold for any more numbers by Lagrange's theorem. Therefore $a^{p-1}\equiv -1 \pmod p$ if $a$ is not a square $\pmod p.$
Now we have $\left(\frac{ab}{p}\right)= \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, so in order to determine $\left(\frac{a}{p}\right)$ for any $a$, it suffices to know $\left(\frac{q}{p}\right)$, $\left(\frac{2}{p}\right)$ and $\left(\frac{-1}{p}\right)$ for all odd primes $q$. By Euler's criterion, $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$. The law of quadratic reciprocity determines the symbol $\left(\frac{q}{p}\right)$. The symbol $\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$ could be computed with a similar argument.
Gaussian sums and quadratic reciprocity
We are now in a position to state the law of quadratic reciprocity.
Theorem 3. Let $p$ and $q$ be distinct odd primes. Then
\[\begin{eqnarray}\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}.\end{eqnarray}\]
As mentioned, the proof is based on considering the Gauss sums
\[\begin{eqnarray}G_q=\sum_{m=1}^{q-1}\left(\frac{m}{q}\right)e^{\frac{2\pi i m}{q}}.\end{eqnarray}\]
This is the discrete Fourier transform of the numbers $\left(\frac{m}{q}\right)$. The basic idea of the proof is the based on the general principle that if we obtain enough information about a generating function (which to us is this discrete Fourier transform), then we can extract information about its coefficients. We will compute two quantities, and then combine the results to get the quadratic reciprocity law.
Lemma 4. Let $\chi(n)=\left(\frac{n}{q}\right)$ where $q$ is a prime (this is called a real Dirichlet character). Then $\chi$ has the discrete Fourier series
\[\begin{eqnarray}\chi(n)G_{q}=\sum_{n=1}^{q-1} \chi(m)e^{\frac{2\pi i mn}{q}}.\end{eqnarray}\]
Proof. First suppose $q\nmid n,$ and denote by $\mathbb{Z}_q^{\times}$ the invertible residue classes $\pmod q$. In this case the lemma follows from
\[\begin{eqnarray}\sum_{m=1}^{q-1}\chi\left(m\right)e^{\frac{2\pi i mn}{q}}&=&\sum_{m\in \mathbb{Z}_q^{\times}} \chi\left(m\right)e^{\frac{2\pi i mn}{q}}\\&=&\sum_{k\in\mathbb{Z}_q^{\times}} \chi\left(kn^{-1}\right)e^{\frac{2\pi i k}{q}} \quad (\text{denoting} \quad k=mn)\\&=&\chi\left(n^{-1}\right)G_q=\chi\left(n\right)G_q\end{eqnarray}\]
Then let $q\mid n.$ In that case the identity follows from $0=\sum_{n=1}^{q-1}\left(\frac{n}{q}\right),$ which is true since there are exactly $\frac{q-1}{2}$ quadratic residues $\pmod q$. ■
Lemma 5. For any odd integer $q$, we have $G_q^2=(-1)^{\frac{p-1}{2}}p$.
Proof. We apply the previous lemma to get
\[\begin{eqnarray}G_q^2&=&G_q\sum_{n\in \mathbb{Z}_q}\chi(n)e^{\frac{2\pi i n}{q}}\\&=&\sum_{n\in \mathbb{Z}_q}\sum_{m\in \mathbb{Z}_q} \chi(m)e^{\frac{2\pi i mn}{q}} e^{\frac{2\pi i n}{q}}\\&=&\sum_{m\in \mathbb{Z}_q}\chi(m)\sum_{n\in \mathbb{Z}_q} e^{\frac{2\pi i (m+1)n}{q}}.\end{eqnarray}\]
If $m\neq -1$ (in $\mathbb{Z}_q$), the inner sum is zero, and otherwise it is $q$. Therefore,
\[\begin{eqnarray}G_q^2=\chi(-1)q=(-1)^{\frac{q-1}{2}}q\end{eqnarray}\]
since $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ by Euler's criterion. ■
Lemma 6. For any distinct odd primes $p$ and $q$, we have $G_p^{q-1}=\left(\frac{q}{p}\right),$ where the equality is in a finite field $F$ containing $\mathbb{Z}_q$ and the $p$th roots of unity (it cannot be an equality in $\mathbb{C}$ since by Lemma 5 the number $G_p$ has absolute value $\sqrt{p}$).
Since the field $F$ contains $\mathbb{Z}_q$, it has characteristic $q$ (that is, $qx=0$ for $x\in F$), so the binomial formula gives $(a+b)^q=a+b$ for all $a,b\in F$. Let $\zeta_p$ be a primitive $p$th root of unity in $F$. We get
\[\begin{eqnarray}G_p^{q}=\sum_{m=1}^{p-1}\left(\frac{m}{p}\right)\zeta_p^{qm}.\end{eqnarray}\]
Let $m=q'n$ where $qq'\equiv 1 \pmod p$. Then
\[\begin{eqnarray}G_p^{q}=\sum_{n=1}^{q-1}\left(\frac{nq'}{p}\right)\zeta_p^{n}=\left(\frac{q'}{p}\right)G_p=\left(\frac{q}{p}\right)G_p,\end{eqnarray}\]
since $q$ is a quadratic residue if and only if its reciprocal $q'$ is. By Lemma 5, $G_p\neq 0$, so we may divide by it. ■
Now we can finish the proof of the law of quadratic reciprocity. We compute
\[\begin{eqnarray}G_p^q=(G_p^2)^{\frac{q-1}{2}}G_p=p^{\frac{q-1}{2}}(-1)^{\frac{(p-1)(q-1)}{4}}G_p\end{eqnarray}\]
by Lemma 5. On the other hand, by Lemma 6, the result in $F$ is $\left(\frac{q}{p}\right)G_p$. Comparing the quantities, we see that
\[\begin{eqnarray}p^{\frac{q-1}{2}}(-1)^{\frac{(p-1)(q-1)}{4}}=\left(\frac{q}{p}\right),\end{eqnarray}\]
and by Euler's criterion $\left(\frac{p}{q}\right)=p^{\frac{q-1}{2}}$, which completes the proof. ■
