Quadratic Reciprocity: Gauss's Lemma for Quadratic Residues

In today's blog I continue the proof for the Principle of Quadratic Reciprocity. If you are not familiar with the concepts of quadratic reciprocity, quadratic residues, or the Legendre Symbol start here.

If you would like to start this proof at the beginning, start here.

Today's proof is taken from Gareth A. Jones and J. Mary Jones' Elementary Number Theory.

Definition 1: Congruence Class (mod n)

The set of all numbers that are congruent to each other modulo a value n. This congruence class is represented in brackets such as [0].

NOTE: If you are not familiar with the concept of congruence or modulo, you can review modular arithmetic here.

If we consider n = 3, then we see that:
[1] = { ... ,-2, 1, 4, 7, ... }

since:

-2 ≡ 4 ≡ 7 ≡ 1 (mod 3).

Definition 2: Unit (mod p)

A congruence class [a] is a unit mod p if there exists another congruence class [b] such that ab ≡1 (mod p).

Here are some examples:

1 is a unit mod 8
3 is a unit mod 8 since (3)(3) ≡ 1 (mod 8)
5 is a unit mod 8 since (5)(5) ≡ 1 (mod 8)
7 is a unit mod 8 since (7)(7) ≡ 1 (mod 8)

Lemma 1: Let p be an odd prime. Let P be the set { 1, 2, ... (p-1)/2 }. Let x,y be elements of P.
Then: x ≠ y → x ± y is not congruent to 0.

(1) Assume that x is less than y (otherwise, we can use the same arguments on y)

(2) Case I: x + y

3 ≤ x + y ≤ (p-1)/2 + (p-1)/2 -1 = (p-1)/2 + (p-1-2)/2 = (2p -4)/2 = p-2.

(3) Case II: x-y

-1 ≥ x-y ≥ 1 - (p-1)/2 = (2 - p + 1)/2 = (-p + 3)/2 = -(p-3)/2

(4) Case III: y-x

1 ≤ y - x ≤ (p-1)/2 - 1 = (p-1-2)/2 = (p-3)/2

QED

Lemma 2: Let p be a prime, let a be an integer such that gcd(a,p)=1. Let P be the set { 1, 2, ... (p-1)/2 }. Then:
x ∈ P, y ∈ P, ax ≡ ± ay → x=y

(1) Assume that ax ≡ ± ay (mod p) and x ≠ y.

(2) ax ± ay ≡ 0 (mod p) [See here for a review of modular arithmetic if needed]

(3) So, p divides a(x ± y)

(4) But p doesn't divide a since gcd(a,p) = 1

(5) So, p divides x ± y [By Euclid's Lemma]

(6) So, x ± y ≡ 0 (mod p)

(7) But x ± y is not congruent to 0 (mod p) from Lemma 1 above.

(8) So we have a contradiction and we reject (#1)

QED

Corollary 2.1: If p is an odd prime and P = { 1, 2, ... (p-1)/2 } and gcd(a,p)=1, then there exists ε_i where aP = { (ε₁₎, (ε₂)(2), ... (ε_(p-1)/2)[(p-1)/2] } and each ε_i = +1 or -1.

(1) We know that each element of aP must be in { ±1, ±2, ... ±(p-1)/2 } since:

(a) Let b be any element of P.

(b) We know that ab must fit into one of the following congruence classes [± 1], [± 2], ... [ ±(p-1)/2 ] since ab (mod p) must be between 0 and p-1.

(c) But this means that either it is between 0 and (p-1)/2 or it is between (p-1)/2 + 1 and p - 1.

(d) If it is between 0 and (p-1)/2 then we are done.

(e) If it is between (p-1)/2 + 1 and p-1, then ab (mod p) is between -(p-1)/2 and -1 since p-1 ≡ -1 (mod p) and since [(p-1)/2 + 1] ≡ -(p-1)/2 (Consider that (p-1)/2 + 1 + (p-1)/2 = (p-1+2 +p - 1)/2 = 2p/2 = p.)

(f) But then either way ab is in { ± 1, ± 2, ... ± (p-1)/2 }

(2) We know that aP = { ±1, ±2, ... ±(p-1)/2 } since:

(a) Let's suppose we have b,c such that b,c ∈ P and b ≠ c.

(b) Then, we know that that ab is not congruent to ac from Lemma 2 since it if they were congruent then they must be the same which contradicts our assumption.

QED

Lemma 3: if p is an odd prime and a is a unit mod p, then a^(p-1)/2 ≡ (∏ε_i) (mod p) where ε_i is derived from aP as in Corollary 2.1 above.

(1) We know that aP = { ± 1, ± 2, ... ±(p-1)/2 } where at each point ε_i = 1 or -1 [See corollary 2.1]

(2) (∏ε_i) ≡ [(a*1)(a*2)...(a*(p-1)/2)]/[(1)(2)...(p-1)/2] (mod p)

NOTE: We can make this assumption since multiplication in modular arithmetic is an abelian group. More details here.

(3) Now, be definition of factorial [(p-1)/2]! ≡ (1)(2)...(p-1)/2 [See here for review of factorials]

(4) Likewise (a*1)(a*2)*...*(a*[p-1]/2) ≡ a^(p-1)/2[(p-1)/2]! (mod p)

(5) Combining #2 with #3 and #4 gives us:
(∏ε_i) ≡ a^(p-1)/2[(p-1)/2]!/[(p-1)/2]! = a^(p-1)/2 (mod p)

QED

Lemma 4: Gauss's Lemma for Quadratic Residues

If p is an odd prime and gcd(q,p)=1, then:



where:
μ = the number of elements in qP ∩ N
P = { 1, 2, ... (p-1)/2 }
N = { -1, -2, ... -(p-1)/2 }

(1) Let x,y be elements of P such that x ≠ y.

(2) qx is not congruent to ± qy (mod p) (from Lemma 2 above)

(3) So, we see from (2) that there are (p-1)/2 distinct congruence classes that are created from qP since for each combination, we know from (2), that there is no overlap.

(4) q^(p-1)/2 ≡ (∏ε_i) (mod p) where ε_i = 1 if (i) ∈ P and ε_i = -1 if (i) ∈ N [From Lemma 3 above]

(5) So, q^(p-1)/2 ≡ (-1)^μ (mod p) where μ = the number of elements in qP ∩ N since:

(a) (∏ε_i) = (-1)^μ where μ is the number of times ε_i = -1. [Since we can ignore all the times ε_i = 1]

(b) But this means we need to figure out the count of all elements b ∈ qP that are also in N.

(c) And this means that we are looking for the number of elements in qP ∩ N.

(6) By Euler's Criterion (see here), we know that:


(7) Combining (5) and (6) gives us our conclusion since the Legendre symbol is only = to 1 or -1.


QED