-1

From the proof that there are infinitely many primes:

Given all the primes $p_i$ known up to the $n$th prime, construct the number $q_n$ such that

$$ q_n = 1 + \prod^{n}_{i=1} p_i $$

Since there is no prime within the first $n$ primes that evenly divides $q_n$, either $q_n$ must be prime or there is another prime $p_k$ that evenly divides $q_n$. Hence, for all $n$, there is always another prime not included in the first $n$ primes.

I've checked the following values.

$q_1 = 2 + 1 = 3$, which is prime.
$q_2 = (2)(3) + 1 = 7$, which is prime.
$q_3 = (2)(3)(5) + 1 = 31$, which is prime.
$q_4 = (2)(3)(5)(7) + 1 = 211$, which is prime.
$q_5 = (2)(3)(5)(7)(11) + 1 = 2311$, which is prime.
$q_6 = (2)(3)(5)(7)(11)(13) + 1 = 30031 = (59)(509)$, which is not prime.

How would I proof without example that it is possible for this function to produce a non-prime value?

Thank you to Henning Makholm for providing the example $q_6$.

Attempt:

Assume that $q_n$ is non-prime. There is some prime $p_k > p_n$ and an other number $c$ that divide $q_n$. I must show that for $p_k$ to exist, there is a prime $p_i$ where $i < n$ that divides $c$ for this to be a proof by contradiction. It's not immediately apparent to me how to prove this.

Community
  • 1
Axoren
  • 2,303
  • 1
    Compute for a while longer. Then look for information about primorials. – André Nicolas Feb 03 '15 at 19:36
  • There really is no reason why it should "always" be prime. All we know is that $q_n$ will not be divisible by any $p_1,\ldots,p_n$ of the first $n$ primes. But the $q_n$ grow so rapidly that before long the smallest prime divisor of $q_n$ gets to be larger than (the slowly growing) $p_n$ and we find our counterexample. – hardmath Feb 03 '15 at 19:51

2 Answers2

3

You can't prove that it always produces primes, because that is not true.

The way to prove that it doesn't always produce primes is to show a counterexample.

The smallest counterexample is $$ q_6 = 2\cdot 3\cdot 5\cdot7\cdot 11\cdot 13+1 = 30031 = 59\cdot 509 $$

It's hard to state categorically that this can't be proved other than exhibiting a counterexample. Conceivably we could find some property that the $q_i$ sequence has (and prove that it has it without computing so much that we run into the counterexample itself) and then prove that no sequence with that property can consist entirely of primes. But even if that can be carried out, it would surely (in this case) be more complex than showing the counterexample.

hmakholm left over Monica
  • 286,031
  • I still want to prove without a specific example that it's "possible" for there to be examples. A much harder thing to do than to just give an example. However, I'll edit the question to reflect that there are non-prime $q$-values. – Axoren Feb 03 '15 at 19:41
  • 1
    Is it known that there are infinitely many non-prime values? I suspect not. – Robert Israel Feb 03 '15 at 19:52
-1

How about "Every number has possible prime factors up to its square root. Thus every $q$ has possible prime factors between the largest prime used to create it and it's own square root."?

Elem-Teach-w-Bach-n-Math-Ed
  • 1,205
  • I know that this is far from correct format for a proof and someone else could easily rephrase this better, but isn't this in essence what we're saying here? $q$ might be divisible by anything between the largest prime used to create it and $\sqrt{q}$? – Elem-Teach-w-Bach-n-Math-Ed Feb 06 '16 at 00:27
  • Another thought... remove the 2 from $q_3 = (2)(3)(5) + 1 = 31$. You now have $q = (3)(5) + 1 = 16$ - not prime. Why? $(3)(5)$ can never be equivalent to 0 (mod 2) as it doesn't have 2 for a factor. It must be something else (mod 2). It can only be 1 (mod 2). Thus after $+1$, you now have 0 (mod 2). Thus any $q$ not including 2 must be divisible by 2. If you instead removed the 3, you'd have $q = (2)(5) + 1 = 11$, which is prime. However, since $(2)(5)$ must be equivalent to either 1 or 2 (mod 3) then adding 1 would give either 2 (mod 3) or 0 (mod 3) as in $q = (2)(5)(7)(11) + 1 = 771$. – Elem-Teach-w-Bach-n-Math-Ed Feb 06 '16 at 00:52