Suppose we have

2 * 17 = 34.

Now we add 1.

34′ = 35.

Now 35 is not prime, it is a product of 5 and 7. These are two primes not in the factorization of 34. We also have that 5 and 7 are both smaller than 17. We need to avoid these pitfalls in a prime number list extension style proof.

http://www.math.utah.edu/~pa/math/q2.html

http://primes.utm.edu/notes/proofs/infinite/euclids.html

Suppose we have

N = p_1 * …. * p_n

N’ = N + 1

Here N is given in terms of a prime factorization, i.e. all the p_i are primes. Moreover, they are the primes in order, taken with multiplicity one for each prime.

Case I. If N’ is prime, then we have a new prime. It is bigger than p_n. (prove that)

Case II.

If N’ is not prime, then the proof of infinitely many primes shows there has to be a prime bigger than p_n. This is what we have not done yet in this case.

When we prove this, we can conclude that the list of primes does not end.

(Notice how uniqueness of naturals enters in here. As we go in succession chains, we get unique numbers from those before. We don’t go back in a cycle. This is part of what we learn in Peano Axiom treatments.)

Let p be one of the primes in the factorization of N.

N’/p = M + 1/p

Here M is N/p and is a natural number. (prove this)

1/p is not a natural number for p bigger than one. (prove this)

(Show p is bigger than one is part of our proof. Fill in step.)

M + 1/p is not a natural number. (prove this)

N’/p is not a natural number. Thus N’ has to have a prime factor greater than p_n.

Conclusion: N’ can’t have a prime factor less than p_n, because by assumption on N, it is the first n prime numbers multiplied together. Note how the order property of natural numbers is used in specifying N.

End Case II.

In either Case I or Case II, we need to associate (n’,p(n’)) where p(n’) is the n’ prime. Thus we continue the list in order.

N’ exists as a prime in Case I. But it still may not be the next prime after p(n). So we have to go through and find the next prime p(n’) before iterating the proof. All we learned from Case I and Case II is that a next prime exists. We also know it is between p(n) and N’, excluding p(n) and including N’.

Some other proofs.

http://primes.utm.edu/notes/proofs/infinite/

We could proceed to structure the proof differently.

Lemma: Assume N is not prime. Then if N’ is not prime, then N and N’ do not share a common prime factor.

Stated differently:

Lemma: (N,N’) can not share a prime factor if both are non-prime.

Lemma: Thus if N, N’ are both not prime, then N’ must have a prime factor not in the prime factorization of N.

Lemma: If N had all the first n primes, then N’ must have a prime after the first n primes.

This way of structuring the proof brings it out more clearly. We break it into lemmas that explicitly state some property we are proving in Case II. This makes the logical structure of the proof easier to grasp. This is chunking. This is how we make proofs and explanations easier to understand at all age and sophistication levels.

This makes it easier to reproduce the proof later.

The above is draft and preliminary. I will have to check this later to see if missed something.