Notes on Quadratic Reciprocity

Steven J. Miller^{∗} October 2, 2002

Abstract

1 Arithmetic Modulo p

Let ℤ denote the integers, and define ℤ/nℤ = {0, 1, 2, …, n−1}. We often read ℤ/nℤ as the integers modulo n. Definition 1.1 (Congruence) x ≡ y mod n means x − y is a multiple of n. Definition 1.2 (Equivalence Relation) Let R be a binary operation on a set S. We say R is an equivalence relation if the following hold:

1. ∀x ∈ S, R(x, x) is true;

2. ∀x, y ∈ S, R(x, y) is true if and only if R(y, x) is true;

3. ∀x, y, z ∈ S, R(x, y) and R(y, z) true imply R(x, z) is true. Exercise 1.3 1. Let S be any set, and let R(x, y) be x = y. Prove R is an

equivalence.

2. Let S = ℝ and let R(x, y) be x ≤ y. Prove R is an equivalence.

3. Let S = ℤ/nℤ and let R(x, y) be x ≡ y. Prove R is an equivalence.

We define addition by x, y ∈ ℤ/nℤ, then x+y is the unique number z ∈ ℤ/nℤ such that n|(x + y − z). In other words, z is the unique number in ℤ/nℤ such that x + y ≡ z.

ℤ/nℤ is a finite group under addition; in fact, it is a finite ring. Exercise 1.4 Prove we can multiply elements of ℤ/nℤ, and that every non-zero element has a multiplicative inverses if and only if n is prime.

∗E-mail: millerj@cims.nyu.edu or sjmiller@math.princeton.edu

Try and solve in ℤ the equation 2x + 1 = 2y. The left hand side is odd, the right hand side is even. Thus, there are no solutions. Really, what we did above is just arithmetic mod 2 or arithmetic in ℤ/2ℤ.

Now consider a harder problem: x^{2} + y^{2} + z^{2} = 8n + 7. This never has a solution. Look modulo 8. The RHS is 7 modulo 8. What are the squares mod 8? 1^{2} ≡ 1, 2^{2} ≡ 4, 3^{2} ≡ 1, 4^{2} ≡ 0, and then the pattern repeats (as modulo 8, k and (8 − k) have the same square). We see there is no way to add three squares and get 7. Thus, there are no solutions to x^{2} + y^{2} + z^{2} = 8n + 7.

General Idea: First, try and solve the equation modulo different primes. If you cannot solve it for some prime, then you cannot solve it over the integers.

1.1 Group Theory Review

A group G is a set of elements g_{i} satisfying the four conditions below, relative to some binary operation. We often use multiplicative notation (g_{1}g_{2}) or additive notation (g_{1} + g_{2}) to represent the binary operation. For definiteness, we use multiplicative notation below; however, one could replace xy with b(x, y) below.

If the elements of G satisfy the following four properties, then G is a group.

1. (Identity) ∃e ∈ G s.t. ∀g ∈ G : eg = ge = g. We often write e = 1 for multiplicative groups, and e = 0 for additive groups.

2. (Associativity) ∀x, y, z ∈ G : (xy)z = x(yz).

3. (Inverse) ∀x ∈ G, ∃y ∈ G s.t. xy = yx = e. We write y = x^{−1} for multiplication, y = −x for addition.

4. (Closure) ∀x, y ∈ G : xy ∈ G.

If commutation holds (∀x, y ∈ G, xy = yx), we say the group is Abelian. Non-abelian groups exist and are important.

Exercise 1.5 Consider the group of N ×N matrices with real entries and nonzero determinant. Prove this is a group under matrix multiplication, and show this group is not commutative.

H is a subgroup of G if H is a group and its elements form a subset of those of G. The identity of H is the same as the identity of G. Once one has shown the elements of H are closed (ie, under the binary operation, b(x, y) ∈ H if x, y ∈ H), then associativity in H follows from closure in H and associativity in G.

1.2 Algebra Review

