Quadratic Residues, Quadratic Reciprocity

Lecture 9 Quadratic Residues, Quadratic Reciprocity Quadratic Congruence - Consider congruence ax2 + bx + c ≡ 0 mod p, with a 6= 0 mod p. This can be reduced to x2 + ax + b ≡ 0, if we assume that p is odd (2 is trivial case). We can now complete the square to get a 2 a2 +b− ≡ 0 mod p 2 4 So we may as well start with x2 ≡ a mod p  x+ If a ≡ 0 mod p, then x ≡ 0 is the only solution. Otherwise, there are either no solutions, or exactly two solutions (if b2 ≡ a mod p, then x = ±b mod p). (x2 ≡ a ≡ b2 mod p ⇒ p|x2 − b2 ⇒ p|(x − b)(x + b) ⇒ x ≡ b or −b mod p). We want to know when there are 0 or 2 solutions. (Definition) Quadratic Residue: Let p be an odd prime, a 6≡ 0 mod p. We say that a is a quadratic residue mod p if a is a square mod p (it is a quadratic non-residue otherwise). Lemma 39. Let a 6≡ 0 mod p. Then a is a quadratic residuemod p iff a mod p p−1 2 ≡ 1 Proof. By FLT, ap−1 ≡ 1 mod p and p − 1 is even. This follows from index calculus. Alternatively, let’s see it directly  a p−1 2 2 ≡1 mod p ⇒ a p−1 2 ≡ ±1 mod p Let g be a primitive root mod p. {1, g, g 2 . . . g p−2 } = {1, 2, . . . p − 1} mod p. Then a ≡ g k mod p for some k. With that a = g k+(p−1)m mod p so k’s only defined mod p − 1. In particular, since p − 1 is even, so we know k is even or odd doesn’t depend on whether we shift by a multiple of p − 1. (ie., k is well defined mod 2). We know that a is quadratic residue mod p iff k is even (if k = 2l then a ≡ g 2l ≡ (g l )2 mod p). Conversely if a ≡ b2 mod p and b = g l mod p we get a ≡ g 2l mod p, so k is even. Note: this shows that half of residue class mod p are quadratic residues, and
p−1 k(p−1) p−1 half are quadratic nonresidues. Now look at a 2 ≡ g k 2 ≡ g 2 mod p. k(p−1) k(p−1) k ≡ 1 mod p iff p − 1 = ordp g divides 2 iff (p − 1)| 2 ↔ 2|k ↔ a is a quadratic residue.  1 (Definition) Legendre Symbol:   ( 1 if a is a quadratic residue mod p a = p −1 if a is a quadratic non-residue mod p Defined for odd prime p, when (a, p) = 1. (For convenience and clarity, written (a|p)). p−1 We just showed that (a|p) ≡ a 2 mod p. Remark 1. This formula shows us that (a|p)(b|p) = (ab|p). LHS ≡ a p−1 2 b p−1 2 ≡ (ab) p−1 2 mod p ≡ RHS mod p and since both sides are ±1 mod p, which is an odd prime, they must be equal Similarly, (a2 |p) = (a|p)2 = 1 Eg. (−4|79) = (−1 · 22 |79) = (−1|79)(2|79)2 = (−1|79) = (−1)39 = −1 Also, 79 is not 1 mod 4 so −1 is quadratic non-residue. We’ll work toward quadratic reciprocity relating (p|q) to (q|p). We’ll do Gauss’s 3rd proof. Lemma 40 (Gauss Lemma). Let p be an odd prime, and a 6≡ 0 mod p. For any integer x, let xp be the residue of x mod p which has the smallest absolute value. (Divide x by p, get some remainder 0 ≤ b < p. If b > p2 , let xp = b, if b > p p p 2 , let xp be b − p. ie., − 2 < xp < 2 ) Let n be the number of integers among p−1 (a)p , (2a)p , (3a)p . . . (( 2 )a)p which are negative. Then (a|p) = (−1)n . Proof. (Similar to proof of Fermat’s little Theorem) We claim first that if 1 ≤ k 6= l ≤ (ka)p = ±(la)p . Then, we’d have p−1 2 then (ka)p 6= ±(la)p . Suppose not true: ka ≡ ±la mod p ⇒ (k ∓ l)a ≡ 0 mod p ⇒ k ∓ l ≡ 0 This is impossible because 2 ≤ k + l ≤ p − 1 and − p2 < k − l < (no multiple of p possible). mod p p 2 and k − l 6= 0 1 So the numbers |(ka)p | for k = 1 . . . p− 2 are all distinct mod p (there’s 2 p−1 2 of them) and so must be the integers {1, 3 . . . p−1 2 } in some order. p−1  1 · 2 · ··· · p−1 2  ≡ 2 Y |(ka)p | mod p k=1 p−1 ≡ (−1)n 2 Y (ka)p mod p k=1 p−1 n ≡ (−1) 2 Y ka mod p k=1 ≡a ⇒1≡a p−1 2 p−1 2    p−1 (−1)n 1 · 2 · · · · · 2 (−1)n mod p mod p p−1 2 a ≡ (−1)n mod p (a|p) ≡ (−1)n mod p (a|p) = (−1)n since p > 2 where the second step follows from the fact that exactly n of the numbers (ka)p are < 0.  and (a, p) = 1, then if a is odd, we have (a|b) = Theorem 41. If p is an oddj prime, P(p−1)/2 ja k t (p2 −1)/8 (−1) where t = j=1 p . Also, (2|p) = (−1) Proof. We’ll use the Gauss Lemma. Note that we’re only interested in (−1)n . We only care about n mod 2. We have, for every k between 1 and p−1 2 (  0 if (ka)p > 0 ka ka = p + (ka)p + p p if (ka)p < 0 (   0 if (ka)p > 0 ka ≡ + |(ka)p | + p 1 if (ka)p < 0  Sum all of these congruences mod 2 3 mod 2 (p−1)/2 X (p−1)/2  X ka ≡ k=1 k=1 k=1 (p−1)/2 (p−1)/2 X X ka = a  (p−1)/2 X ka + |(ka)p | + n mod 2 p k k=1 k=1    p−1 p−1 1 a +1 2 2 2 2 a(p − 1) = 8 = Now P p−1 |(a)p |. Since {|a|p , . . . , | p−1 2 a|p } is just {1 . . . 2 }, (p−1)/2 (p−1)/2 X X |(ka)p | = k=1 k k=1    1 p−1 p−1 2 2 2 p−1 = 8 = Plug in to get  n≡a p2 − 1 8  ≡ (a − 1) If a is odd, we have get p2 −1 8   − p2 − 1 8 p2 − 1 8 (p−1)/2   + X k=1 ka p  mod 2 (p−1)/2  + X (ka|p) mod 2 k=1 is integer and a − 1 is even, so product ≡ 0 mod 2, to (p−1)/2  n≡ X k=1 ka p  mod 2 ≡ t mod 2 So (a|p) = (−1)n = (−1)t When a = 2,  (p−1)/2  X p2 − 1 2k n≡ + 8 p k=1 4 mod 2 So, note that for k ∈ {1 . . . p−1 2 } 2 ≤ 2k ≤ p − 1 so 0< 2 2k p−1 ≤ ≤ <1 p p p so b so 2k c=0 p (p−1)/2 X (2k |p) = 0 k=1 so n≡ p2 − 1 8 mod 2 and (2|p) = (−1)n = (−1) p2 −1 8 So far, (−1|p) = (−1) p−1 2 Check (2|p) = (−1) p2 −1 8 ( 1 if p = 1 mod 4 = −1 if p = 3 mod 4 ( 1 if p = 1, 7 = −1 if p = 3, 5 mod 8 mod 4  Theorem 42 (Quadratic Reciprocity Law). If p, q are distinct odd primes, then ( p−1 q−1 1 if p or q ≡ 1 mod 4 2 2 (p|q)(q|p) = (−1) = −1 otherwise Proof. Consider the right angled triangle with vertices (0, 0), ( p2 , 0), ( p2 , 2q ). Note that: no integer points on vertical side, no nonzero integer points on hypotenuse (slope is pq , so if we had integer point (a, b) then ab = pq ⇒ pb = qa, so p|a, q|b, and if (a, b) 6= (0, 0), then a ≥ p, b ≥ q). Ignore the ones on horizontal side. Claim: the number of integer points on interior of triangle is (p−1)/2  X k=1 5 qk p  q qk l Proof. If we have a point (k, l), then 1 ≤ k ≤ p−1 2 and slope k < p ⇒ l < p . Number j k of points on the segment x = k is the number of possible l, which is just qk p .  Add these (take triangle, rotate, add to make rectangle) - adding points in interior of rectangle is (p−1)/2  X l=1  (pX     −1)/2  pl qk p−1 q−1 + = q p 2 2 k=1 t1 (q|p) = (−1) where t1 = (p|q) = (−1)t2 where t2 = X  qk  p X  pl  q (p|q)(q|p) = (−1)t1 +t2 where t1 + t2 = total number of points  6