Harbourne's Math 310 Problem set 5

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.
- 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₁, ..., p_m. He then multiplied them together and added one; i.e., he looked at P = p₁...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₁, ..., q_n, but you should now look at Q = (q₁...q_n)²+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₁, ..., q_n. Now look at Q = (q₁...q_n)²+2. Each q_i is congruent to 3, hence (q_i)² is congruent to (3)² = 9 (which is itself congruent to 1) modulo 4. Thus (q₁...q_n)² 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.

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

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)² for some integers m and n, with m and n relatively prime. Thus 3n²=m², so 3 divides m² and hence also m (by the Fundamental Theorem of Arithmetic). But that means m = 3r for some integer r, so 3n² = (3r)² = 9r², or n² = 3r², 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)² for some integers m and n, with m and n relatively prime. Thus 3n²=m². But gcd(m,n)=1 implies gcd(m²,n²)=1, so m² and n² are relatively prime. But 3n²=m², so m² divides 3n². Since m² and n² are relatively prime, m² divides 3. But 3 is prime so either m² = 1, or m² = 3. If m² = 1, then 3n²=1, but we know 3n² > 3 so this is impossible. If m² = 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.