# How can you prove that 3 1

Claim: There are infinitely many prime numbers

The required proof is often given by contradiction. I want to do that too first. As a second proof, I will give that by complete induction. It will be seen that the contradiction proof is more laborious. Namely, the contradiction is generated exactly with the constructive idea for the complete induction.

If there really are an infinite number of prime numbers, one certainly cannot write down all prime numbers. But you can check the possibility that there are only a finite number of prime numbers and think about this possibility consistently. At the end of this reflection, you will find that something is wrong. And if an end result based on the laws of logic obviously cannot be true, it has been proven that the assumption made at the beginning cannot be true either. According to mathematical logic, something wrong can never follow from something right. This proof technique is called a Proof of contradiction.

Accepted there would only be a finite number of prime numbers p1, ...., pn.
Then consider the number p = p1* ... * pn+1, which is obviously not due to any of the pi, i = 1, ..., n is divisible. Then p, which of all pi is different, obviously be a prime number.
That is a contradiction to assumption.
So the assumption was wrong that there must be an infinite number of prime numbers.

The proof contains a constructive idea, how one can construct another number from the first n prime numbers, through which one can prove the existence of another, the (n + 1) th prime number.
Instead of proving by contradiction, one would have that too direct proof being able to lead. It goes like this:

Let the first n prime numbers be known. Then consider number q = p1* ... * pn+1, which is obviously not due to any of the pi, i = 1, ..., n is divisible.

We don't know whether q is a prime number, so let's look at both possibilities now.
Case 1: q is a prime number. Then we found another prime number.
Case 2: q is not a prime number. Then there is a proper divisor of q. (A real divisor is neither 1 nor q itself).
According to the construction of q, this divisor is not one of the prime numbers p1, ..., pn. So there must be another prime that divides q. This "other" prime number is greater than pn. I will call this new prime p*. p* is not necessarily the n + 1 -th prime (there may be other prime numbers between the largest prime number among the first n prime numbers and the new prime number), but the existence of n prime numbers implies the existence of at least n + 1 prime numbers. That way of inferring is the complete induction. The existence of a prime number suffices as an induction start. Starting from p1= 2 one proves the existence of another prime number.

If you are wondering whether q is not always a prime number, I will give you a counterexample:
2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 is not a prime number, because 30031 = 59 * 509.

One must therefore be careful in the induction step.
From the first n prime numbers p1, ...., pn results in the existence of another. The proof does not say what this new prime number is.
And the prime number p* is not necessary the (n + 1) -th prime number. But if it is up to p* there are more than n + 1 prime numbers, then that's enough. One then looks for the first n + 1 from the more than n + 1 prime numbers and can thus carry out the induction step from n + 1 to n + 2.