## Math 310: Problem set 5

Instructions: This problem set is due Thursday, September 28, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. Read pp. 47-56 and pp. 59-62.
2. If p is an odd prime, prove that p is congruent either to 1 or to 3 modulo 4, and show that both possibilities occur.
3. Now prove that in fact there are infinitely many primes congruent to 3 modulo 4. [Hint: Mimic Euclid's proof that there are infinitely many primes, but make the following change. Assuming that there are only finitely many primes, Euclid listed them, as say p1, ..., pm. He then multiplied them together and added one; i.e., he looked at P = p1...pm+1. He then showed there must be a prime that divides P but which is not on his list. In the situation of this problem, you can instead assume that there are only finitely many primes congruent to 3 modulo 4, so you also can list them, as say q1, ..., qn, but you should now look at Q = (q1...qn)2+2 and show that there must be a prime congruent to 3 modulo 4 that divides Q but which is not on your list.]
4. You were assigned a number i between 1 and 30, in class. State your number i, and list all numbers n in the interval from 30000 + 10(i-1) to 30000 + 10i which are prime. Briefly indicate how you determined when an integer n is prime.
5. How many primes does the Prime Number Theorem suggest there should be between 30000 and 30300? (I.e., compute pi(30300) - pi(30000).)
6. Prove that the square root of 3 is irrational.