There are some classic theorems with many proofs, e.g. the infinitude of the primes, Quadratic reciprocity, the Pythagorean Theorem, and AM-GM. Today I’ll be giving you two proofs of quadratic reciprocity, which has over 240 proofs, 8 due to Gauss.

First, some motivation. The simplest type of equation that isn’t trivial to solve is a quadratic, of the form $$ ax^2+bx+c = 0$$ for some constants a,b,c. Luckily, over any field, we can reduce this to $$(x – m)^2 + n = 0$$ for some other constants m and n. Over the real or complex numbers, we know when this equation has solutions and what they are. In the integers mod a prime p, when do we have solutions? Conversely, given a prime p, for what primes q does $$x^2 \equiv p \pmod q$$ have a solution?

Now, some definitions and background:

Definition 1 (Legendre Symbol). Given a prime p and integer a coprime to p, the legendre symbol \[ \big( \frac{a}{p} \big) = \begin{cases} 1 & (\exists x \in \mathbb{Z}) x^2 \equiv a \pmod p \\-1 & \mathrm{otherwise}\\ \end{cases}\]. In other words, the Legendre symbol records whether or not a is q quadratic residue mod p.

Exercise. Show the Legendre symbol respects multiplication. That is, $$\big( \frac{a}{p} \big) \cdot \big( \frac{b}{p} \big) = \big( \frac{ab}{p} \big)$$.

Lemma 1 (Euler’s Criterion). $$\big( \frac{a}{p} \big) = a^{\frac{p-1}{2}} $$ for all odd primes p and integers a coprime to p. This fact was proven in my last post.

Theorem 1 (First supplement). -1 is a quadratic residue mod a prime p if and only if p is congruent to 1 mod 4. This can be proven by applying Euler’s criterion to -1.

Now I will state the second supplement to quadratic reciprocity and prove it in two different ways. This will preview the two methods I will use to prove the main theorem.

Theorem 2 (Second supplement). $$\big( \frac{2}{p} \big) = (-1)^{\frac{p-^1}{8}} $$. In other words, 2 is a quadratic residue mod p if and only if p is congruent to 1 or 7 mod 8.

Method 1 (The PROMYS way). Prove Gauss’s Lemma and then apply it to $$a = 2$$.

Lemma 1 (Gauss’s Lemma). $$\big( \frac{a}{p} \big) = (-1)^S $$ where $$S = \sum_{l=1}^{\frac{p-1}{2}} \lfloor \frac{2al}{p} \rfloor $$.

Proof. Note that $$al = \varepsilon_lr_l$$ where $$0 < r_l < \frac{p}{2}$$ and $$\varepsilon_l = (-1)^{\lfloor \frac{2al}{p} \rfloor}$$. Also note that $$r_l$$ is unique for each $$l$$. Then S measures the parity of the number of elements of $$a, 2a, \ldots, \frac{p-1}{2}a$$ which leave a remainder greater than $$\frac{p}{2}$$ when divided by p. Then we have $$a^{\frac{p-1}{2}} \big(\frac{p-1}{2}\big) ! = (-1)^S \big(\frac{p-1}{2}\big) ! $$, and the desired result follows after cancellation. $$\qed$$

Now we can prove the second supplement. We simply count the number of remainders of $$2, 2\cdot 2, \ldots, 2 \cdot \frac{p-1}{2}$$ which are greater than $$\frac{p}{2}$$. If p is congruent to 3 mod 4, then there are $$\frac{p-1}{2} – \frac{p-3}{4} = \frac{p+1}{4}$$ remainders greater than $$\frac{p}{2}$$. Then p must be congruent to 7 mod 8. If p is 1 mod 4, then there are $$\frac{p-1}{2} – \frac{p-1}{4} = \frac{p-1}{4}$$ remainders, so p must be congruent to 1 mod 8. $$\qed$$

Method 2 (Gauss Sums, but not really).

Let $$\zeta = e^{\frac{2i\pi}{8}}$$ and $$\tau = \zeta + \zeta^{-1}$$. Then note $$\tau^2 = 2$$. We have $$\tau^p = (\zeta + \zeta^{-1})^p  = 2^{\frac{p-1}{2}}\tau \equiv \big( \frac{2}{p} \big) \pmod p$$. However, by the binomial theorem, we have $$\tau^p \equiv \zeta^p + \zeta^{-p} \pmod p$$. Then check cases and note that $$\zeta^p + \zeta^{-p} = (-1)^{\frac{p^2-1}{8}}$$. Then we have $$\tau^p \equiv (\zeta^p + \zeta^{-p} ) (-1)^{\frac{p^2-1}{8}} \equiv \tau \big( \frac{2}{p} \big) \pmod p$$. The desired result follows.

Here is the main result in two ways.

Remark. The first method is more elementary and does not require manipulating complex numbers, but I think it relies too much on a combinatorial fact. However, you will learn all the basics of number theory doing it. The second one requires a little more background and it seems unnecessary to use complex numbers, but you’ll see why we need certain complex numbers (roots of irreducible polynomials over $$\mathbb{Q}$$) as you learn more.

Theorem 3 (Quadratic Reciprocity). Let $$p$$ and $$q$$ be positive odd primes. Then $$! \big( \frac{p}{q} \big) \big( \frac{q}{p} \big) = (-1) ^{\frac{p-1}{2} \frac{q-1}{2}} $$

Method 1 (Modify Gauss’s Lemma).

We will show that for odd a coprime to p, that $$\big( \frac{a}{p} \big)  = (-1)^S$$ where $$S = \sum_{l=1}^{\frac{p-1}{2}} \lfloor \frac{al}{p} \rfloor$$. Because the Legendre symbol is multiplicative and is always 1 or -1, we have that $$ \big( \frac{2a}{p} \big) = \bigg( \frac{\frac{p+a}{2}}{p} \bigg)$$. Then note \[  \bigg( \frac{\frac{p+a}{2}}{p} \bigg) =(-1)^{\sum_{l=1}^{(p-1)/2} \lfloor \frac{(p+a)l}{p} \rfloor} = (-1)^{\sum_{l=1}^{(p-1)/2} l + \lfloor \frac{al}{p} \rfloor} \]. That becomes $$ (-1)^{\frac{p^2-1}{8} + S $$, so then we have that $$\big( \frac{a}{p} \big)  = (-1)^S$$.

Then we show that \[ \sum_{m=1}^{(p-1)/2} \lfloor \frac{mq}{p} \rfloor + \sum_{m=1}^{(q-1)/2} \lfloor \frac{mp}{q} \rfloor = \frac{p-1}{2} \frac{q-1}{2} \]. This is left as an exercise (Hint: lattice points).

After that, we put the two results together and obtain QR.

Method 2 (Gauss Sums, really this time).

Define $$g_p = \sum_{k=1}^{p-1} \big( \frac{k}{p} \big) \zeta_p^k $$. Then we show that $$g_p^2 = p*$$, where $$p* = \big( \frac{-1}{p} \big) p $$. By definition we have $$! g_p^2 = \sum_{k,m=1}^{p-1} \big( \frac{km}{p} \big) \zeta_p^{k+m} $$. But then we get $$! g_p^2 = \sum_{k=1}^{p-1} \sum_{n=1}^{p-1} \big( \frac{k^2n}{p} \big) \zeta_p^{k+kn} $$ by setting $$n \equiv km \pmod p$$. We can simplify this to $$! \sum_{n=1}^{p-1} \left( \sum_{k=1}^{p-1} \zeta_p^{k(1+n)} \right) \big( \frac{n}{p} \big) $$. If $$n \neq p-1$$, then the inner sum runs through all the roots of $$\frac{x^p-1}{x-1}$$, so the inner sum is -1. If $$n=p-1$$, then the inner sum is $$p-1$$. Then we get $$! g_p^2 = – \sum_{n=1}^{p-2} \big( \frac{n}{p} \big) + (p-1) \big( \frac{-1}{p} \big) = -\sum_{n=1}^{p-1} \big( \frac{n}{p} \big) + p\big( \frac{-1}{p} \big) = p \big( \frac{-1}{p} \big) $$.

Now we can prove QR. Note $$!g_p^q = (p*)^{\frac{q-1}{2}}g_p \equiv \big( \frac{p*}{q} \big) g_p \pmod q $$. But by the binomial theorem, we have $$!g_p^q \equiv \sum_{k=1}^{p-1} \big( \frac{k}{p} \big) \zeta_p^{qk} \equiv \big( \frac{q}{p} \big) \sum_{k=1}^{p-1} \big( \frac{k}{p} \big) \zeta_p^k \equiv \big( \frac{q}{p} \big) g_p \pmod q$$. Then we can set the two congruences equal to each other and obtain $$! \big( \frac{q}{p} \big) \big( \frac{p}{q} \big) = \big( \frac{(-1)^{\frac{p-1}{2}}}{q} \big) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}} \qed $$

How many natural numbers can we write as a sum of two squares? Three? Four? What is the least $$n$$ such that we can write every natural number as a sum of $$n$$ squares? Try figuring these things out for yourself!

Here are some number theory facts to help you in your exploration.

Lemma 1 (Lagrange). A polynomial over any field $$K$$ of degree $$n$$ has at most $$n$$ roots.

Proof. Note that for polynomials $$f(x),g(x) \in K[x]$$, we can write $$! f(x) = g(x)q(x) + r(x)$$ where the degree of $$r$$ is less than the degree of $$g$$. Then we induct on the degree of the polynomial. We know linear polynomials have only one root. Then let $$f(x)$$ be of degree $$n$$ and suppose it has root $$a$$. Then $$f(x) = (x-a)q(x)$$, and the degree of $$q$$ is $$n-1$$, so we can apply the inductive hypothesis.

Lemma 2 (Euler). Let $$a$$ be coprime to a prime $$p$$. Then $$a$$ is a quadratic residue mod $$p$$ if and only if $$a^{\frac{p-1}{2}} \equiv 1 \pmod p$$.

Proof. From Fermat’s Little Theorem, we know $$(a^{p-1}-1) = (a^{\frac{p-1}{2}} – 1) (a^{\frac{p-1}{2}} + 1) \equiv 0 \pmod p$$, so $$a^{\frac{p-1}{2}}$$ is either $$1$$ or $$-1$$. Then if $$a \equiv x^2 \pmod p$$, $$a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod p$$. Then there are $$p-1$$ quadratic residues and at most $$p-1$$ roots of $$a^{\frac{p-1}{2}}-1$$, so quadratic non-residues must satisfy $$a^{\frac{p-1}{2}} \equiv -1 \pmod p$$. Then the result we want follows easily.

Lemma 3. -1 is a quadratic residue mod $$p$$ if and only if $$p \equiv 1 \pmod 4$$.

Proof. Apply Euler’s Criterion to $$a = -1$$.

Lemma 4. There exist integers $$a$$ and $$b$$ such that $$a^2+b^2+1 \equiv 0 \pmod p$$ for odd primes $$p$$.

Proof. As $$a$$ and $$b$$ range from $$0$$ to $$p-1$$, $$a^2$$ and $$-b^2-1$$ take on $$\frac{p+1}{2}$$ values mod $$p$$, so by the pigeonhole principle, there exist $$a$$ and $$b$$ such that $$a^2 \equiv -b^2-1 \pmod p$$.

Here is a geometry fact that might help you prove any conjectures you make:

Lemma 5 (Minkowski). Let $$L$$ be a lattice of determinant $$D$$ in $$\mathbb{R}^n$$ and $$S$$ be a convex subset of $$\mathbb{R}^n$$ that is symmetric about the origin and has volume $$V > 2^nD$$. Then $$S$$ contains a nonzero point of $$L$$.

Proof. It suffices to show the result for $$L = \mathbb{Z}^n$$ and then use the fact that linear maps preserve relative area. Consider $$f:S \rightarrow \mathbb{R}^n$$ given by $$(x_1, x_2, \ldots, x_n) \mapsto (x_1 \pmod 2, x_2 \pmod 2, \ldots, x_n \pmod 2) $$. Then, using the pigeonhole principle, it is clear that $$f$$ is not injective because it maps a region of volume greater than $$2^n$$ into a region of volume of $$2^n$$. Thus, we have $$s_1, s_2 \in S$$ that map to the same point. We know $$s_2 = s_1 + 2(i,j)$$, so $$\frac{s_2-s_1}{2} = (i,j) \in S$$ by symmetry about the origin and convexity, so we are done.