Consider arithmetic in the ring ℤ/nℤ.

Definition 1.6 ((ℤ/nℤ)^{∗}) (ℤ/nℤ)^{∗} are the invertible (under multiplication)

elements in the ring ℤ/nℤ; ie, x is in (ℤ/nℤ)^{∗} if there is a y such that xy ≡ 1 mod n.

Note: if gcd(x, n) > 1 (ie, x and n have a common prime divisor p), then you cannot invert x (there is no y with xy ≡ 1 mod n). Why? xy ≡ 1 mod n means xy = 1 + λn for some integer λ. But if p|x and p|n, then p|1 which is absurd.

Exercise 1.7 (Euclidean Algorithm) If gcd(x, n) = 1, there is an multiplicative inverse to x mod n.

The cardinality (number of elements in the set) of (ℤ/nℤ)^{∗} is the number of x ∈ {0, 1, 2, …, n − 1} such that gcd(x, n) = 1. We denote the number of such x by ϕ(x), the Euler totient function. A good reference is H. Davenport, The Higher Arithmetic. Note that if p is prime, ϕ(p) = p − 1. This implies that

|(ℤ/pℤ)^{∗}| = p−1 = ℤ/pℤ−{0}. In other words, we have a field if n is a prime, as every non-zero element is invertible.

(ℤ/nℤ)^{∗}, for any n, is a finite Abelian group (we have inverses under multiplication, and order of multiplication doesn’t matter). Finite Abelian Groups is a trivial subject: the Structure Theorem for Finite Abelian Groups says any such group can be decomposed as a product of cyclic groups.

For n = p a prime, (ℤ/nℤ)^{∗} is a cyclic group of order p − 1.

Definition 1.8 (order) The order of x in a group G, ord(x), is the least positive power m such that x^{m} = e, where e ∈ G is the identity of the group.

Exercise 1.9 Prove that, in a finite group, every element has finite order. Hint: use the pidgeonhole principle.

1.3 Lagrange’s Theorem

Theorem 1.10 (Lagrange) Let H be a sub-group of a finite group G. Then |H| divides |G|. In particular, taking H to be the sub-group generated by x ∈ G, ord(x) | ord(G).

We first prove two useful lemmas.

Lemma 1.11 (Cayley) Let H be a sub-group of G, andlet h ∈ H. Then hH = H.

Proof: by closure hH falls within H. We only need to show that hh_{i} can never equal hh_{j} for two different elements i ≠ j. If hh_{i} = hh_{j}, since a unique h^{−1} exists we could pre-multiply the equation hh_{i} = hh_{j} by h^{−1} to give h_{i} = h_{j}, giving a contradiction. Therefore hh_{i} ≠ hh_{j} if i ≠ j. As H is finite, hH = H. □ Lemma 1.12 Let H be a sub-group of a finite group G. Then either g_{i}H = g_{j}H or the two sets are disjoint.

Proof: assume there is some element in both. Then g_{i}h_{1} = g_{j}h_{2}. Multiplying on the right by h_{i}^{−1} ∈ H (since H is a sub-group) gives g_{i} = g_{j}h_{2}h_{1}^{−1}. As H is a sub-group, ∃h_{3} ∈ H such that h = h_{2}h_{1}^{−1}. Thus g_{i} = g_{j}h_{3}. Therefore, as h_{3}H = H, g_{i}H = g_{j}h_{3}H = g_{j}H, and we see if the two sets have one element in common, they are identical. □

Definition 1.13 (coset) We call a set gH a coset (actually, a left coset) of H.

We now prove Lagrange’s Theorem.

Clearly

G = ⋃_{g∈G} gH  (1.1)

Why do we have an equality? As g ∈ G and H ⊂ G, every set on the right is contained in G. Further, as e ∈ H, given g ∈ G, g ∈ gH. Thus, G is a subset of the right side, proving equality.

