1
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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$. $\endgroup$ – TonyK Feb 14 '20 at 16:36
  • $\begingroup$ Thank you for the information!! $\endgroup$ – John Mancini Feb 14 '20 at 17:26
  • 2
    $\begingroup$ @JohnMancini Your proof is correct, but I am afraid you are late by some 2500-3000 years :) $\endgroup$ – NiloS Feb 14 '20 at 17:42
1
$\begingroup$

You don't need to show that $p_{n+1}-p_n<p_1\cdots 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}$).

$\endgroup$
4
  • $\begingroup$ You don't need to show $N$ has a prime that is greater than the $p_i$, only that it is different to them. $\endgroup$ – Jaap Scherphuis Feb 14 '20 at 16:47
  • $\begingroup$ 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. $\endgroup$ – kccu Feb 14 '20 at 16:49
  • $\begingroup$ @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 :) $\endgroup$ – John Mancini Feb 14 '20 at 19:19
  • $\begingroup$ @JohnMancini: All facts about the natural numbers remain true no matter how far into the future. The harder questions are: (1) What are natural numbers? (2) What are facts about them? I won't attempt to answer the second question, but you can be certain that basic facts involving prime numbers will remain relevant to humanity for as long as humanity lasts, because almost every cryptographic system depends on the properties of primes in some way or another. For example, RSA depends on Fermat's little theorem for decryption. $\endgroup$ – user21820 Jun 24 '20 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.