0
$\begingroup$

Let $P_k$ be a prime number and let $P = 2.3.\dots.P_k$. be the product of all primes smaller or equal to $P_k$.

Then $P+1$ is either a prime number or not. If it is not a prime number it shares factors with $P$. Let the product of these factors be $P_r$ such that $P=P_sP_r$.

Then we can write $P+1 = P_rm$ where $m$ is some product of prime numbers. From this it follows that $P_r(P_s -m) = -1$.

Now here's where I get shaky. Does this not imply that $P_r=1$. Does this then not mean that $P+1$ does not in fact share any factors with $P$ and that therefore it is a prime number itself?

Of course this cannot be a prime number generator but where did I make the error?

$\endgroup$
4
  • 3
    $\begingroup$ No, because $P+1$ is much bigger than $P_k$, it is possible for $P+1$ to not be prime and have prime factors bigger than $P_k$. This is a related to a common misreading of Euclids proof that there are infinitely many primes. $\endgroup$
    – Thomas Andrews
    Nov 10, 2015 at 15:23
  • 4
    $\begingroup$ The typical counter-example is that $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509$ $\endgroup$
    – Thomas Andrews
    Nov 10, 2015 at 15:29
  • $\begingroup$ So, what you've found is related to Euclid's proof that there are infinitely many primes. If you have a finite set of primes, $p_1,\dots,p_k$, then they cannot be all of them, because $p_1p_2\dots p_k+1$ must be divisible by another prime. It might not be prime, but what it means is that no finite list of primes is complete. $\endgroup$
    – Thomas Andrews
    Nov 10, 2015 at 15:47
  • $\begingroup$ But as a formula for finding more primes, this proof is very slow, because you have to factor $p_1p_2\dots p_k+1$ to find the new prime, and factoring that huge number is going to be harder than just dumbly searching for a prime after $p_k$. $\endgroup$
    – Thomas Andrews
    Nov 10, 2015 at 15:49

1 Answer 1

Reset to default
1
$\begingroup$

As mentioned in comments, the value is not always prime, but obviously, any prime factors have to be bigger than $P_k$. Indeed, for the primes $P_k$ after $11$ and less than $50$, the product of the primes up to and including $P_k$, then adding one, results in a value that is not prime, except in the case of $31$.

$$\begin{align} 2\cdot3\cdot5\cdot7\cdot11\cdot13+1 &= 30031 \\&= 59\cdot509\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17+1 &= 510511 \\&= 19\cdot97\cdot277\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19+1 &= 9699691 \\&= 347\cdot27953\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23+1 &= 223092871 \\&= 317\cdot703763\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29+1 &= 6469693231 \\&= 331\cdot571\cdot34231\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37+1 &= 7420738134811 \\&= 181\cdot60611\cdot676421\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41+1 &= 304250263527211 \\&= 61\cdot450451\cdot11072701\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43+1 &= 13082761331670031 \\&= 167\cdot78339888213593\\ 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47+1 &= 614889782588491411 \\&= 953\cdot46727\cdot13808181181\\ \end{align}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .