Many Proofs 1: Quadratic Reciprocity

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 $$

Leave a Reply

Your email address will not be published. Required fields are marked *