18.781 Solutions to Practice Questions for Midterm 2

18.781 Practice Questions for Midterm 2 Note: The actual exam will be shorter (about 10 of these questions), in case you are timing yourself. 1. Find a primitive root modulo 343 = 73 . Solution: We start with a primitive root modulo 7, for example 3. The proof of existence of primitive roots modulo p2 shows that if g is a primitive root mod p, then there is exactly one value of t mod p such that g + tp is not a primitive root mod p2 , and for this value of t, we will have (g + tp)p−1 ≡ 1 (mod p2 ). So we just compute 36 modulo 49, and see that we get  1 (mod 49). Therefore, 3 is a primitive root modulo 49. Now the proof of existence of 43 ≡ primitive roots modulo pe showed that if we have a primitive root mod p2 , it’s also a primitive root mod pe . So 3 is a primitive root modulo 343 as well. 2. How many solutions are there to x12 ≡ 7 (mod 19)? To x12 ≡ 6 (mod 19)? Solution: In general, if p  a, the number of solutions to xk ≡ a (mod p) can be calculated as  1 (mod p), and there follows. Let d = gcd(k, p − 1). Then there are no solutions if a(p−1)/d ≡ are d solutions if a(p−1)/d ≡ 1 (mod p). To see this, let g be a primitive root mod p. Write a = gb . Then any x solving the congruence equals gm for some m, and then the congruence says gmk ≡ gb (mod p), which is equivalent to mk ≡ b (mod p − 1), since the order of g mod p is p − 1. Now this is just a linear congruence, and it has exactly 0 or d = gcd(k, p − 1) solutions, according to whether d  b or d|b. This latter condition is equivalent to whether or not p − 1 divides (p − 1)b/d, which is equivalent to whether 1 ≡ g(p−1)b/d = a(p−1)/d (mod p). For the given examples, compute 718/6 = 73 ≡ 1 (mod 19), so the first congruence has 6 solutions. On the other hand, 63 ≡ 7 (mod 19), so the second congruence has no solutions. 3. Solve the congruence 3x2 + 4x − 2 ≡ 0 (mod 31). Solution: First, we make the congruence monic by inverting 3 mod 31. Noting that 3 · 10 = 30 ≡ −1 (mod 31), we see that 3−1 = −10. So x2 − 40x + 20 ≡ 0 (mod 31). Next, complete the square to see (x − 20)2 ≡ 202 − 20 = 380 ≡ 8 (mod 31). We need to check whether 8 is a square mod 31 and also to compute a square root if it is. First, check     8 2 = = 1. 31 31 To compute a square root, one can use Tonelli’s algorithm. Here, it’s pretty easy since 31 ≡ 3 (mod 4). So a square root of 8 is 8(31+1)/4 = 88 = 224 ≡ 16 (mod 31). So x ≡ 20 ± 16 (mod 31). i.e x ≡ 4, 5 (mod 31) are the two solutions. 1 4. Characterize all primes p such that 15 is a square modulo p. Solution: Obviously 15 is a square mod 2, 3, 5. So suppose p > 5. We compute the Jacobi symbol      p p 15 3 5 = . = (−1)(p−1)/2 p p p 3 5 So the answer will depend on p modulo 4 · 15 = 60. Looking at the φ(60) = 2 · 2 · 4 = 16 residue classes mod 60, we see that the RHS is +1 exactly when p ≡ ±1, ±7, ±11, ±17  5. If n is odd, evaluate the Jacobi symbol n3 n−2 (mod 60).  . Solution: Using quadratic reciprocity for the Jacobi symbol (noting that one of n and n − 2 must be 1 mod 4, we have  3        n n n−2 −2 = = = n−2 n−2 n n which is 1 when n ≡ 1, 3 (mod 8) and −1 when n ≡ 5, 7 (mod 8). 6. If n = pe11 . . . perr , how many squares modulo n are there? How many quadratic residues modulo n are there (i.e. the squares which are coprime to n)? Solution: For both these questions, we can use the Chinese Remainder theorem. Let’s solve the second question first. If p is an odd prime, then there are (p − 1)/2 quadratic residues mod p. For each such quadratic residue a, Hensel’s lemma can be applied to f (x) = x2 − a to see that a (and anything congruent to a mod pe ) must be a square. Since there are pe−1 such  0 (mod p), we see that the number of quadratic residues mod pe lifts for every choice of a ≡ e−1 e is p (p − 1)/2 = p (1 − 1/p) · 1/2. If p = 2, then we can use the fact that modulo 2, 4, 8 there is exactly one quadratic residue (namely 1), and if a is a square mod 8, then it is a square mod every higher power of 2 (this follows from an extended version of Hensel’s lemma). So the number of quadratic residues mod 2e  is : 1 if e ≤ 3 and 2e−3 if e > 3. Therefore, the number of quadratic residues mod n = 2e pei i is, by CRT, equal to  e −1 pi i (pi − 1)/2. max(1, 2e−3 ) Now for the number of squares mod n. The number of squares will again be a product over all the primes dividing n, of the number of squares mod pei i . Separate out the squares according to what their gcd with pe is; it must be an even power of p. We get the following: if e is even then p−1 p−1 p−1 pe−1 · + pe−3 · + ··· + p · +1 2 2 2 (the last term corresponding to 0 being a square mod pe ). The sum equals pe−1 (p − 1) (1 − p−e ) pe−1 (p − 1) (1 + p−2 + · · · + p−2(e/2−1) ) + 1 = · +1 2 2 1 − p−2 p(pe − 1) p(pe + 1) + 2 = +1= . 2(p + 1) 2(p + 1) 2 Similarly, if e is odd we get pe−1 · p−1 pe+1 + 2p + 1 p−1 p−1 + pe−3 · + ··· + · +1= . 2 2 2 2(p + 1) I’ll leave the calculation for when p = 2 to you. The answer is 2e−1 + 4 if e is even , 3 2e−1 + 5 if e is odd. 3 2 2 7. Let p > 3 be a prime.   Show that the number of solutions (x, y) of the congruence x + y ≡ 3 (mod p) is p − −1 p . 8. The number of solutions is  p−1   3 − x2 x=0 p  2    p−1  p−1    3 − x2 −1 x −3 +1 =p+ =p+ p p p x=0 x=0    p−1  2 −1 x −3 =p+ p p x=0  We showed on homework that for any k,   simplifies to p − −1 p . x2 +k p  = −1. Therefore the expression above 9. Compute (with justification) the cyclotomic polynomial Φ12 (x). Solution: We start with x12 − 1, factoring it and removing any factors that divide xd − 1 for proper divisors d of 12. We have x12 − 1 = (x6 − 1)(x6 + 1) and so we can immediately throw out x6 − 1. Next, x6 + 1 = (x2 + 1)(x4 − x2 + 1) and x2 + 1 is a factor of x4 − 1. So Φ12 (x) must divide x4 − x2 + 1. Now since φ(12) = 4, we see that equality must hold. So Φ12 (x) = x4 − x2 + 1. 10. Let f (n) = (−1)n . Compute Z(f, 2) =  f (n) n≥1 (you may use that n2 . 1/n2 = π 2 /6.) Solution: We want to know the value of S = −1 + 1 1 1 1 − 2 + 2 − 2 + ... 2 2 3 4 5 3 We already know π2 1 1 1 1 = 1 + 2 + 2 + 2 + 2 + ... 3 4 5 6 2 Adding these we get S+   1 1 1 + + + . . . 22 42 62   1 1 1 1 =2· · + + + ... 4 12 22 32 1 π2 =2· · . 4 6 π2 =2 6 Therefore S = −π 2 /12. 11. For n = pe11 . . . perr , calculate the value of (U ∗ U ∗ U )(n), where U is the arithmetic function such that U (n) = 1 for all n. Solution: Since U is multiplicative, so is U ∗ U ∗ U . So enough to calculate it for pe . Then we have   (U ∗ U ∗ U )(pe ) = U (d1 )U (d2 )U (d3 ) = 1 e1 +e2 +e3 =e d1 d2 d3 =pe p, say pei . since di can only be a power of So the value of the function is just the number of nonnegative integer solutions of e1 + e2 + e3 = e. There are many ways to compute this number. One easy way is: if we fix any e1 between 0 and e, the number of possible e2 is e − e1 + 1 (since e2 can range between 0 and e − e1 ) and then e3 is forced to equal e − e1 − e2 . So the total number of solutions is e e e    (e + 1) − e1 = (e + 1)2 − e(e + 1)/2 = (e + 1)(e + 2)/2. (e − e1 + 1) = e1 =0 e1 =0 e1 =0 So for n = pe11 . . . perr , by multiplicativity, we have (U ∗ U ∗ U )(n) = r  (ei + 1)(ei + 2)/2. i=1 12. Let pbe a prime which is 1 mod 4, and suppose p = a2 + b2 with a odd and positive. Show that ap = 1. Solution: We have by Quadratic Reciprocity,      2   2 a p a + b2 b = = = = 1. p a a a  13. Let a1 , a2 , a3 , a4 be integers. Show that the product p = i 3, we have p | ap−1 . Solution: The characteristic polynomial is T 2 − 5T + 6 = (T − 2)(T − 3). So we must have an = A · 3n + B · 2n for some A, B. Plugging in n = 0, 1 we get A = 1, B = −1. So an = 3n − 2n . Now by Fermat, if p > 3 then 2p−1 ≡ 1 ≡ 3p−1 (mod p), so ap−1 ≡ 0 (mod p). 15. Find a positive integer such that μ(n) + μ(n + 1) + μ(n + 2) = 3. Solution: We know μ(n) = ±1 if n is squarefree, and 0 otherwise. The only way we could have the equation holding is if μ(n) = μ(n + 1) = μ(n + 2) = 1. That is, n, n + 1, n + 2 are all squarefree and products of an even number of primes. In particular, n must be 1 mod 4 (else 4 will divide one of these numbers). Trying the first few values, we see that n = 33 is the smallest value which works. 16. Compute the set of integers n for which μ(d)φ(d) = 0. d|n Solution: Since μ(n)φ(n) is a multiplicative function of n, so is  f (n) = μ(d)φ(d). d|n Let’s compute what it is on prime powers. We have f (1) = 1, andfor e ≥ 1, f (pe ) = φ(1) − φ(p) = 2 − p. Therefore, for n = pe11 . . . perr , we have f (n) = (2 − pi ). Therefore f (n) = 0 iff one of the pi is 2, i.e. iff n is even. 17. Let f be a multiplicative function which is not identically zero. Show that f (1) = 1. Solution: We have f (1) = f (12 ) = f (1)f (1), so f (1)(f (1) − 1) = 0. If f (1) =  1, this forces f (1) = 0. Then f (n) = f (n · 1) = f (n)f (1) = f (n) · 0 = 0 for all n, so f is identically 0. We used that 1 is coprime to all integers. 5