The Legendre symbol, three ways
Gauss's count for a
Reduce a, 2a, …, ((p − 1)/2)a mod p and count how many land in the upper half, above p/2. Call the count μ.
μ (upper half)
(−1)μ
(a/p)
Lesson 03 · The multiplicative group · 55–70 minutes
Euler's Criterion and the Legendre Symbol
Half of the units mod p are squares. Lesson 02 identified them as the units of even index. Here that fact becomes a sign, the Legendre symbol (n/p) = ±1, which multiplies like a character and can be computed as a single power, n(p−1)/2 mod p, without finding a primitive root. Then Gauss's lemma, a counting argument with the floor function, decides exactly when −1 and 2 are squares. That picks out the primes used for the rest of the course.
Where this lesson is headed
(np) = (−1)ind n ≡ n(p−1)/2 (mod p), (2p) = 1 ⇔ p ≡ ±1 (mod 8)
In words: being a square is a multiplicative sign, detected by one power. −1 is a square exactly when p ≡ 1 (mod 4), and 2 exactly when p ≡ ±1 (mod 8). The primes p > 5 with p ≡ 5 (mod 8), called P*, have −1 a square but 2 not; they are the primes of Parts III and IV.
You will use
n is a square mod p exactly when ind n is even, and the squares are half the units (Lesson 02, ℓ = 2). g(p−1)/2 ≡ −1 (Lesson 02, step 2). Wilson's theorem is not needed.
p: an odd prime
quadratic residue: a unit n ≡ x2 for some x; otherwise a nonresidue
(n/p): 1 for residues, −1 for nonresidues, 0 if p | n
⌊x⌋: the largest integer ≤ x
⟨m⟩: the remainder of m on division by p, in 0 to p − 1
P*: primes p > 5 with p ≡ 5 (mod 8)
01. Three ways to tell a square
Start with p = 13, the smallest prime of P*. The table computes (n/p) three independent ways: by listing squares, from the index, and by Euler's power n6. Then use Gauss's count on the right to decide whether 2 is a square without computing any powers.
Guided experiments
Do these in order. "Set this up" chooses p and a.
Why the floor function appears
Dividing m by p gives a quotient and a remainder: m = p⌊m/p⌋ + ⟨m⟩, with 0 ≤ ⟨m⟩ ≤ p − 1. Gauss's lemma asks where the remainders ⟨ka⟩ fall, and its proof (and Lesson 10) turns that question into sums of floors.
For negative m, ⌊m/p⌋ rounds down, so the remainder stays in 0 to p − 1: ⟨−1⟩ = p − 1.
02. Euler's criterion and Gauss's lemma
Each step has the general statement on the left and your p and a from Stage 01 on the right.
1
The symbol is a sign, and it multiplies
By Lesson 02 with ℓ = 2 (so d = 2), n is a square exactly when ind n is even, and there are (p − 1)/2 squares. So
(n/p) = (−1)ind n, (ab/p) = (a/p)(b/p)
since ind(ab) ≡ ind a + ind b (mod p − 1) and p − 1 is even. In particular residue × residue and nonresidue × nonresidue are residues; residue × nonresidue is not.
2
Euler's criterion
Write n = gk. Then
n(p−1)/2 = (g(p−1)/2)k ≡ (−1)k = (n/p)
using g(p−1)/2 ≡ −1. So one modular power decides whether n is a square, with no primitive root in sight: n(p−1)/2 reads 1 or p − 1, never anything else.
3
When is −1 a square?
Put n = −1 in Euler's criterion:
(−1/p) = (−1)(p−1)/2
which is 1 exactly when (p − 1)/2 is even, that is p ≡ 1 (mod 4). Lesson 04 uses the square root of −1 this gives.
4
Floors and remainders
For any integer m, m = p⌊m/p⌋ + ⟨m⟩ with 0 ≤ ⟨m⟩ ≤ p − 1. The quotient ⌊m/p⌋ steps up by 1 each time m passes a multiple of p. For a with p ∤ a and 1 ≤ k ≤ (p − 1)/2, ⟨ka⟩ is never 0 and never exactly p/2 (p is odd), so it lies either in the lower half 1 to (p − 1)/2 or the upper half (p + 1)/2 to p − 1.
5
Gauss's lemma
Let μ be the number of k ≤ (p − 1)/2 with ⟨ka⟩ in the upper half. Replace each upper value r by p − r ≡ −r; now every value lies in the lower half. These values are all different: ka ≡ ±k′a would give k ≡ ±k′, impossible for distinct k, k′ in 1 to (p − 1)/2 (their sum and difference are both strictly between 0 and p). So they are 1, 2, …, (p − 1)/2 in some order, and multiplying everything:
a(p−1)/2 · ((p−1)/2)! ≡ (−1)μ · ((p−1)/2)!
Cancel the factorial and use Euler's criterion:
(a/p) = (−1)μ
6
The rule for (2/p)
For a = 2 the multiples 2, 4, …, p − 1 need no reduction. They lie in the upper half when 2k > p/2, that is k > p/4, so
μ = (p − 1)/2 − ⌊p/4⌋
Checking the four classes of p mod 8:
| p | 8m + 1 | 8m + 3 | 8m + 5 | 8m + 7 |
|---|---|---|---|---|
| μ | 2m | 2m + 1 | 2m + 1 | 2m + 2 |
| (2/p) | +1 | −1 | −1 | +1 |
So (2/p) = 1 exactly when p ≡ ±1 (mod 8).
7
The primes P*
For p ≡ 5 (mod 8): p ≡ 1 (mod 4), so −1 is a square; and (2/p) = −1, so 2 is not. Also 4 | p − 1 but 8 ∤ p − 1. The course calls
P* = {p prime : p ≡ 5 (mod 8), p > 5}
(p = 5 is left out because there (p − 1)/4 = 1 and the subgroup of fourth powers used from Lesson 07 on is trivial). These are exactly the primes where, from Lesson 07 on, the quartic character exists, is odd, and can be normalized by its value at 2.
03. The theorem
Assemble the argument, then test it on every prime below 1000.
Theorem. For an odd prime p and p ∤ n: (n/p) ≡ n(p−1)/2 (mod p) and (ab/p) = (a/p)(b/p). Moreover (a/p) = (−1)μ with μ as in Gauss's lemma, (−1/p) = (−1)(p−1)/2, and (2/p) = (−1)(p²−1)/8, which is 1 exactly when p ≡ ±1 (mod 8).
Complete proof
Symbol and Euler. The squares are the units of even index (Lesson 02), so (n/p) = (−1)ind n, which is multiplicative because p − 1 is even. With n = gk, n(p−1)/2 ≡ (g(p−1)/2)k ≡ (−1)k. Taking n = −1 gives (−1/p) = (−1)(p−1)/2.
Gauss's lemma. For 1 ≤ k ≤ (p − 1)/2 let rk = ⟨ka⟩ if it is at most (p − 1)/2, and p − ⟨ka⟩ otherwise; μ of them needed the second case. The rk are distinct, since rk = rk′ gives ka ≡ ±k′a, so p | k ∓ k′, impossible. Hence {rk} = {1, …, (p − 1)/2}, and multiplying the congruences ka ≡ ±rk gives a(p−1)/2((p − 1)/2)! ≡ (−1)μ((p − 1)/2)!. Cancel and apply Euler.
(2/p). For a = 2 no reduction occurs, and 2k is in the upper half iff k > p/4, so μ = (p − 1)/2 − ⌊p/4⌋. Checking p = 8m + 1, 3, 5, 7 gives μ = 2m, 2m + 1, 2m + 1, 2m + 2, so (2/p) = 1 iff p ≡ ±1 (mod 8); equivalently (2/p) = (−1)(p²−1)/8. ∎
Computer check
For every odd prime below 1000 and every unit n: compares (n/p) from the list of squares with n(p−1)/2 and with Gauss's count; checks multiplicativity on a sample; checks the rules for (−1/p) and (2/p); and counts the primes of P* below 1000.
Not run yet.
Exit problem
Use p = 29. Enter symbols as 1 or −1.
Extension · quadratic reciprocity
For distinct odd primes p and q, (p/q)(q/p) = (−1)((p−1)/2)((q−1)/2). Gauss's lemma plus a count of lattice points under a line proves it; the rule for (2/p) above is its companion. The rest of the course does not use it, but it is worth knowing. Try some pairs: