MATH 261 Midterm, Fall 2001

Math 261 — Fall 2001–2002 Solutions to Midterm Quiz 1. Find the prime factorizations of 8536 and 7007, and use these to calculate ϕ(7007) and the GCD (8536, 7007). Answer. 8536 = 23 · 11 · 97, where 97 is prime since it is not divisible by any prime less than √ 97 ≈ 10. Also 7007 = 72 · 11 · 13. We use this to conclude that ϕ(7007) = (72 − 7)(11 − 1)(13 − 1) = 5040, and that (8536, 7007) = 11. 2. Calculate � 3 11 � in two ways, first by Euler’s criterion, and second by Gauss’ Lemma (not by quadratic reciprocity). Answer. Note that (11 − 1)/2 = 5. Then Euler’s criterion gives � 3 11 � ≡ 35 ≡ 243 ≡ +1 (mod 11). For Gauss’ Lemma, we look at 3 · 1 ≡ 3, 3 · 2 ≡ −5, 3 · 3 ≡ −2, 3 · 4 ≡ 1, and 3 · 5 ≡ 4 (mod 11). Here we reduce to a residue mod 11 that is between ±5. There are two minus signs (−5 and −2), so the quadratic residue is (−1)2 = +1. 3. Find one solution to the equation x2 ≡ 5 (mod 112). (You do not need to find the most general solution.) Answer. If x2 ≡ 5 (mod 112), then certainly x2 ≡ 5 (mod 11). So we can start with x0 = 4 (found by trial and error), which certainly satisfies x2 0 ≡ 5 (mod 11). We then try x = x0 + 11k = 4 + 11k, where we only care about k mod 11. Now (4 + 11k)2 = 16 + 88k + 112k2 ≡ 16 + 88k (mod 112), so we must solve the equation 16 + 88k ≡ 5 (mod 112). Equivalently, 88k ≡ −11 (mod 112) ⇐⇒ 8k ≡ −1 (mod 11) ⇐⇒ k ≡ −7 ≡ 4 (mod 11). (Note that the last step follows by noting that 7 is the inverse of 8 mod 11. This can be found by trial and error or by the Euclidean algorithm.) Anyhow we obtain x = 4 + 11 · 4 = 48 as a solution. (Alternatively, if we start from x1 = 7, we obtain another root 73 (mod 112). Note that 73 ≡ −48 (mod 112).) 4. Show that every number a has a unique cube root x modulo 101. (For example, the number 14 has the cube root 6, since 63 = 216 ≡ 14 (mod 101). I am asking you to show both existence and uniqueness of the cube root for any a, not just for 14.) Answer. Note that 101 is a prime number. In case a ≡ 0 (mod 101), then the only solution is x ≡ 0. Otherwise, if a ̸≡ 0 (mod 101), then let g be a primitive root mod 101, and write a ≡ gb (mod 101) for some b which is only determined modulo 100. We are looking for an x ̸≡ 0 (mod 101), so we can write x ≡ gy (mod 101), where y is our “unknown” that is determined modulo 100. Then x3 ≡ a (mod 101) ⇐⇒ g3y ≡ gb (mod 101) ⇐⇒ 3y ≡ b (mod 100). This last equation has a unique solution for y mod 100, since 3 is invertible modulo 100 [why?]. Once we know y, we then obtain a unique x. 5. Using the Chinese Remainder Theorem, find one solution x to the equation x2 ≡ 1 (mod 91) with x ̸≡ ±1 (mod 91). (Again, you do not need to find the most general x of this form. It may help you to notice that 91 = 7 · 13.) 1 Answer. We want x2 ≡ 1 modulo each of the primes 7 and 13, so by an argument from class we see that x ≡ ±1 modulo each of 7 or 13. To ensure that x ̸≡ ±1 (mod 91), we take a different choice modulo each prime: x ≡ +1 (mod 7), x ≡ −1 (mod 13). (∗) This can be solved by the Chinese Remainder Theorem. Explicitly, we see that x = 13k−1 but x ≡ 1 (mod 7), so we obtain 13k − 1 ≡ 1 (mod 7), which we solve to obtain k ≡ −2 ≡ 5 (mod 7). This yields x ≡ 13 · 5 − 1 ≡ 64 (mod 91). (One can alternatively solve the opposite system from (∗), and obtain the other solution x ≡ 27 (mod 91).) 6. Let p be a prime dividing 1032 + 1. Show that p ≡ 1 (mod 64). Hint: what is the order of 10 modulo p? Answer. We know that 1032 + 1 ≡ 0 (mod p), so we obtain 1032 ≡ −1 (mod p), and also 1064 ≡ (1032)2 ≡ +1 (mod p). So the order of 10 modulo p is a factor of 64 but not a factor of 32, so the order of 10 is exactly 64. But we know by the little Fermat theorem that 10p−1 ≡ 1 (mod p), so the order of 10 is a factor of p − 1. This implies 64|p − 1, so p ≡ 1 (mod 64). Note: 1032 + 1 = 19841 · 976193 · 6187457 · 834427406578561. Also note that we used implicitly the fact that −1 ̸≡ 1 (mod p). This is okay, since 1032 + 1 is odd, so p ̸= 2. 7. In this question, p is a prime with p ̸= 2, 3. Even if you cannot prove every part of this problem, you may assume the result of a previous part in all subsequent parts. a) Show that p ≡ ±1 (mod 6). b) Show that � −3 p � = � p 3 � . c) Conclude that −3 is a quadratic residue modulo p if and only if p ≡ 1 (mod 6). d) Show that there exist infinitely many primes of the form 6k + 1. Answer. a) p is odd, so p ≡ 1, 3, or 5 (mod 6). But p is not divisible by 3, so the only choices are p ≡ 1 or 5 (mod 6). b) Case I: p ≡ 1 (mod 4), in which case � −3 p � = � −1 p �� 3 p � = (+1) � p 3 � . Case II: p ≡ 3 (mod 4), in which case � −3 p � = � −1 p �� 3 p � = (−1)(− � p 3 � ) = + � p 3 � . c) −3 is a quadratic residue ⇐⇒ � −3 p � = 1 ⇐⇒ � p 3 � = 1 ⇐⇒ p ≡ 1 (mod 3) ⇐⇒ p ≡ 1 (mod 6). The last equivalence is because the only choices of p modulo 6 are ±1, and this determines the residue of p modulo 3. d) Assume p1, p2, . . . , pr are the only primes congruent to 1 (mod 6). Form the number N = 4(p1p2 · · · pr)2+3. It is easy to see that N is not divisible by any of the primes 2, 3, p1, p2, . . . , pr. So N is divisible by some other prime q. However, N ≡ 0 (mod q) means that 4(p1p2 · · · pr)2+3 ≡ 0 (mod q), which means that the number a = 2p1p2 · · · pr satisfies a2 ≡ −3 (mod q). Thus by part (c), q ≡ 1 (mod 6), and we have located a new prime of the form 6k + 1; contradiction. Thus there are infinitely many such primes. Note: you can instead use the choice N = 12(p1p2 · · · pr)2 + 1. Do you see why? 2