The mistake and correction of the proof of infinitely many prime numbers during lecture.

1.Doubt about the proof of the lecture.

The proof of there are infinitely many prime numbers given during lecture is wrong.

S : for any n in N, |P| > n ,     P is the set of all prime numbers.
Proof: Assume there is an N*, such that |P| <= N*.

Then |P| = K <= N*,

Then P = {p1,p2,p3,...pk}

Let r = p1*p2*p3*...*pk,

Then r>=2          # |P| >=1

Then r + 1 = p1*p2*p3*...*pk +1,

Then r +1> p1,p2,...pk,

Then r +1is not a prime    # |P|= K

Then there exists a p in P,  p| r +1  # any natural number has a prime factor.

Then p| p1*p2*p3*...*pk +1,

Then p| r+1 - r        # p|r = p1*p2*p3*...*pk certainly is true.

Then p| 1

Then it causes a contradiction.

Then the assumption is not true. 

Then for any n in N, |P| > n 

Then there are infinitely many prime numbers. 

The proof is wrong. Because we assume the r + 1 which is constructed by p1*p2*p3*...*pk +1 should have a prime divisor in P. But actually the constructed r +1 may not have any of the element in P.

A classic way to prove this may cause a huge problem:

The main problem with this proof is :

p = p1 * p2 * p3*...*pn + 1.p's divisor could be not in P.

An counterexample:

2*3*5*7*11*13 + 1 = 30031 = 59 * 509

59 is not equal to any of 2,3,5,7,11,13

  

2.Corrected proof:

Call the primes in our finite list p₁, p₂, ..., p_r.  Let P be any common multiple of these primes plus one (for example, P = p₁p₂...p_r+1).  Now P is either prime or it is not.  If it is prime, then P is a prime that was not in our list.  If P is not prime, then it is divisible by some prime, call it p.  Notice p can not be any of p₁, p₂, ..., p_r, otherwise p would divide 1, which is impossible.  So this prime p is some prime that was not in our original list.  Either way, the original list was incomplete. 

The first letter to everyone.

Dear all,

This blog is created for sharing my experience of studying csc165. It will keep track of my ups and downs during the study process and introduce my own opinion and understanding of how to tackle obstacles and problems, how to optimize the process and results, what to reflect and think about when the problem is solved and also my personal feelings.

I think there's nothing better than a personal blog in tracing the paths of mind. Because it's more organized and eternal than talk and more spontaneous and natural than a well prepared book. And it can be very reflective and well written, which leaves the person the alone time to think deeper and more comprehensively.

So as for the intention of communication, any kinds of opinions or feedback are welcome. I hope this blog can be more interactive than personal. And I will really appreciate it if there are constructive and thoughtful communications going on here. :)

Also, I'm very excited for upcoming study. Things seem to get more interesting! Just need to hang in there and more proactive!

Sincerely,
L.gal