# Trying to understand Euclid's prime number proof

I am not a mathematician, so I don't really understand one specific of Euclid's proof. I am, however, trying to learn about prime numbers. Here's my question:

Why does Euclid use the set $P=p_1*p_2...*p_n$ instead of $R=p_1*p_2...*p_{(n-1)}$?

The reason why I am asking is because, and correct me if I'm wrong, as you move towards infinity, the distance between every prime number should logically get larger. For me, this brings up several questions. Assume $Z= 1$, $2$ or $3$. These three prime numbers are the only known primes in which the statement R < $p_n$ holds true. After the first three prime numbers, the subsequent primes follow the pattern of $R > p_n$

With that being said, if the distance between each prime number logically increases as you move towards infinity, shouldn't there eventually be an instance in which $R = p_n$ or... $R < p_n$ again?

In my mind at least, I can't understand what happens to the prime numbers after $R = p_n$ then passes into $R < p_n$. Does anything change with the prime numbers?

You see, with a different subset of numbers, I came to a completely different answer - that, maybe, $R < p_n$ cannot exist past 1, 2 or 3, so there could really be a 'highest prime number.' Am I making any sense? Why did Euclid use set P instead of R?

Thanks!

• Not entirely sure what you are asking. There might, for example, be infinitely many twin primes it which case it would not be true that the distance between successive primes increased for large numbers. – lulu Aug 8 '17 at 12:06
• By the way, when you say "These three prime numbers are the only known primes in which...", remember that 1 is not a prime number – user3141592 Aug 8 '17 at 12:10
• I don't get the point of your question...even if you could make a side argument to show that it would suffice to use the smaller collection, what would be gained? The proof would necessarily be more elaborate and one great beauty of Euclid's argument is its profound simplicity. Now, there might be mathematical value in showing that the other expression also worked, if that is true. – lulu Aug 8 '17 at 12:10
• Note: I just checked. Take $n=19$. That is, look at the primes $\{2,3,5,7,11,13,17,19\}$. Then, unfortunately, $2\times 3\times 5\times 7\times 11\times 13\times 17+1=510511 = 19\times 97\times 277$ so it is divisible by $19$. Thus you could not use the smaller collection without further work. – lulu Aug 8 '17 at 12:13
• @Antek: Actually there's no difference between the numbers (not sets) $P$ and $R$, to some extent. Euclid's argument is: take any finite number of primes, multiply them together and add $1$. The number you get must be divisible by some prime different from those used to produce it. Therefore there are infinitely many primes. – AdLibitum Aug 8 '17 at 12:26

The average distance between primes increases as you get into larger and larger primes. But it increases slowly.

The product $p_1 p_2 p_3 \cdots p_{n-1},$ however, grows very quickly:

\begin{align} 2 \cdot 3 &= 6 \\ 2 \cdot 3 \cdot 5 &= 30 \\ 2 \cdot 3 \cdot 5 \cdot 7 &= 210 \\ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 &= 2310 \\ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 &= 30030 \\ \end{align}

By this point we're only up to $13$ as the largest prime on the left hand side, and yet the right hand side is already in the tens of thousands. And it only gets more extreme as we keep multiplying by more primes.

So no, you would never get to a point where $R < p_n.$ On the contrary, the ratio $R/p_n$ keeps attaining larger and larger values.

By the way, there is no guarantee that by applying Euclid's argument to $p_1 p_2 p_3 \cdots p_{n-1}$ you will discover the prime $p_n.$ Yes, as a comment by lulu showed, when $n = 7,$ then $p_{n-1} = 17,$ and $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 +1 = 510511,$ which is divisible by the eighth prime, $19.$ But if we set $n=8$ then we have $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 +1 = 9699691,$ whose prime factorization is $9699691 = 347 \times 27953.$ That's right, by the time we get to $n=8$ the product $p_1 p_2 p_3 \cdots p_{n-1}$ is so enormous that the two prime factors of $p_1 p_2 p_3 \cdots p_{n-1} + 1$ are both many places beyond $p_n$ in the list of primes.

