## 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.
- Read pp. 47-56 and pp. 59-62.
- 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.
- 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
p
_{1}, ..., p_{m}. He then multiplied them together
and added one; i.e., he looked at P = p_{1}...p_{m}+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
q_{1}, ..., q_{n}, but you should now look at
Q = (q_{1}...q_{n})^{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.]
- 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.
- How many primes does the Prime Number Theorem suggest
there should be between 30000 and 30300? (I.e., compute
pi(30300) - pi(30000).)
- Prove that the square root of 3 is irrational.