12
$\begingroup$

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds have thought on this previously. I can't see the issue, so I thought I would raise it in a broader forum. What is wrong with this proof?

1) A number n is prime iff n mod p is non zero for every prime number 1 < p < n

This is easy to prove from the definition of a prime number and mod. It just says that n is not equally divisible by another prime, making it prime.

Let $p_n$ = the nth prime $p_0 = 1$, $p_1 = 2$ ...

Consider $N_n = \Pi_0^n p_n$.

It is easy to see that $N_n \mod p_j = 0 $ for all primes $0 < j < n$

$(N_n + 1) \mod p_j = 1 $ for all primes $0 < j < n$, and therefore, from #1 must be prime

$(N_n - 1) \mod p_j = (p_j - 1) $ for primes $0 < j < n$, and therefore, from #1 must be prime as well

The set $p_n$ has infinite members (as shown by Euclid) , so there are infinite $N_n$. Therefore there are an infinite set of twin prime numbers $(N_n-1,N_n+1)$ .

$\endgroup$
  • 2
    $\begingroup$ Try writing out a few examples and you'll see where things go wrong. $\endgroup$ – RghtHndSd Dec 7 '14 at 7:07
  • 13
    $\begingroup$ There are more primes less than $N_n$, than just $p_1,p_2,\ldots,p_n$. $\endgroup$ – Zircht Dec 7 '14 at 7:08
  • 6
    $\begingroup$ You check that $N_n+1$ is not divisible by $p_j$, for $0<j<n$. But there may be primes between $p_n$ and $N_n$, that's where you have a problem. $\endgroup$ – zarathustra Dec 7 '14 at 7:08
  • $\begingroup$ What you have shown is that there is always another pair of numbers $N_n-1,N_n+1$ which are relatively prime to all of the first $n$ primes. You have not shown that either number is prime. $\endgroup$ – abiessu Dec 7 '14 at 7:13
  • 1
    $\begingroup$ … 1 isn't prime. $\endgroup$ – bjb568 Dec 7 '14 at 17:44
38
$\begingroup$

This repeats a common misconception about Euclid's proof. Your argument does not show that either $N_n+1$ or $N_n-1$ is prime, but rather that these numbers must be divisible by a prime greater than $p_n$. Indeed, $N_4=210$ has $N_4+1$ prime but $N_4-1=209$ is divisible by $11$.

$\endgroup$
  • 5
    $\begingroup$ (An aside: the question of whether $1$ should be a prime or not is a sort of red herring, insofar as it doesn't really matter: other definitions and assertions would simply have to be modified accordingly. Indeed, until late in the 19th century, $1$ was usually considered prime, apparently. The point is that we understand that specific aspect, and it's not really the issue at all...) $\endgroup$ – paul garrett Dec 7 '14 at 23:19
  • $\begingroup$ I had heard that 1 can't be a prime because it breaks prime factorization... $\endgroup$ – k_g Dec 8 '14 at 4:39
  • 3
    $\begingroup$ @k_g: that's not why it can't be a prime, that's why it's convenient for it not to be a prime. Unique prime factorisation says that every integer has a prime factorisation that is unique up to the order of factors. If we called 1 prime then we'd have to say unique up to the order of factors and the number of times 1 occurs, which would be annoying. Then again, with 1 not prime we have a definition/theorem that $p$ is prime iff p is not zero or a unit and $\forall a \forall b (p|ab \Rightarrow p|a \lor p|b)$. We choose the lesser inconvenience, but "can't" is overstating the problem :-) $\endgroup$ – Steve Jessop Dec 8 '14 at 10:57
  • 2
    $\begingroup$ Anyway, there are statements true of primes, statements true of units, and statements true of both primes and units. It's largely a matter of convenient short names that we don't call those three categories, "primes except units", "units", and "primes". Or for that matter "foos", "bars" and "bazes". "1 is not prime" is simply the assertion, "it's more convenient to define this handy short name to exclude units than includes them" $\endgroup$ – Steve Jessop Dec 8 '14 at 11:03
  • $\begingroup$ I see, so basically it's just a matter of semantics. $\endgroup$ – k_g Dec 8 '14 at 21:15
11
$\begingroup$

$$N_4-1=p_0p_1p_2p_3p_4-1=1\cdot2\cdot3\cdot5\cdot7-1=210-1=209=11\cdot19$$ $$N_6+1=p_0p_1p_2p_3p_4p_5p_6+1=1\cdot2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30030+1=30031=59\cdot509$$

$\endgroup$
  • 9
    $\begingroup$ To be honest, I think this answer would be a lot better with a few lines of explanation along the way. $\endgroup$ – Mast Dec 7 '14 at 12:42
  • 2
    $\begingroup$ It shows directly that the purported proof fails. What else do you want? $\endgroup$ – gnasher729 Dec 8 '14 at 0:29
  • 3
    $\begingroup$ I want more spacing in the answer. $\;$ $\endgroup$ – user57159 Dec 8 '14 at 2:09
3
$\begingroup$

$N_7+1 = 510511 = 19 ⋅ 97 ⋅ 277$, $N_7-1 = 510509 = 61 ⋅ 8369$ is the first example where both numbers are not primes. I would suggest that not only is $(N_k-1, N_k+1)$ not always a twin prime pair, but that this would actually be quite rare.

According to http://primes.utm.edu/top20/page.php?id=5 $N_k+1$, $N_k-1$ have been tested for k ≤ 100,000 with very few primes found, and with no twin primes found beyond the pair (2309, 2311).

$\endgroup$

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.