# Is this proof that there are infinite primes correct? I thought of it and I am fairly certain it is correct.

Let $$p_n$$ be the $$n$$th prime in ascending order. We wish to prove that $$p_{n+1} - p_n < p_1 ... p_n$$

Proof: Observe $$N = p_1 ... p_n + 1$$ which by the division algorithm is not divisible by any $$p_i$$ for $$i = 1, ... , n$$. We know $$N$$ must have some prime divisor. Let $$p_k$$ be the prime divisor of $$N$$ where $$p_k > p_n$$. Thus, $$p_{n+1} \leq p_k \leq N = p_1 ... p_n + 1$$ Since $$p_n > 1$$, $$p_{n+1} - p_n < p_1 ... p_n$$ Therefore, the difference between the $$n+1$$st prime and the $$n$$th prime is less than $$p_1 ... p_n$$, and so there are infinite primes.

• The very first sentence of your proof establishes that there are an infinite number of primes. The rest of your proof establishes an upper bound (albeit a very loose one) on the lengths of the Prime Gaps. A much tighter bound is given by Bertrand's postulate, which says that $p_{n+1}-p_n<p_n$. – TonyK Feb 14 '20 at 16:36
• Thank you for the information!! – John Mancini Feb 14 '20 at 17:26
• @JohnMancini Your proof is correct, but I am afraid you are late by some 2500-3000 years :) – NiloS Feb 14 '20 at 17:42

You don't need to show that $$p_{n+1}-p_n to conclude that there are infinitely many primes. The proof is over as soon as you show that $$N$$ has a prime divisor that is greater than $$p_1,\dots,p_n$$. This shows that there must be a next largest prime $$p_{n+1}$$. Hence the set of primes cannot be finite (or else there would be an $$n$$ for which $$p_n$$ is the largest prime, and so there would be no larger prime $$p_{n+1}$$).
• You don't need to show $N$ has a prime that is greater than the $p_i$, only that it is different to them. – Jaap Scherphuis Feb 14 '20 at 16:47
• Right. In this case, the assumption is that $p_1,\dots,p_n$ are the first $n$ primes, so it would necessarily follow that $p_{n+1}$ is greater than them if it is different than them. – kccu Feb 14 '20 at 16:49
• @kccu It constantly blows my mind that Euclid proved that so long ago, and it is still a relevant theorem in many University classes today. I didn't realize my theorem is just copying Euclid's theorem, and then putting a large upper bound on $p_{n+1} - p_n$, but now I know :) – John Mancini Feb 14 '20 at 19:19