But boiled down to its essence, Euclid's proof argues that there is no such thing as the finite product of all the primes. By adding one to the alleged finite product of all the primes, we discover that it "missed" at least one prime; so if the list of all primes were finite, it wouldn't be a list of all the primes.

To make this work, however, we have to look at the product of all of the (allegedly finite number of) primes that exist. If we only have a list of some of the primes that exist, it would hardly be surprising that the "new" prime exhibited by Euclid's argument would be one that we already knew existed but didn't bother to put in the list. Whether we number the list of all primes from $1$ to $n$ or from $1$ to $n-1$ doesn't matter; what matters is the "all of the primes" part.

• Correction: Euclid's proof is not a proof by contradiction (from the hypothesis that there are only finite many primes). Rather, Euclid gave a constructive proof showing how to construct a prime not in any given finite set of primes, viz. take any prime factor of their $\rm product + 1,\,$ e.g. the least factor $> 1.\$ – Bill Dubuque Aug 8 '17 at 21:33
• @BillDubuque There is what Euclid actually wrote, and then there are the ways that present-day accounts present "Euclid's proof." I confess I do not recall the differences among these treatments well enough to say exactly what Euclid's original proof included beyond the construction. But the "proof by contradiction" idea seems to be a common setting in which to present Euclid's construction nowadays. Perhaps I should put "Euclid's" in quotation marks when I refer to Euclid's proof. (The three other extant answers at this time all describe a proof by contradiction; it's not just me.) – David K Aug 8 '17 at 22:26
• We number theorists do our best to try to correct the widespread misconception that Euclid's proof was by contradiction, but the error is so widespread that it is no easy task (this is discussed at length in the Intelligencer paper by Hardy and Woodgold that I cite here). There are many good reasons not to present the proof by contradiction besides historical inaccuracy (e.g. it often confuses novices into thinking that the product+1 is necessarily prime, and it destroys its constructive applications). – Bill Dubuque Aug 8 '17 at 22:37

https://www.youtube.com/watch?v=ctC33JAV4FI here's a basic overview of the video using the modern way to demonstrate the proof. By the way they probably use n as the index to go up to because n is easier to write.

1. Let's assume the set of primes is a finite set $\{p_1,p_2,p_3,...p_n\}$
2. Let's say the the natural numbers are infinite.
3. This means we can make a number in the list by multiplying all the primes together and adding one. ( $P=1+\prod_\limits{k=0}^n p_k$)
4. Using the fact that no number greater than a number divides into that number to give a natural number result we get that P can no longer divide by any of our prime set.
5. P is either prime or it's composite. If it's prime, it's missing from our set (so we started with an incomplete set). If it's composite it's prime factors aren't in our set ( so we started with an incomplete set). This contradicts that our set of primes contained all the primes in either case.
• You don't need to assume that the primes you listed are all the primes that there are. Besides, your point 2 is rather pointless. – AdLibitum Aug 8 '17 at 12:28
• @AdLibitum if the primes in the set aren't all the primes then in theory the new prime could just be one that was already known ( though I get that technically, any set of primes will create a factorization that uses primes not on the list is the point), and point two actually is very important because if the natural numbers aren't infinite then neither can be any subset of them (the primes that were dealing with are a subset of the natural numbers so if no subset can be infinite then the primes can't be...). – user451844 Aug 8 '17 at 12:31
• I think, I can't grasp this logically, because I'm thinking in terms of probability. My assumption is that as the set approaches infinity, the probability of a prime must decrease, and I assumed it eventually reached zero, when in fact it reaches infinitely close to zero – Antek Aug 8 '17 at 12:42
• @RoddyMacPhee: for the "all primes" thing see my comment in the comments section. About your point 2: $\Bbb N$ is certainly infinite because it has an injective map into itself that is not surjective (Peano). The "this means" you start your point 3 with is certainly misleading since the possibility to construct $P$ depends on the algebraic structure of $\Bbb N$ and not just for it being infinite. – AdLibitum Aug 8 '17 at 12:42
• in other words you think I should use the magma property of addition and multiplication of natural numbers ? – user451844 Aug 8 '17 at 12:47

It doesn't matter whether you use $n$ or $n-1$, the point is that you assume finitely many primes and you get a contradiction. ..