Here are the answers:

Theorem 1 (Fermat). A prime $$p$$ can be written as a sum of two squares if and only if $$p \equiv 1 \pmod 4$$ or $$p=2$$.

Proof. Note if $$p \equiv 3 \pmod 4$$, then it cannot be expressed as a sum of two squares because all squares are congruent to 0 or 1 mod 4.

If $$p \equiv 1 \pmod 4$$, then there is a natural number $$a < p$$ that satisfies $$a^2 \equiv -1 \pmod p$$. Then consider the lattice $$L$$ in $$\mathbb{R}^2$$ generated by $$l_1 = (a, 1)$$ and $$l_2 = (p,0)$$. Then this lattice has determinant $$p$$. Now consider the open disk given by $$x^2+y^2<2p$$. Clearly it is convex and symmetric with respect to the origin, so it contains a nonzero element of the lattice. Then see that $$(ma+np)^2 + m^2 = m^2(a^2+1) + 2mnap + n^2p^2$$ is divisible by $$p$$, so there is an element of the lattice $$(x, y)$$ that satisfies $$0<x^2+y^2<2p$$, so we must have $$x^2+y^2=p$$.

Theorem 2. A positive integer $$n$$ is expressible as the sum of two squares if and only if all prime factors of the form $$4k+3$$ have even power.

Proof. Note $$2 = 1^2+1^2$$. Now let $$n = a^2+b^2$$. Then if $$p=4k+3$$, $$p$$ divides both $$a$$ and $$b$$ (See if you can prove this yourself. Hint), so $$p^2$$ divides both $$a^2$$ and $$b^2$$. Thus $$p^2 \mid n$$. Then in the other direction if $$p_1, p_2, \ldots p_m$$ are of the form $$4k+1$$ and $$q_1, q_2, \ldots q_l$$ are of the form $$4k+3$$, $$n = 2^{a}p_1^{a_1}p_2^{a_2} \ldots p_m^{a_m}q_1^{2b_1}q_2^{2b_2} \ldots q_l^{2b_l} = (1+1)^a(x_1^2+y_1^2)^{a_1}(x_2^2+y_2^2)^{a_2} \ldots (x_m^2+y_m^2)^{a_m}q_1^{2b_1}q_2^{2b_2} \ldots q_l^{2b_l}$$ which is a sum of two squares because a product of a sum of two squares is also a sum of two squares (prove it yourself! Hint).

Theorem 3. All positive integers can be written as a sum of four squares.

Proof. It suffices to show this for odd primes because a product of a sum of four squares is a sum of four squares and because $$2 = 1^2+1^2+0^2+0^2$$. Consider positive integers $$a$$ and $$b$$ that satisfy $$a^2+b^2+1 \equiv 0 \pmod p$$. Then consider the lattice $$L$$ in $$\mathbb{R}^4$$ generated by $$(1, 0, -a, b)$$, $$(0, 1, b, a)$$, $$(0,0,p,0)$$, and $$(0,0,0,p)$$ with determinant $$p^2$$. Then note that $$x_1^2 + x_2^2 + (x_3p+x_2b-x_1a)^2 + (x_4p + x_2a + x_1b) \equiv (x_1^2+x_2^2)(a^2+b^2+1) \equiv 0 \pmod p$$.
Now consider the open ball $$x_1^2+x_2^2+x_3^2+x_4^2 < 2p$$. Because it has volume $$2 \pi^2 p^2 > 2^4p^2$$, it contains a nonzero point of $$L$$. Then for that point we have $$0<x_1^2+x_2^2+x_3^2+x_4^2<2p$$, so $$x_1^2+x_2^2+x_3^2+x_4^2=p$$.

Theorem 4. A positive integer $$n$$ can be expressed as a sum of three squares if and only if it is not of the form $$4^a(8b+7)$$ for integers $$a$$ and $$b$$.

This fact is much more difficult to prove than the other theorems and will be discussed in the next post.