## Math 310: Problem set 6

*Instructions*: This problem set is due
Friday, February 17, 2006.
- (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.)
- (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=4q
_{1} + 1 and n=4q_{2} + 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: p
_{1}, p_{2}, ..., p_{t}.
Let P = p_{1}p_{2}...p_{t} 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 p_{1}, p_{2}, ..., p_{t}
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
p_{1}, p_{2}, ..., p_{t} that divides N. Conclude
that there must be infinitely many primes of class 3.)