There are only finitely many elements in G. As we go through all g in G, we see if the set gH equals one of the sets already in our list (recall we’ve shown two cosets are either identical or disjoint). If the set equals something already on our list, we do not include it; if it is new, we do. Continuing this process, we obtain

G = ⋃_{i=1}^{k} g_{i}H  (1.2)

for some finite k. If H = {e}, k is the number of elements of G; in general, however, k will be smaller.

Each set g_{i}H has |H| elements. Thus, |G| = k|H|, proving |H| divides |G|. Applying Lagrange’s Theorem to (ℤ/pℤ)^{∗} gives

Corollary 1.14 (Fermat’s Little Theorem) For any prime p, if gcd(a, p) = 1, then a^{p−1} ≡ 1 mod p.

Proof: |(ℤ/pℤ)^{∗}| = p − 1.

Exercise 1.15 Prove that if a^{n−1} ≢ 1 mod n then n is composite.

1.4 Legendre Symbol

From now on, p and q will always be odd primes.

Definition 1.16 (Legendre Symbol \binom{\underline{·}}{p}) The Legendre Symbol \binom{\underline{a}}{p} is 1 if a is a non-zero square mod p, 0 if a = 0, and −1 otherwise (ie, if a is not a square mod p).

Note a is a square mod p if there exists an x ∈ {0, 1, …, p − 1} such that a ≡ x^{2} mod p. For p an odd prime, half the non-zero numbers are squares, half are not.

Exercise 1.17 (Euler’s Criterion) \binom{\underline{a}}{p} = a^{\frac{p−1}{2}} mod p for odd p. Hint: a^{\frac{p−1}{2}}

squared is a^{p−1} ≡ 1, so a^{\frac{p−1}{2}} ≡ ±1 mod p.

The Legendre symbol is a function on 𝔽_{p} = ℤ/pℤ. We can extend the Legendre symbol to all integers. We only need to know a mod p, and we define \binom{\underline{a}}{p} = \binom{\underline{a mod p}}{p}.

Initially the Legendre symbol is define only when the bottom is prime. We now extend the definition to all n as follows: let n = p_{1} · p_{2} ⋯ p_{t} be the product of t distinct primes. Then (\frac{a}{n}) = (\frac{a}{p_{1}} ) (\frac{a}{p_{2}} ) ⋯ (\frac{a}{p_{t}} ). Note this is not the same as saying that if a is a square (a quadratic residue) mod n, then a is a square mod p_{i} for each prime divisor.

The main result (which allows us to calculate the Legendre symbol quickly and efficiently) is the celebrated

Theorem 1.18 (Quadratic Reciprocity) For m, n odd and relatively prime, (\frac{m}{n}) (\frac{n}{m}) = (−1)^{\frac{m−1}{2} \frac{n−1}{2}} .

Gauss gave at least four proofs of this deep result. If either p or q is equivalent to 1 mod 4, then one has (\frac{q}{p}) = \binom{\underline{p}}{q}, ie, p is a square root modulo q if and only if q is a square root modulo p.

2 Eisenstein’s Proof of Quadratic Reciprocity

2.1 Preliminaries

Theorem 2.1 (Quadratic Reciprocity) Let p and q be distinct odd primes. Then

(\frac{q}{p}) (\frac{p}{q}) = (−1)^{\frac{p−1}{2} \frac{q−1}{2}} .  (2.3)

As p and q are distinct, odd primes, both (\frac{q}{p}) and (\frac{p}{q}) are ±1. The difficulty is figuring out which signs are correct, and how the two signs are related.

We use Euler’s Criterion, proved previously:

Lemma 2.2 (Euler’s Criterion)

(\frac{q}{p}) ≡ q^{\frac{p−1}{2}} mod p.  (2.4)

The idea behind Eisenstein’s proof is as follows: (\frac{q}{p}) (\frac{p}{q}) is −1 to a power. Further, we only need to determine the power mod 2. Eisenstein shows many expressions are equivalent, mod 2, to this power. Eventually, we arrive at an expression which is trivial to calculate (mod 2).

