Please show all steps and reasoning. Urgent. Due tomorrow midnight.
Math 463 Final Prof. Jerry Rosen Spring 2021 Instructions: Answer all 8 questions and submit your answers in a single PDF. This is an open book/open notes exam, but absolutely no internet sources! You can assume the results for the Legendre symbols ( a p ) for a = −1, 2, 3, 5, if necessary. 1. (12 pts) Determine the primes p > 5 for which −5 is a quadratic residue modp (see exercise 10.8.23) 2. (12 pts) Suppose p is an odd prime and assume that q = 4p + 1 is also prime. Prove that 2 must be a primitive root modq as follows: (a) What must the order of 2 be modq to be a primitive root? (b) Use Fermat’s Theorem to explain why the possible orders of 2modq must be one of 2, 4, p, 2p, 4p (c) Use Euler’s Criterion to rule out 2, p, 2p (d) Also rule out 4 (e) Make the conclusion 3. (12 pts) Consider the equation x4 ≡ 16mod17 Explain why this equation must have four distinct solutions without using an explicit primitive root. Use g for the primitive root (HINT: what is 16 congruent to mod17?) 4. (14 pts) Show all work in solving the following. No credit for guessing! (a) Consider 4x2−12x+7 ≡ 0mod31. Does this equation have solutions mod31? If so, explain and find them. If not, why? (b) Consider 3x2 − 19y = 1. Does this equation have integer solutions? If so, explain and find them. If not, why? 5. (10 pts) Let n > 1. Prove the sum of the positive integers less than n and relatively prime to n equals 12nφ(n) as follows: (a) Let a1 , a2, . . . , aφ(n) be the desired integers and set s = a1 + a2 + · · ·+ aφ(n) (b) Explain why gcd(n − ai , ai) = 1 for i = 1, 2, . . . , φ(n) and hence{ a1, a2, . . . , aφ(n) } = { n− a1, n− a2, . . . , n− aφ(n) } (c) Now write s in another way and equate 6. (12 pts) Answer parts (a) and (b) (a) Explain why 26 must have a primitive root (just quote a theorem) and find the smallest primitive root mod26. Then express all the primitive roots mod26 in terms of this one. 1 (b) Prove 20 is a primitive root of 73 by considering ord732 and ord7310 7. (10 pts) Answer parts (a) and (b) (a) Suppose p is an odd prime such that gcd(ab, p) = 1 (for natural numbers a and b). Explain why at least one of the numbers a, b, or ab must be a quadratic residue modp (b) Prove: given a prime number p, there must exist a natural number n such that p divides the product (n2 − 2)(n2 − 3)(n2 − 6) (first show this is true if p = 2 or p = 3, then assume p > 3 and use part (a)) 8. (18 pts) Evaluate the following Legendre or Jacobi symbols (a) (−125 113 ) (b) ( 111 301 ) (c) ( 210 229 ) 2