Euclid proof of the infinitude of primes can be extended into this.

Assuming there is a finite number of primes, $k$, sort them in increasing order and split the series after any prime at $t$. Create the difference between the products of each group.

$$ \left | \prod_{t< m \leq k} p_m - \prod_{1 \leq n \leq t} p_n \right | $$

The result cannot be divisible by any used prime, therefore it has to be $1$.

There are $k-1$ differences in the form:

$$ P_k(t) = \prod_{t< m \leq k} p_m - \prod_{1 \leq n \leq t} p_n $$

and obviously:

$$ P_{k}(1) > P_{k}(2) > \cdots > P_k(k-1) $$

However, in this strictly monotonic series, we can have only once $-1$ and $1$, which means that as long as there are at least four primes there cannot be a finite number of primes. And we know four initial primes.

The question which comes naturally is:

Can you write every prime as a difference between split products of the full set of first $k$ primes?

$$ p_N = \left | \prod_{n \in J} p_n - \prod_{m \notin J} p_m \right |, J \subset \{1,2,...,k\}$$

It seems as we are adding more primes we have more combinations of the differences, closing to $2^m$ differences. However primorial function, the product of primes, grows as $m^m$ so it seems that it will quickly start skipping as we are going towards larger primes.

(I think there is only some hope if we loose the restriction and say that we are allowed to use two products of different set of primes, not necessarily the complete set, since then the number of combinations is somewhat larger, but it still does not look sufficient.)

Anyway, does the proof sound correct and what extension or restriction of this might still give us each prime?

(The proof here explicitly elaborates Euclid proof in the sense of what if we take that $p_1 p_2 \cdots p_n + 1=1$ which is actually the only option, but without using $+1$, which is, albeit trivial actually, constructed for the purpose of the proof, and then it discusses the actual number of initial primes we need in order to claim that there is an infinite number of them.)

(Euclid's proof has a small gap that is rarely mentioned. Notice that when you create $p_1p_2p_3...p_n$ you implicitly assume that there is at least one prime number and that all primes are positive. $p_1p_2p_3...p_n+1=1$ is perfectly valid in case you have no prime numbers, and if primes can be negative everything falls apart. This is all elementary, but it is still a small gap.)

  • 2
    $\begingroup$ It is easy to anticipate what you mean, but the notation is suboptimal, I think. How about, splitting into two disjoint subsets $I,J$, and considering $|\prod_{p\in I} p - \prod_{q\in J} q|$ or some such? $\endgroup$ Aug 20 at 20:40
  • $\begingroup$ @paulgarrett It is clumsy whichever way. to be honest, but I will try $\endgroup$
    – user113386
    Aug 20 at 20:42
  • 1
    $\begingroup$ At least if you use $I,J$ the notation makes sense, unlike now where you use $m,n$ both as some fixed elements and as variables over which products range. $\endgroup$
    – Wojowu
    Aug 20 at 20:50
  • $\begingroup$ @Wojowu I am trying... hold a moment, and I will keep m,n to be clear that they are different even more. $\endgroup$
    – user113386
    Aug 20 at 20:57
  • $\begingroup$ I reduced it all to what the proof really needs. $\endgroup$
    – user113386
    Aug 21 at 16:21

See Guy, Lacampagne, and Selfridge, Primes at a Glance, Mathematics of Computation, volume 48, number 177, January 1987, pages 183-202.

Abstract. Let $N = B - L$, $B \ge L$, $\gcd(B,L) = 1$, $p \mid BL$ for all primes $p\le\sqrt N$. Then $N$ is $0,1$ or a prime. Writing $N$ in this form suggests a primality and a squarefreeness test. If we also require that when the prime $q \mid BL$ and $p < q$ then $p \mid BL$, we say that $B - L$ is a presentation of $N$. We list all presentations found for any $N$. We believe our list is complete.

There is also Takashi Agoh, Paul Erdős and Andrew Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10 (Dec., 1997), pp. 943-945.

  • $\begingroup$ Yeah, that is close to what I was asking. Pity it is jumbled about couple of related methods by execution but not by result. It is kind of investigating unrelated curiosities some of which work, some not. But the tests are super simple for small primes, you can do it in your head. $\endgroup$
    – user113386
    Aug 21 at 2:14
  • 1
    $\begingroup$ "Jumbled"? Given squarefree $N$ let $(a_1,b_1), (a_2,b_2),\dots$ be the pairs of positive integers for which $a_jb_j=N$ with $b_j\geq a_j$ and $b_1-a_1<b_2-a_2<\dots$ (eg N is the product of the first $k$ primes). Now if $j>1$ then $b_j-a_j>b_j-b_1> gcd(b_j,b_1)$ and similarly $b_j-a_j>b_j-a_1> gcd(b_j,a_1)$. Therefore $(b_j-a_j)^2>gcd(b_j,b_1) \cdot gcd(b_j,a_1) = gcd(b_j,N)=b_j>\sqrt{N}$. Therefore $b_2-a_2>N^{1/4}$. That should help unjumble your thoughts! $\endgroup$ Sep 1 at 14:20

Your idea is quite closely related to an early paper of John Thompson: "A method for finding primes"- American Mathematical Monthly 60,(1953), p175, see also MR 0052448. I believe that it was later pointed out that it is not possible to express each prime as such a difference.

  • $\begingroup$ Yeah, he is talking about the same thing. I just extended it into an explicit proof and then ask questions about prime numbers in it. No, it does not seem possible, but it is the system of creating new primes nevertheless. $\endgroup$
    – user113386
    Aug 20 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy