(iii) a ≡ b (mod p) implies (a | p) = (b | p);

2 ’1)/8

(iv) (2 | p) = (’1)(p ;

(v) if q is an odd prime, then

p’1 q’1

(p | q) = (’1) (q | p).

2 2

Part (v) of this theorem is called the law of quadratic reciprocity.

Note that when p = q, both (p | q) and (q | p) are zero, and so the statement

of part (v) is trivially true ” the interesting case is when p = q, and in this

case, part (v) is equivalent to saying that

p’1 q’1

(p | q)(q | p) = (’1) .

2 2

Part (i) of this theorem follows from Theorem 12.1. Part (ii) is an imme-

diate consequence of part (i), and part (iii) is clear from the de¬nition.

The rest of this section is devoted to a proof of parts (iv) and (v) of this

theorem. The proof is completely elementary, although a bit technical.

Theorem 12.5 (Gauss™ lemma). Let p be an odd prime and let a be an

integer not divisible by p. De¬ne ±j := ja mod p for j = 1, . . . , (p’1)/2, and

let n be the number of indices j for which ±j > p/2. Then (a | p) = (’1)n .

Proof. Let r1 , . . . , rn denote the values ±j that exceed p/2, and let s1 , . . . , sk

denote the remaining values ±j . The ri and si are all distinct and non-zero.

We have 0 < p ’ ri < p/2 for i = 1, . . . , n, and no p ’ ri is an sj ; indeed,

if p ’ ri = sj , then sj ≡ ’ri (mod p), and writing sj = ua mod p and

ri = va mod p, for some u, v = 1, . . . , (p ’ 1)/2, we have ua ≡ ’va (mod p),

which implies u ≡ ’v (mod p), which is impossible.

It follows that the sequence of numbers s1 , . . . , sk , p ’ r1 , . . . , p ’ rn is just

286 Quadratic residues and quadratic reciprocity

a re-ordering of 1, . . . , (p ’ 1)/2. Then we have

((p ’ 1)/2)! ≡ s1 · · · sk (’r1 ) · · · (’rn )

≡ (’1)n s1 · · · sk r1 · · · rn

≡ (’1)n ((p ’ 1)/2)! a(p’1)/2 (mod p),

and canceling the factor ((p ’ 1)/2)!, we obtain a(p’1)/2 ≡ (’1)n (mod p),

and the result follows from the fact that (a | p) ≡ a(p’1)/2 (mod p). 2

Theorem 12.6. If p is an odd prime and gcd(a, 2p) = 1, then (a | p) =

(p’1)/2 2

ja/p . Also, (2 | p) = (’1)(p ’1) /8.

(’1)t where t = j=1

Proof. Let a be an integer not divisible by p, but which may be even, and let

us adopt the same notation as in the statement and proof of Theorem 12.5;

in particular, ±1 , . . . , ±(p’1)/2 , r1 , . . . , rn , and s1 , . . . , sk are as de¬ned there.

Note that ja = p ja/p + ±j , for j = 1, . . . , (p ’ 1)/2, so we have

(p’1)/2 (p’1)/2 n k

ja = p ja/p + rj + sj . (12.1)

j=1 j=1 j=1 j=1

Also, we saw in the proof of Theorem 12.5 that the integers s1 , . . . , sk , p ’

r1 , . . . , p ’ rn are a re-ordering of 1, . . . , (p ’ 1)/2, and hence

(p’1)/2 n k n k

(p ’ rj ) + sj = np ’

j= rj + sj . (12.2)

j=1 j=1 j=1 j=1 j=1

Subtracting (12.2) from (12.1), we get

(p’1)/2 (p’1)/2 n

(a ’ 1) ja/p ’ n + 2

j=p rj . (12.3)

j=1 j=1 j=1

Note that

(p’1)/2

p2 ’ 1

j= , (12.4)

8

j=1

which together with (12.3) implies

(p’1)/2

p2 ’ 1

(a ’ 1) ≡ ja/p ’ n (mod 2). (12.5)

8

j=1

12.3 The Jacobi symbol 287

If a is odd, (12.5) implies

(p’1)/2

n≡ ja/p (mod 2). (12.6)

j=1

If a = 2, then 2j/p = 0 for j = 1, . . . , (p ’ 1)/2, and (12.5) implies

p2 ’ 1

n≡ (mod 2). (12.7)

8

The theorem now follows from (12.6) and (12.7), together with Theo-

rem 12.5. 2

Note that this last theorem proves part (iv) of Theorem 12.4. The next

theorem proves part (v).

Theorem 12.7. If p and q are distinct odd primes, then

p’1 q’1

(p | q)(q | p) = (’1) .

2 2

Proof. Let S be the set of pairs of integers (x, y) with 1 ¤ x ¤ (p ’ 1)/2 and

1 ¤ y ¤ (q ’ 1)/2. Note that S contains no pair (x, y) with qx = py, so let

us partition S into two subsets: S1 contains all pairs (x, y) with qx > py,

and S2 contains all pairs (x, y) with qx < py. Note that (x, y) ∈ S1 if and

(p’1)/2

only if 1 ¤ x ¤ (p ’ 1)/2 and 1 ¤ y ¤ qx/p . So |S1 | = x=1 qx/p .

(q’1)/2

Similarly, |S2 | = y=1 py/q . So we have

(p’1)/2 (q’1)/2

p’1q’1

= |S| = |S1 | + |S2 | = qx/p + py/q ,

2 2

x=1 y=1

and Theorem 12.6 implies

p’1 q’1

.2

(p | q)(q | p) = (’1) 2 2

12.3 The Jacobi symbol

Let a, n be integers, where n is positive and odd, so that n = q1 · · · qk , where

the qi are odd primes, not necessarily distinct. Then the Jacobi symbol

(a | n) is de¬ned as

(a | n) := (a | q1 ) · · · (a | qk ),

where (a | qj ) is the Legendre symbol. Note that (a | 1) = 1 for all a ∈ Z.

Thus, the Jacobi symbol essentially extends the domain of de¬nition of the

Legendre symbol. Note that (a | n) ∈ {0, ±1}, and that (a | n) = 0

288 Quadratic residues and quadratic reciprocity

if and only if gcd(a, n) > 1. Also, note that if a is a quadratic residue

modulo n, then (a | n) = 1; however, (a | n) = 1 does not imply that a

is a quadratic residue modulo n. The following theorem summarizes the

essential properties of the Jacobi symbol.

Theorem 12.8. Let m, n be odd, positive integers, an let a, b be integers.

Then

(i) (ab | n) = (a | n)(b | n);

(ii) (a | mn) = (a | m)(a | n);

(iii) a ≡ b (mod n) implies (a | n) = (b | n);

(iv) (’1 | n) = (’1)(n’1)/2 ;