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.