0
$\begingroup$

How would you show that not every number of the form $N = (p_1 p_2 p_3 \cdots p_n) + 1$ is prime, where $p_1, p_2, p_3,...,p_n$ is the list of all prime numbers?

I have tried several proof techniques including the proof of infinitely many primes but to no avail. Any suggestions would be appreciated.

$\endgroup$
4
  • 1
    $\begingroup$ There is no exhaustive, yet finite list of prime numbers. Do you mean $p_1, \ldots, p_n$ are the first $n$ prime numbers? If so, I would recommend searching for a counterexample. $\endgroup$ – user754697 Mar 4 '20 at 10:29
  • $\begingroup$ See Euclid's proof $\endgroup$ – Mauro ALLEGRANZA Mar 4 '20 at 10:33
  • $\begingroup$ @user754697, $p_1$,...,$p_n$ is the list of all prime numbers. $\endgroup$ – DYBnor Mar 4 '20 at 10:33
  • 1
    $\begingroup$ @DYBnor The point is that there are infinitely many primes. So either $p_1\times p_2\times \ldots \times p_n=2\times3\times\ldots$ is infinite or it contains a finite subset of the primes (e.g., the first ones). $\endgroup$ – Jam Mar 4 '20 at 10:35
4
$\begingroup$

You could just do it by counterexample. The Euclid numbers are the numbers of the form $p_n\#+1$, where $p\#$ denotes the "primorial" (the product of the primes less than or equal to $p$). These are exactly what you desire in form: $p_n$ denotes the $n^{th}$ prime in this context.

The first composite Euclid number is the sixth one:

$$p_6\# +1 = 13\# + 1 = 30031 = 59 \times 509$$

$\endgroup$
2
  • $\begingroup$ @ Evee Trainer, I am a bit confused. How can you use counterexample when the statement has got 'not' in it.? In am thinking in this case $p_6$# + 1 confirms the statement. $\endgroup$ – DYBnor Mar 4 '20 at 11:01
  • $\begingroup$ @DYBnor It's a counterexample to the claim that all numbers of the form $p_n\#+1$ are prime. So it's an example that proves your claim. It just depends on which angle you look at the problem. Mostly, you'd phrase this type of conjecture as "proposition X is true for all $n$". $\endgroup$ – Jam Mar 4 '20 at 11:07

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.