Math545 Homework 4 Due Wed, Oct 28, 2013 Directions: Solve the following 6 problems. For computer problems, complete solutions include source code, an English language overview of your code, and the nal answer. The overview should be suciently complete that an intelligent reader with no prior access to your code will understand how it works. See the course syllabus and the Homework Webpage on the course website for general directions and guidelines. 1. [NT 5-2.f9,10g] (a) Prove that if p is a prime and p 1 (mod 4), then p ?? 1 2 !2 ??1 (mod p). (b) Use the above to nd a solution for each of the following. i. x2 ??1 (mod 13) ii. x2 ??1 (mod 17) 2. [NT 5-3.4] (a) Prove that for each n, there are n consecutive integers, each of which is divisible by a perfect square larger than 1. (b) Using your proof above, explicitly nd 3 consecutive integers, each of which is divisible by a perfect square larger than 1. In your answer, give the integers as well as the corresponding perfect squares. 3. [NT 6-4.2] Prove that if f(n) is multiplicative, thenXdjn (d)f(d) =Ypjn 1 ?? f(p). 4. Primitive Roots. (a) [NT 7-1.1] Find all primitive roots modulo 5, modulo 9, modulo 11, modulo 13, and modulo 15. (b) Let a and m be positive, relatively prime integers. Let S be the set of primes dividing (m). Prove that if a(m)=p 61 (mod m) for each p 2 S, then a is a primitive root of m. 5. [NT 8-1.4] Modify the proof of Theorem 8{1 to prove that there exist innitely many primes congruent to 5 (mod 6). 6. The prime number counting function. (a) In class, we proved that (2n) ln(4) n ln n + (n) for n 2. Prove by induction that (2t) 62t t for t 1. Hint: establish the base cases t = 1 and t = 2 directly, and the case t 3 in the inductive step. Note: using additional base cases, we could reduce the constant 6. (b) Prove that (n) C n ln n for some constant C.