# Proof of infinitude of primes using ratio of n to its totient

A few preliminaries:

A primorial is the product of the first primes. There are two notations for this ($$n\#$$ is the product of all primes under $$n$$, and $$p_n\#$$ is the product of the first $$n$$ primes; I use the second notation).

A $$k$$-rough integer is an integer that only has factors that are larger than or equal to $$k$$. It is important to note that the minimum difference between consecutive $$k$$-rough multiples of $$k$$ is $$2k$$ when $$k$$ is prime (see another of my questions here: Minimum difference between consecutive multiples of $k$ that are $k\text{-rough}$).

I came across this gem: On a ratio between a number and it's totient . Consider: the ratio $$\frac{n}{\varphi(n)}$$ gives the average gap between the elements of the reduced residue system modulo $$n$$.

Now for the meat of the question:

Consider the primorial $$p_n \#$$; using this as the input for the above ratio gives us the average gap between $$k$$-rough integers in the range $$[1, p_n \#]$$. Recall that we need only prove a number is not divisible by any prime smaller than or equal to its square root to show that that number is prime. If $$k = p_{n+1}$$, any $$k$$-rough integer in the range $$(p_n, p_{n+1}^2)$$ must be prime.

EDIT (everything below this has been added or edited from the original question for clarity and completeness).

For primorial inputs, we can simplify Euler's totient function to: $$\varphi(p_n \#) = \prod_{i=1}^n (p_i - 1)$$. This becomes important for the limit below.

Let's take the limit:

$$\lim_{n \to \infty}\left(2p_{n+1}-\frac{p_n\#}{\varphi(p_n\#)}\right)$$

This limit is the difference between the smallest-possible gap between consecutive $$k$$-rough multiples of $$k$$ if $$k = p_{n+1}$$, and the average gap between the elements of the reduced residue system modulo $$p_n \#$$. We could replace the first part of this limit with $$p_n^2 - p_n$$, but I find the form written here to be much more strict in range and it accomplishes more or less the same goal.

We can replace the totient function with the simplified form:

$$\lim_{n \to \infty}\left(2p_{n+1}-\frac{p_n\#}{\prod_{i=1}^n (p_i - 1)}\right)$$

I note that the primes are very difficult to work with in calculus, so I re-write the above limit to remove dependence on primes and come up with something very similar which is much easier to work with:

$$\lim_{n \to \infty}\left(2(n+1)-\frac{n!}{\prod_{i=2}^n (i - 1)}\right)$$ $$= \lim_{n \to \infty}\left(2(n+1) - \frac{n!}{(n-1)!}\right)$$ $$= \lim_{n \to \infty}\left(2(n+1) - n \right)$$ $$= \lim_{n \to \infty} n + 2 = \infty$$

I believe this limit stands regardless of the subset of the positive integers we choose to use in the products so long as the same set is used in both functions in the difference (correct me if I'm wrong on that).

So: does this approach stand as a valid proof of the infinitude of the primes? (I guess I should also include in this: is my calculus valid?)

Here is why I'm interested in this: the simplified form of Euler's totient function can also be modified in other ways. For example:

$$(\prod_{i=3}^n (p_i - 2)) - 1$$

...counts the number of translations of the $$k$$-tuple $$(0, 2)$$ (twins) among the residues modulo $$p_n\#$$. In fact, if we pick the right starting point for this product, we can substitute in any $$k$$ as the subtrahend and start the product out at the first prime that is at least half as large as the diameter (difference between the largest and smallest elements) of our target $$k$$-tuple. A few other minor details need to be accounted for, such as the initial number of $$k$$-tuples in the residues, but this product can be used to count the number of any admissible $$k$$-tuple among the residues modulo primorials that are large enough relative to the target $$k$$-tuple. The interesting thing is that all of these minor details pretty much account for nothing when $$n$$ goes to infinity; the limit remains the same.

We know:

1. there are infinitely many primes, so this means that 1-tuples fall into the provably-prime interval for $$k$$-rough integers in their corresponding primorial residues, so this happens infinitely often.
2. the distribution of any $$k$$-tuple, when $$n$$ goes to infinity, among the residues modulo primorials, behaves in exactly the same way as the distribution of $$1$$-tuples.

So: 1-tuples fall into the provably-prime interval infinitely often, and the distribution of these behaves exactly like the distribution of any $$k$$-tuple among the residues modulo primorials. So: If there are infinitely many 1-tuples, there must also be infinitely many $$k$$-tuples for any $$k$$ because any other result would be contradictory to our observation that this limit applies equally well to all $$k$$-tuples.

All of this seems far too simple for it to have been missed, so I conclude I must be missing something or my logic is incomplete or impossible in some way, and I'm trying to figure out what that is so this can stop driving me nuts.

• You seem to already be assuming an infinity of primes when you write $\lim_{n\to\infty}(2p_{n+1} - \cdots)$? – joriki Dec 29 '19 at 8:48
• Not necessarily. You can establish that same limit by replacing primorials with factorials; in either case, the density of the set of numbers you use doesn't much matter. – Adam Dec 29 '19 at 8:55
• I don't understand. That limit contains the $(n+1)$-th prime. I don't know in what sense "that same limit" could be established without those primes. Please elaborate. – joriki Dec 29 '19 at 8:57
• If we replace references to primes and their corresponding primorials with integers and their corresponding factorials, we can instead write: $\lim_{n \to \infty} \left( 2(n+1) - \frac{n!}{\varphi(n!)}\right)$. We could find a suitable replacement function as a stand-in for the totient function much as we use factorials as a stand-in for the primorials; essentially, we can substitute our way through the limit to show that the substitutes diverge, and therefore the originals must also diverge to positive infinity. – Adam Dec 29 '19 at 9:06
• I'm afraid I still don't understand. You claim that a specific sequence involving primes and primorials diverges. This is a different sequence than the one in your comment. I don't see how you're trying to infer the divergence of the former from the divergence of the latter. Perhaps you could flesh this out as part of the question? – joriki Dec 29 '19 at 9:16

So, $$\lim_{n \to \infty} f(n)$$ evaluated when $$f(n)$$ exists for all $$n$$, even if it is constant. But assuming $$f(n) = \left(2p_{n+1}-\frac{p_n\#}{\prod_{i=1}^n (p_i - 1)}\right)$$ exists for large $$n$$ ($$\infty$$).
Already proves that $$p_{\infty}$$ exists, hence infinitude of primes proved.