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
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.]
- 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.