# Gaps between primes

I recently watched a video about the recent breakthrough involving the gaps between primes. I have an idea that I'm sure is wrong, but I don't know why.

1. If you take the product of all prime numbers up to a certain number and call it x, won't x-1 and x+1 always be primes?
2. And since they always differ by 2, doesn't that make there an infinite number of primes that differ by 2?

Once again, I know that I'm wrong, but I would like to know why.

-
Because those will not be primes in general. I forgot how many you need to take before it fails. –  Tobias Kildetoft Jul 22 '13 at 18:59
$2\cdot 3\cdot 5 \cdot 7 = 210$. $209 = 11\cdot 19$. –  Daniel Fischer Jul 22 '13 at 19:01
There is a difference between relative primes and primes! –  Ali Jul 22 '13 at 19:01
No, for example $2\cdot3\cdot5\cdot7\cdot11\cdot 13+1 = 30031 = 59\cdot509$. We know this number can't be divisible by primes $2,3,5,7,11,13$, but there are bigger possible prime factors. –  Thomas Andrews Jul 22 '13 at 19:02
What was the video? I would like to watch it too! –  grayQuant Feb 23 at 18:14

Say $p_k$ is the largest prime $\le$ some number $n$. Then take $\displaystyle x=p_1p_2\cdots p_k$ Now, of course $x-1$ and $x+1$ are not divisible by any of $p_i,\ 1\le i\le k$. But there may be $p_k<p_i< x-1$ and $p_k<p_j<x+1$ such that $p_i|x-1$ and $p_j|x+1$. Just look at the example given by @DanielFischer to appreciate this fact.

-
Perfect explanation. Thank you. –  PygameNerd Jul 22 '13 at 19:28

What you propose is actually part of a very simple and elegant proof, proposed by Euclid (about 300 BC).

To prove that there are infinitely many primes:

• Suppose that $p_1 < p_2 < \dots < p_n$ are the only primes.
• Let $P = p_1p_2 \dots p_n + 1$. Now $P$ can be prime, but that is not the point.
• If $P$ is prime indeed, well, we have found another prime, because $P$ is not divisible by any of the primes $p_1 \dots p_n$. (The remainder in such case will always be one.)
• If $P$ is not prime, that means it has got a divisor $q$ that is neither $1$ nor $P$ itself. If $q$ was one of the numbers $p_1 \dots p_n$, that would mean it divides the product of all primes $p_1p_2 \dots p_n$. But we supposed that $q$ divides $P = p_1p_2 \dots p_n + 1$. Then $q$ has to divide the difference of both numbers (see below), which is $1$. And no prime can do that. Our assumption led us to contradiction.
• In either case, we have found another prime. This can be repeated infinitely many times, yielding infinitely many prime numbers.

Most people when they see this for the first time remember that $P$ is prime somehow and then get confused about it.

Say $m,n$ have a common divisor $q$. Then we can write $m = uq$ and $n = tq$. Their difference $m - n$ can then be written as $d = uq - tq = (u - t)q$. As we can see, $d$ is divisible by $q$ as well.

Furthermore, Euclid's proof shows that such prime number $P$ exists, it does not "construct" it. We have shown that an abstract mathematical entity exists without actually finding it.

Finding huge primes quickly is extremely important for cryptography. A basic algorithm for finding primes is called the Sieve of Eratosthenes.

-
There's a second part to Pygame's question that relates to settling the Twin Prime Conjecture (i.e. proving that there are infinitely many twin primes). The reason why you can't use Euclid's argument and cite $P+1$ and $P-1$ as evidence for infinitely many twin primes is that the act of showing either of them is prime has just proven by contradiction that there are not finitely many primes. Then it does not matter what else you can derive from the false statement. That's why you can't settle the Twin Primes Conjecture in that way. –  Assad Ebrahim Mar 18 at 22:27

Others have already pointed out that the product of the fist $n$ primes plus one will not in general be a prime number.

Just to point out what Yitang Zhang actually proved (I assume that this is what you give referemce to).

Let $p_n$ be the $n$th prime number. Then it is true that $$\liminf_{n\to \infty} p_{n+1} - p_n < 70\cdot 10^6.$$ That is, you will always be able to find conseqtive prime numbers that are at most 70 million apart.

-
The paper by Zhang Yitang could be on arXiv arxiv.org/find/math/1/au:+Zhang_Y/0/1/0/all/0/1? Could add the title and volume data publication in Annals of Mathematics? –  Elias Jul 22 '13 at 19:56
For me this is a very surprising result that contradicts my intuition. –  Elias Jul 22 '13 at 19:58
@Elias: Has the paper already appeared? –  Thomas Jul 22 '13 at 20:00
On this link terrytao.wordpress.com/2013/07/07/… you can see the refinement of Zhang's argument to reduce the gap to no more than $5414$ - the obstacles to improving this are increasing though there are suggestions which might get it down by a further $750$ or so. It also seems possible from Tao's blog that there is a more elementary proof (but with a worse bound). Zhang's proof and the computer age have produced a revolution which would once have taken a generation or more. –  Mark Bennet Jul 22 '13 at 21:22
@Thomas I do not have access to the Annals of Mathematics. I thought that was already published. –  Elias Jul 23 '13 at 0:10

Previous posters have already answered the first part of your question (finding primes by taking products), but not yet the second part.

With reference to the second part of your question about settling the Twin Prime Conjecture, i.e. proving that there are infinitely many twin primes:

The reason why you can't use a Euclid style argument (explained above by David) and cite $P+1$ and $P-1$ as evidence for infinitely many twin primes is that the act of showing that either of them is prime proves by contradiction that there are not finitely many primes.

Once you've established that, then it does not matter what else you can derive from the false statement "Suppose there are finitely many primes...". Anything that follows from that is not guaranteed to be true.

That's why you can't settle the Twin Primes Conjecture in that way.

-