•  Number Theory and Cryptography – Math UN3020, for undergraduate students at Columbia University.
• mcgil MATH 346 Number Theory
• ucalgary MATH 641.01 – Algebraic Number Theory
• UCB Math613-Winter2023

If $p$ is a prime, the discussion of the congruence $x^2 \equiv a(p)$ is fairly easy. It is solvable iff $a^{(p-1) / 2} \equiv 1(p)$. With this fact in hand a complete analysis is a simple matter. However, if the question is turned around, the problem is much more difficult. Suppose that $a$ is an integer. For which primes $p$ is the congruence $x^2 \equiv a(p)$ solvable? The answer is provided by the law of quadratic reciprocity. This law was formulated by Euler and A. M. Legendre but Gauss was the first to provide a complete proof. Gauss was extremely proud of this result. He called it the Theorema Aureum, the golden theorem.

We shall present an ingenious proof due to Eisenstein. For a somewhat more elementary and standard proof, see.

A complex number $\zeta$ is called an $n$th root of unity if $\zeta^n=1$ for some integer $n>0$. If $n$ is the least integer with this property, then $\zeta$ is called a primitive $n$th root of unity.

The $n$th roots of unity are $1, e^{2 \pi i / n}, e^{(2 \pi i / n) 2}, \ldots, e^{(2 \pi i / n)(n-1)}$. Among these the primitive $n$th roots of unity are $e^{(2 \pi i / n) k}$, where $(k, n)=1$.

If $\zeta$ is an $n$th root of unity and $m \equiv l(n)$, then $\zeta^m=\zeta^l$. If $\zeta$ is a primitive $n$th root of unity and $\zeta^m=\zeta^l$, then $m \equiv l(n)$.

If $n>0$ is odd, we have
$$x^n-y^n=\prod_{k=0}^{n-1}\left(\zeta^k x-\zeta^{-k} y\right), \quad \text { where } \zeta=e^{2 \pi i / n}$$

If $n$ is a positive odd integer and $f(z)=e^{2 \pi i z}-e^{-2 \pi i z}$, then
$$\frac{f(n z)}{f(z)}=\prod_{k=1}^{(n-1) / 2} f\left(z+\frac{k}{n}\right) f\left(z-\frac{k}{n}\right)$$

If $p$ is an odd prime, $a \in \mathbb{Z}$, and $p \nmid a$, then
$$\prod_{l=1}^{(p-1) / 2} f\left(\frac{l a}{p}\right)=\left(\frac{a}{p}\right) \prod_{l=1}^{(p-1) / 2} f\left(\frac{l}{p}\right)$$

Quadratic Reciprocity. Let $p$ and $q$ be distinct odd primes and $a \geq 1$ an integer. Then the following assertions are equivalent:
(a) $(p / q)(q / p)=(-1)^{((p-1) / 2)((q-1) / 2)}$.
(b) If $p \equiv \pm q(4 a), p \nmid a$, then $(a / p)=(a / q)$.

Proof. In order to show (a) implies (b) it is enough, by multiplicativity, to show that (b) holds when $a$ is prime. For $a=2$ the result follows from Proposition 5.1.3. If $a$ is an odd prime then by (a) $(a / p)=(-1)^{((p-1) / 2)((a-1) / 2)}(p / a)$. If $p \equiv q(4 a)$ then $(p / a)=(q / a)$ so that
\begin{aligned} \left(\frac{a}{p}\right) & =(-1)^{((p-1) / 2)((a-1) / 2)}\left(\frac{q}{a}\right)=(-1)^{((p-1) / 2)((a-1) / 2)}(-1)^{((q-1) / 2)((a-1) / 2)}\left(\frac{a}{q}\right) \ & =(-1)^{((a-1) / 2)((p+q-2) / 2)}\left(\frac{a}{q}\right) . \end{aligned}
But $p \equiv q(4 a)$ implies $p+q-2 \equiv 0$ (4) and the result follows. If, on the other hand $p \equiv-q(4 a)$, a similar calculation shows
$$\left(\frac{a}{p}\right)=(-1)^{((a-1) / 2)((p+q) / 2)}\left(\frac{a}{q}\right) .$$
Since $p+q \equiv 0$ (4) the result also holds in this case.
To show that (b) implies (a) suppose first of all that $p>q$ and $p \equiv q$ (4). The $p=q+4 a, a \geq 1$. Thus
\begin{aligned} \left(\frac{p}{q}\right) & =\left(\frac{q+4 a}{q}\right)=\left(\frac{a}{q}\right)=\left(\frac{a}{p}\right)=\left(\frac{4 a}{p}\right)=\left(\frac{p-q}{p}\right)=\left(\frac{-q}{p}\right) \ & =(-1)^{(p-1) / 2}\left(\frac{q}{p}\right) . \end{aligned}
If $p \equiv 1$ (4) then $(p / q)=(q / p)$ which gives (a). If $p \equiv 3$ (4) then $q \equiv 3$ (4) and we obtain $(p / q)=-(q / p)$ which is part (a) in that case. Finally if $p \equiv$ $-q$ (4) then, $p+q=4 a$ and
$$\left(\frac{p}{q}\right)=\left(\frac{-q+4 a}{q}\right)=\left(\frac{a}{q}\right)=\left(\frac{a}{p}\right)=\left(\frac{4 a}{p}\right)=\left(\frac{p+q}{p}\right)=\left(\frac{q}{p}\right) .$$
Thus $(p / q)=(q / p)$ which is the assertion of part (a) since in this case at least one of $p$ or $q$ must be congruent to 1 modulo 4 . The proof is complete.

Problem 1. If $p \equiv 1$ (4), show that $p$ is the sum of two squares; i.e., $p=a^2+b^2$ with $a, b \in \mathbb{Z}$. (Hint: $p=\alpha \beta$ with $\alpha$ and $\beta$ being nonunits in $\mathbb{Z}[i]$. Take the absolute value of both sides and square the result.) This important result was discovered by Fermat.
Problem 2. An integer is called a biquadratic residue modulo $p$ if it is congruent to a fourth power. Using the identity $x^4+4=\left((x+1)^2+1\right)\left((x-1)^2+1\right)$ show that -4 is a biquadratic residue modulo $p$ iff $p \equiv 1$ (4).
Problem 3. Suppose that $f$ is such that $b \equiv a f(p)$. Show that $f^2 \equiv-1(p)$ and that $2^{(p-1) / 4} \equiv$ $f^{a b / 2}(p)$.
Problem 4. Show that $x^4 \equiv 2(p)$ has a solution iff $p$ is of the form $A^2+64 B^2$.

BS equation代写