## Math 310: Problem set 6

Instructions: This problem set is due Friday, February 17, 2006.
1. (2 points) Let m be the integer I emailed to you. Thus each of you has your own particular m. For each integer n from 34000+10m to 34000+10m+10, determine whether or not n is prime. List the ones that are prime. (If you have a calculator that can do this, fine. If not, you can use the web form on our class web site. Combine results in class as a test of the Prime Number Theorem, which gives an estimate on how many primes there are in a range of integers.)
2. (8 points) Let n be a positive integer. Let r be the remainder when n is divided by 4. We will say n has class r. (Thus, for example, 10 has class 2, 83 has class 3, and every n has class either 0, 1, 2 or 3.)
• (a) Show that a positive integer of class 0 or 2 is even.
• (b) Show that every odd integer has class either 1 or 3.
• (c) If m and n are positive integers of class 1, then so is mn. (Hint: First write m=4q1 + 1 and n=4q2 + 1.)
• (d) Mimic Euclid's proof that there are infinitely many primes to show that there are infinitely many primes of class 3. (Hint: Assume that there are only finitely many primes of class 3. List them: p1, p2, ..., pt. Let P = p1p2...pt be the product. Show that P has class either 1 or 3. Now define an integer N as follows. If P has class 1, let N = P+2. If P has class 3, let N = P+4. Show that, either way, N has class 3. Show that none of the primes p1, p2, ..., pt divides N. Using the fact (that we already know) that N is either prime or a product of primes, conclude that there must be some prime q of class 3 other than any of p1, p2, ..., pt that divides N. Conclude that there must be infinitely many primes of class 3.)