18.781 Solutions to Problem Set 5

18.781 Solutions to Problem Set 5 1. Note that 41 − 1 = 23 · 5. Start with a quadratic nonresidue mod 41, say, 3. Now b = 35 = 81 · 3 ≡ −3 (mod 41), which has order exactly 8. (−3)−1 ≡ −14 (mod 41). Now we calculate a square root of 21. First, check that 21 is a square: 21(41−1)/2 = 2120 = 320 · 720 ≡ −1 · 720 ≡ −1 · 4910 ≡ −1 · 810 ≡ −230 ≡ −220 · 210 ≡ −1 · 1024 ≡ 1 (mod 41). Next, calculate 2110 ≡ 4415 ≡ (−10)5 ≡ 18 · 18 · (−10) ≡ 324 · (−10) ≡ (−8)(−10) ≡ −1 (mod 41). So update A = (21)/(−3)2 ≡ 21 · 142 = 21 · 196 ≡ 21 · (−9) ≡ 16 (mod 41). Next, since 165 ≡ 220 ≡ 1 (mod 41), there is no need to modify A and b for this step. We’re at the stage where Aodd ≡ 1 (mod 41), so a square root of A is A(5+1)/2 = 163 ≡ −4 (mod 41). (Note: we could have guessed a square root of 16 anyway since it’s a perfect square.) Thus, a square root of 21 is given by (−3)(−4) ≡ 12 (mod 41). Check: 122 = 144 ≡ 21 (mod 41). The other square root of 21 mod 41 is -12. 2. First, observe that (2p − 1)/3 is an integer, and that by Fermat’s Little Theorem  3 a(2p−1)/3 = a2p−1 = a(ap−1 )2 ≡ a (mod p). Since 3 and p − 1 are coprime, this is the unique cube root of a. 3. (a) Since p - a, we complete the square:   b c ax2 + bx + c = a x2 + x + a a !  2 b c b2 =a x+ + − 2 2a a 4a " # 2 b (b2 − 4ac) =a x+ − 2a 4a2 = 1 [(2ax + b)2 − (b2 − 4ac)]. 4a 1 Letting y = 2ax + b, the congruence f (x) ≡ 0 (mod p) is equivalent to y 2 ≡ D (mod p). If p|D then obviously y ≡ 0 is the only solution, and thus x ≡ −b/2a. Else, if p - D, then there are either 0 or 2 solutions depending on whether D is or is not a square mod p. Finally, f 0 (x0 ) = 2ax0 +b = y0 must be nonzero mod p because its square D is nonzero. (b) By part (a), x2 ≡ a (mod p) has exactly 1 + ( ap ) solutions mod p. Since f (x) = x2 − a satisfies the criterion of Hensel’s Lemma, every solution mod p lifts to a unique solution mod pe . Hence, the number of solutions mod pe is 1 + ( ap ) as well. 4. We use the Chinese Remainder Theorem to decompose each congruence into a system of congruences with factors of the modulus. (a) We have 118 = 2 · 59. Now the congruence x2 ≡ −2 ≡ 0 (mod 2) has a unique solution, and x2 ≡ −2 (mod 59) has two solutions because      −2 −1 2 = = (−1) · (−1) = 1. 59 59 59 Therefore there are two solutions to the original congruence. (b) The congruence x2 ≡ −1 (mod 4) has no solutions, so there are no solutions. (c) We have 365 = 5 · 73. There are two solutions to each of the congruences x2 ≡ −1 (mod 5) and x2 ≡ −1 (mod 73), so there are 2 · 2 = 4 solutions. (d) Since 227 is prime, we use quadratic reciprocity:       7 227 3 =− =− = −(−1) = 1. 227 7 7 So there are two solutions. (e) We have 789 = 3 · 263. The first congruence, x2 = 267 ≡ 0 (mod 3), has exactly one solution. The second, x2 = 267 ≡ 4 (mod 263), has two solutions. Thus there are two solutions. 5. Assume p is odd, since if p = 2 this is obvious. If we let x = g k , where g is a primitive root mod p, then we have g 8k ≡ 16 (mod p). This equation has a solution if and only if 1 ≡ 16(p−1)/ gcd(8,p−1) = 24(p−1)/ gcd(8,p−1) (mod p). Now if 8 - p − 1, then gcd(8, p − 1) is 2 or 4. It follows that 4(p − 1)/ gcd(8, p − 1) is a multiple of p − 1, so 24(p−1)/ gcd(8,p−1) ≡ 1 (mod p) by Fermat. On the other hand, if 8|p − 1, then 2 is a quadratic residue mod p, and thus 24(p−1)/ gcd(8,p−1) = 2(p−1)/2 ≡ 1 (mod p). 6. We will argue by contradiction, as in Euclid’s proof. Suppose there are only finitely many such primes, say, p1 , . . . , pn . Let N = (p1 · · · pn )2 − 2. First, note that N is odd becauase the pi are all odd. Also, since p1 = 7, we have N ≥ 72 − 2 > 1. Finally, since odd2 ≡ 1 (mod 8), N ≡ 1 − 2 ≡ 7 (mod 8). 2 Now  N  is divisible only by odd primes, and if p is a prime dividing N then (p1 · · · pn ) ≡ 2 (mod p), so p2 = 1. Thus p ≡ ±1 (mod 8). But not all the primes dividing N can be congruent to 1 mod 8, as that would force N ≡ 1 (mod 8), so there exists some prime p | N congruent to 7 mod 8. However, p cannot be one of the pi , because (pi , N ) = (pi , (p1 · · · pN )2 − 2) = (pi , 2) = 1. Contradiction. 2 7. Obviously we need p = 6 2, 5. Then, by quadratic reciprocity,         10 2 5 2 p = = . p p p p 5 We have and   ( +1 if p ≡ ±1 (mod 8) 2 = p −1 if p ≡ ±3 (mod 8) ( +1 if p ≡ ±3 (mod 8) = 5 −1 if p ≡ ±2 (mod 5). p So the product will depend on p mod 40. By direct calculation,    ( +1 if p ≡ ±1, ±3, ±9, ±13 (mod 40) 2 p = p 5 −1 if p ≡ ±7, ±11, ±17, ±19 (mod 40). 8. (a) Clearly we need p = 6 3, and everything is a square mod 2, so let’s restrict our attention to primes greater than 3. Then, by quadratic reciprocity,      −3 −1 3 ≡ p p p p p−1 3−1 p−1 = (−1) 2 (−1) 2 · 2 3 p = (3 +1 if p ≡ 1 (mod 3) = −1 if p ≡ −1 (mod 3). So −3 is a quadratic residue mod p if and only if p = 2 or p ≡ 1 (mod 3). (b) For primes of the form 3k − 1: Suppose there are finitely many, say, p1 , p2 , . . . , pn with p1 = 2. Then we let N = 3p1 · · · pn − 1 and argue as in Euclid’s proof. Since N ≡ −1 (mod 3) and N is odd, N must be divisible by some odd prime equivalent to −1 (mod 3). For primes of the form 3k + 1: Now we use N = (2p1 · · · pn )2 + 3. Then N is odd, and if p|N , then −3 ≡ (2p1 · · · pn )2 (mod p) so −3 is a quadratic residue mod p. This implies that p ≡ 1 (mod 3), and again a Euclid-style proof finishes the argument. 9. (a) The congruence y 2 ≡ x2 + k (mod p) is equivalent to (y − x)(y + x) ≡ k (mod p). Let z = y − x, w = y + x. Note that since p is odd, we can invert this system to solve for x, y: ( x ≡ w−z (mod p) 2 w+z y≡ 2 (mod p). So the number of solutions to y 2 ≡ x2 + k (mod p) is the same as the number of solutions to zw ≡ k (mod p). Now we can choose any nonzero value for z and let w = k/z. Therefore there are exactly p − 1 solutions. 2 (b) The number of solutions to y 2 ≡ x2 + k, for a fixed value of x, is 1 + ( x p+k ). So p−1= p  X x=1  1+ x2 + k p  =p+  p  2 X x +k x=1 Thus, X  x2 + k  p 3 = −1. p . (c) The number of solutions to ax2 + by 2 ≡ 1 (mod p) is   p  X X  (1 − ax2 )/b  (1 − ax2 )/b 1+ =p+ p p x=1 X  1 − ax2   b−1  =p+ p p X  1 − ax2   b  =p+ p p X  x2 − 1/a   −a   b  =p+ p p p   X 2  −ab x − a−1 =p+ · p p   −ab =p− , p where the last equality follows from part (a). 10. You should observe that for primes congruent to 1 mod 4, R = N , whereas for primes congruent to 3 mod 4, R > N . When p ≡ 1 (mod 4), R = N follows easily from observing that if x is a quadratic p−1 residue then so is p − x, so the number of quadratic residues in {1, . . . , p−1 2 } must be 4 , exactly half of the total number of quadratic residues. When p ≡ 3 (mod 4), no elementary proof that R > N is known. (The known proof uses L-functions and Dirichlet’s class number formula.) 11. First, it’s easy to see that all the quadratic residues must lie in S1 , because for all x ∈ {1, . . . , p − 1}, x lies in the same set as itself, so x2 lies in S1 . Since S2 is nonempty it must contain some quadratic nonresidue u (mod p). Moreover, the p−1 2 elements in the set {ur : r a quadratic residue} must all lie in S2 because u ∈ S2 and r ∈ S1 . We’ve now exhausted all the nonzero residue classes of p, so S1 contains all the residues and S2 all the nonresidues. 12. (a) Note that πsi (i) = π(si (i)) = π(i + 1), πsi (i + 1) = π(si (i + 1)) = π(i), and for j = 6 i, i + 1 we have πsi (j) = π(si (j)) = π(j). Now if j, k 6∈ {i, i + 1} then π(j) = πsi (j) and π(k) = πsi (k) so (j, k) is an inversion of π if and only if it is an inversion of πsi . So the changes in inversions happen in one of the following three cases: Case I: (i, i + 1) Case II: (j, i) or (j, i + 1), where j < i Case III: (i, k) or (i + 1, k), where k > i + 1. Now for case II, we see that (j, i) is an inversion of π if and only if (j, i + 1) is an inversion of πsi , and (j, i + 1) is an inversion of π if and only if (j, i) is an inversion of πsi . So the total number of inversions in case II doesn’t change between π and πsi . Similarly, the total number of inversions doesn’t change in Case III. Case I only involves one pair (i, i + 1), and thus the number of inversions changes by exactly ±1. (b) We use proof by induction on the number of inversions in the permutation π. If π has no inversions then π must be the identity, and is thus an empty product of transpositions. So assume π has k inversions, and we’ve proved the result for all permutations with fewer than k inversions. Let (i, i + 1) be an inversion of π. Then πsi has one fewer inversion, so by the inductive hypothesis, πsi = sj1 sj2 · · · sjr is a product of transpositions. Since s2i = 1, we have that π = πs2i = sj1 · · · sjr si is also a product of transpositions, completing the induction. (c) It’s enough to show that sign(πsi ) = sign(π)sign(si ) for any transposition si and permutation π. Once we do this, it follows by induction that sign(si1 · · · sir ) = sign(si1 ) · · · sign(sir ) = (−1)r , so if π = si1 · · · sir and σ = sj1 · · · sjt , then π ◦ σ = si1 · · · sir sj1 · · · sjt and hence sign(π ◦ σ) = (−1)r+t = sign(π)sign(σ). 4 Now by part (a), the number of inversions of πsi is the number of inversions of π plus or minus 1. So if we define f (ρ) to be the number of inversions of a permutation ρ, then sign(πsi ) = (−1)f (πsi ) = (−1)f (π) (−1)±1 = sign(π)sign(si ). (d) The proof is by induction on k. For the base case k = 2, we have the transposition π = (ab) where we can assume without loss of generality that a < b. Now the number of inversions is 2(b − a − 1) + 1, which is odd, so sign(π) = −1 = (−1)2−1 . Next, consider an arbitrary k-cycle π = (a1 · · · ak ). Since π = (a1 · · · ak−1 )(ak−1 ak ), by the inductive hypothesis sign(π) = (−1)k−2 (−1) = (−1)k−1 . This completes the induction. Therefore, for a disjoint product of cycles, the sign is (−1)m , where m is the number of even-length cycles. 5