2.2 First Stage

Consider all even multiples of q by an a ≤ p − 1: {2q, 4q, 6q, …, (p − 1)q}. Denote a generic multiple by aq. Recall [x] is the greatest integer less than or equal to x. By integer division,

aq = [\frac{aq}{p} ]p + r_{a}, 0 ≤ r_{a} < p − 1.  (2.5)

Thus, r_{a} is the least non-negative number equivalent to qa mod p.

The numbers (−1)^{r_{a}}r_{a} are equivalent to even numbers in {0, …, p − 1}. If r_{a} is even this is clear; if r_{a} is odd, then (−1)^{r_{a}}r_{a} ≡ p − r_{a} mod p, and as p and r_{a} are odd, this is even.

Lemma 2.3 If (−1)^{r_{a}}r_{a} ≡ (−1)^{r_{b}}r_{b}, then a = b.

Proof: We quickly get ±r_{a} ≡ r_{b} mod p. If the plus sign holds, then r_{a} ≡ r_{b} mod p implies qa ≡ qb mod p. As q is invertible mod p, we get a ≡ b mod p, which yields a = b (as a and b are even integers between 0 and p − 1).

If the minus sign holds, then r_{a} + r_{b} ≡ 0 mod p, or qa + qb ≡ 0 mod p. Multiplying by q^{−1} mod p now gives a + b ≡ 0 mod p. As a and b are even integers between 0 and p − 1, 0 < a + b ≤ 2(p − 1). The only integer strictly between 0 and 2p which is equivalent to 0 mod p is p; however, p is odd and a+b is even. Thus, the minus sign cannot hold, and the elements are all distinct. □.

Lemma 2.4

(\frac{q}{p}) = (−1)^{∑_{aeven} r_{a}}.  (2.6)

Proof: For each even a, qa ≡ r_{a} mod p. Thus, mod p:

∏_{a even} qa ≡ ∏_{a even} r_{a}
q^{\frac{p−1}{2}} ∏_{a even} a ≡ ∏_{a even} r_{a}

(\frac{q}{p}) ∏_{a even} a ≡ ∏_{a even} r_{a},  (2.7)

where the above follows from the fact that we have \frac{p−1}{2} choices for an even

