2

A common misinterpretation of Euclid's original proof for the infinitude of prime numbers is that numbers of the form $\ p_1p_2\ldots p_k+1\ $ (where the $\ p_i\ $ are distinct) must be prime. I understand this is not what the proof says.

However, out of interest:

are there infinitely many primes of the form $\ p_1p_2\ldots p_k+1\ $ where all the $\ p_i\ $ are distinct prime numbers?

Certainly one of the primes, e.g. $\ p_1\ $ must equal $\ 2,\ $ otherwise $\ p_1p_2\ldots p_k+1\ $ would be even. Also it is not known whether there are infinitely many Sophie Germaine primes, that is, primes of the form $\ 2p+1\ $ where $\ p\ $ is prime. However, Sophie Germaine primes is a subset of the set of primes I am asking for. For example, $\ 2\cdot 3\cdot 5+1 = 31,\ $ and $\ 2\cdot 3\cdot 7+1 = 43,\ $ are non-Sophie Germaine primes, but they do belong to my set. So the question remains, and an extension question could be: "what about primes of the form $\ p_1p_2\ldots p_k-1\ $ ?"

Ѕᴀᴀᴅ
  • 34,263
Adam Rubinson
  • 20,052
  • 2
    This is unknown. See the prime Euclid numbers – lulu Jul 13 '21 at 23:29
  • 1
    Assuming $p_k$ is the $k^{th}$ prime, the relevant keyword is primorial prime, see references under 1, 2. Otherwise, if $p_k$ are just distinct primes, see OEIS A039787 (primes $p$ such that $p-1$ is squarefree). – dxiv Jul 13 '21 at 23:35
  • Thanks guys. Yes, I was actually asking about OEIS A039787 - but now I think about it, Euclid's proof is about the first $k$ primes, so the primordial primes/ prime Euclid numbers seem more relevant. I also don't see anywhere saying the set OEIS A039787 is infinite. – Adam Rubinson Jul 13 '21 at 23:47
  • 1
    @AdamRubinson Euclid's proof, as described here, does not assume the primes used are the first $k$ primes. – stewbasic Jul 13 '21 at 23:49
  • Actually, when it says, "The density of this set in A000040 is Artin's constant A = A005596 = 37.39...%" does that mean the density across all prime numbers (and therefore the set is infinite?) – Adam Rubinson Jul 13 '21 at 23:50
  • Yes stewbasic - you are right. I guess a version with "first $k$ primes" also works as a proof, but it is not Euclid's proof. – Adam Rubinson Jul 13 '21 at 23:52

1 Answers1

1

If you don't require that $p_1, ..., p_k$ be distinct, then every single prime number is of the form $p_1 p_2 ... p_k+1$ (including 2 - take $k = 0$). In fact, every single number other than $1$ is of this form - just take the prime factorization of $n - 1$.

As for what happens when you require the primes to be distinct, I'm not sure.

John Bentin
  • 18,454
Mark Saving
  • 31,855