- 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.
- For any integer n we have n = 4q+r for some r which is either 0, 1, 2 or 3. But if n is odd, then r must also be odd, so r must be either 1 or 3, which means p is congruent either to 1 or to 3 modulo 4.

- 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.]- Assume there are only finitely many primes
congruent to 3 modulo 4. Thus we can list them, as say
q
_{1}, ..., q_{n}. Now look at Q = (q_{1}...q_{n})^{2}+2. Each q_{i}is congruent to 3, hence (q_{i})^{2}is congruent to (3)^{2}= 9 (which is itself congruent to 1) modulo 4. Thus (q_{1}...q_{n})^{2}is congruent to 1 modulo 4, so Q is congruent to 1+2=3 modulo 4. Now factor Q as a product of primes. We know 2 is not a factor (since Q is odd) and we know none of the primes on our list are factors (since they leave a remainder of 2 when divided into Q). We also know that the prime factors of Q cannot all be congruent to 1 modulo 4, since the product of numbers congruent to 1 modulo 4 is itself congruent to 1 (and in particular not 3) modulo 4. Thus there must be a prime factor of Q congruent to 3 modulo 4 which is not on our list. This contradicts our list being a list of all primes congruent to 3 modulo 4. I.e., no such list can ever be complete, so there must be infinitely many primes congruent to 3 modulo 4.

- Assume there are only finitely many primes
congruent to 3 modulo 4. Thus we can list them, as say
q
- 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.
- Here is a list of all primes from 30000 to 30300 (there are 30):
The number 30011 is prime. (This occurs for i = 2.) The number 30013 is prime. (This occurs for i = 2.) The number 30029 is prime. (This occurs for i = 3.) The number 30047 is prime. (This occurs for i = 5.) The number 30059 is prime. (This occurs for i = 6.) The number 30071 is prime. (This occurs for i = 8.) The number 30089 is prime. (This occurs for i = 9.) The number 30091 is prime. (This occurs for i = 10.) The number 30097 is prime. (This occurs for i = 10.) The number 30103 is prime. (This occurs for i = 11.) The number 30109 is prime. (This occurs for i = 11.) The number 30113 is prime. (This occurs for i = 12.) The number 30119 is prime. (This occurs for i = 12.) The number 30133 is prime. (This occurs for i = 14.) The number 30137 is prime. (This occurs for i = 14.) The number 30139 is prime. (This occurs for i = 14.) The number 30161 is prime. (This occurs for i = 17.) The number 30169 is prime. (This occurs for i = 17.) The number 30181 is prime. (This occurs for i = 19.) The number 30187 is prime. (This occurs for i = 19.) The number 30197 is prime. (This occurs for i = 20.) The number 30203 is prime. (This occurs for i = 21.) The number 30211 is prime. (This occurs for i = 22.) The number 30223 is prime. (This occurs for i = 23.) The number 30241 is prime. (This occurs for i = 25.) The number 30253 is prime. (This occurs for i = 26.) The number 30259 is prime. (This occurs for i = 26.) The number 30269 is prime. (This occurs for i = 27.) The number 30271 is prime. (This occurs for i = 28.) The number 30293 is prime. (This occurs for i = 30.)

Some of you used my web form, some of you used tables of primes, some of you tried dividing N by all integers from 2 to N^{1/2}(using the fact that an integer N bigger than 1 is prime if and only if N has no factor bigger than 1 but less than or equal to N^{1/2}).

- Here is a list of all primes from 30000 to 30300 (there are 30):
- How many primes does the Prime Number Theorem suggest
there should be between 30000 and 30300? (I.e., compute
pi(30300) - pi(30000).)
- Since pi(n) is about n/(ln(n)), we can expect there would be around 30300/ln(30300) - 30000/ln(30000) or 2936.36 - 2910.09 = 26.27 primes between 30000 and 30300.

- Prove that the square root of 3 is irrational.
- Here is a proof that follows what we did in class.
Suppose not. Then 3=(m/n)
^{2}for some integers m and n, with m and n relatively prime. Thus 3n^{2}=m^{2}, so 3 divides m^{2}and hence also m (by the Fundamental Theorem of Arithmetic). But that means m = 3r for some integer r, so 3n^{2}= (3r)^{2}= 9r^{2}, or n^{2}= 3r^{2}, so r divides n. Thus contradicts m and n being relatively prime. Thus it must not be possible to write the square root of three as m/n.

Here is a similar but different proof. Suppose not. Then 3=(m/n)^{2}for some integers m and n, with m and n relatively prime. Thus 3n^{2}=m^{2}. But gcd(m,n)=1 implies gcd(m^{2},n^{2})=1, so m^{2}and n^{2}are relatively prime. But 3n^{2}=m^{2}, so m^{2}divides 3n^{2}. Since m^{2}and n^{2}are relatively prime, m^{2}divides 3. But 3 is prime so either m^{2}= 1, or m^{2}= 3. If m^{2}= 1, then 3n^{2}=1, but we know 3n^{2}> 3 so this is impossible. If m^{2}= 3, then there is a positive integer m less than 3 whose square is 3, but there is no such integer (the only possibilities are m=1 and m=2 and neither works). Thus every possibility leads to a contradiction, so the square root of 3 is irrational.

- Here is a proof that follows what we did in class.
Suppose not. Then 3=(m/n)