a (to get q^{\frac{p−1}{2}} and Euler’s Criterion (to replace q^{\frac{p−1}{2}} with (\frac{q}{p})).

As a ranges over all even number from 0 to p − 1, so too do the numbers (−1)^{r_{a}}r_{a} mod p. Thus, mod p,

∏_{a even} a ≡ ∏_{a even}(−1)^{r_{a}}r_{a}
∏_{a even} a = (−1)^{∑_{a even} r_{a}} ∏_{a even} r_{a}.  (2.8)

Combining gives

(\frac{q}{p}) (−1)^{∑_{a even} r_{a}} ∏_{a even} r_{a} ≡ ∏_{a even} r_{a}.  (2.9)

As each r_{a} is invertible mod p, so is the product. Thus,

(\frac{q}{p}) (−1)^{∑_{a even} r_{a}} ≡ 1 mod p.  (2.10)

As (\frac{q}{p}) is its own inverse, the Lemma now follows by multiplying both sides

by (\frac{q}{p}). □.

Therefore, it is sufficient to determine ∑_{a even} r_{a} mod 2. We make one last simplification. By integer division, we have

∑_{a even} qa = ∑_{a even} ([\frac{qa}{p}]p + r_{a})

= ∑_{a even} [\frac{qa}{p}]p + ∑_{a even} r_{a}.  (2.11)

As we are summing over even a, the Left Hand Side above is even. Thus, the Right Hand Side is even, so

∑_{a even} [\frac{qa}{p}]p ≡ ∑_{a even} r_{a} mod 2

p ∑_{a even} [\frac{qa}{p}] ≡ ∑_{a even} r_{a} mod 2

∑_{a even} [\frac{qa}{p}] ≡ ∑_{a even} r_{a} mod 2,  (2.12)

where the last line follows from the fact that p is odd, so mod 2, dropping the factor of p from the Left Hand Side doesn’t change the parity.

We have shown

Lemma 2.5 It is sufficient to calculate ∑_{a even} [\frac{qa}{p}]

2.3 Second Stage

Consider the rectangle with vertices at A = (0, 0), B = (p, 0), C = (p, q) and D = (0, q). The upward slopping vertical is given by the equation y = \frac{q}{p}x. As p and q are distinct odd primes, there are no pairs of integers (x, y) on the line AC.

We now interpret ∑_{a even} [\frac{qa}{p}]. Consider the vertical line with x coordinate

a. Then [\frac{qa}{p}] gives the number of pairs (x, y) with x-coordinate equal to a

and y-coordinate an integer at most [\frac{qa}{p}]. Thus, ∑_{a even} [\frac{qa}{p}] is the number of integer pairs (in the rectangle ABCD) with even x-coordinate that are below the line AC.

We add some additional points: E = (\frac{p}{2}, 0), F = (\frac{p}{2}, \frac{q}{2}), G = (0, \frac{q}{2}) and H = (\frac{p}{2}, q). We prove

Lemma 2.6 The number of integer pairs under the line AC (inside the rectangle) with even x-coordinate is congruent mod 2 to the number of integer pairs under the line AF.

Let a > \frac{p}{2} be an even integer. The integer pairs on the line x = a are (a, 0), (a, 1), …, (a, q). There are q + 1 pairs. As q is odd, there are an even number of integer pairs on the line x = a. As there are no integer pairs on the line AC, for a fixed a > \frac{p}{2}, mod 2 there are the same number of integer pairs above AC as there are below AC.

Further, the number of integer pairs above AC is equivalent mod 2 to the number of integer pairs below AF on the line x = p − a. To see this, consider the map which takes (x, y) to (p − x, q − y). As a > \frac{p}{2} and is even, p − a < \frac{p}{2} and is odd. Further, every odd a < \frac{p}{2} is hit (given a_{odd} < \frac{p}{2}, start with the even number p − a_{odd} > \frac{p}{2}).

Let #F CH_{even} be the number of integer pairs (x, y) in triangle F CH with x even.

Let #EBCH be the number of integer pairs in the rectangle EBCH; #EBCH ≡ 0 mod 2 (we’ve shown each vertical line has an even number of pairs).

Let #AF E_{even} be the number of integer pairs (x, y) in the triangle AF E with x even, and let #AF E be the number of integer pairs in the triangle AF E.

We need to calculate ∑_{a even} [\frac{qa}{p}] mod 2:

∑_{a even} [\frac{qa}{p}] = #AF E_{even} + #EBCH − #F CH
≡ #AF E_{even} + #EBCH + #F CH
= #AF E_{even} + #F CH + #EBCH
= #AF E + #EBCH
= #AF E.  (2.13)

Therefore, μ = ∑_{a even} [\frac{qa}{p}] ≡ #AF E mod 2, and we have

(\frac{q}{p}) = (−1)^{μ}.  (2.14)

Reversing the rolls of p and q, we see that

(\frac{p}{q}) = (−1)^{ν},  (2.15)

where ν ≡ #AF G mod 2, with #AF G equal to the number of integer pairs in the triangle AF G.

Now, μ + ν = #AF E + #AF G, which is the number of integer pairs in the rectangle AEF G. There are \frac{p−1}{2} choices for x and \frac{q−1}{2} choices for y, giving \frac{p−1}{2} \frac{q−1}{2} pairs of integers in the rectangle AEF G.

Thus,

(\frac{q}{p}) (\frac{p}{q}) = (−1)^{μ+ν}
= (−1)^{#AF E+#AF G}
= (−1)^{\frac{p−1}{2} \frac{q−1}{2}} ,  (2.16)

which completes the proof of Quadratic Reciprocity. □.