This argument laid the foundation for this investigation. See also this arXiv preprint, and this broader update.

Abstract We define the residues $r_{i}(n)$ for all $n \geq 2$ and all $i \geq 2$ such that $r_{i}(n) = 0$ if, and only if, $i$ is a divisor of $n$. We then show that the joint probability $\mathbb{P}(p_{i} | n\ \cap\ p_{j} | n)$ of two unequal primes $p_{i},\ p_{j}$ dividing any integer $n$ is the product $\mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n)$. We conclude that the prime divisors of any integer $n$ are independent; and that the probability $\mathbb{P}(n \in \{p\})$ of $n$ being a prime $p$ is $\prod_{i = 1}^{\sqrt{n}}(1 - 1/p_{i}) \sim 2e^{-\gamma}/log_{e}\ n$. The number of primes less than or equal to $n$ is thus given by $\pi(n) \approx \sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})$. We further show that $((\pi(x).log_{e}\ x)/x)' = o(1/x)$, and conclude that $(\pi(x).log_{e}\ x)/x$ does not oscillate.

$\S 1$ The residues $r_{i}(n)$

We begin by defining the residues $r_{i}(n)$ for all $n \geq 2$ and all $i \geq 2$ as below:

Definition 1: $n + r_{i}(n) \equiv 0\ (mod\ i)$ where $i > r_{i}(n) \geq 0$.

Since each residue $r_{i}(n)$ cycles over the $i$ values $(i-1, i-2, \ldots, 0)$, these values are all incongruent and form a complete system of residues [1] $mod\ i$.

It immediately follows that:

Lemma 1: $r_{i}(n) = 0$ if, and only if, $i$ is a divisor of $n$.

$\S 2$ The probability $\mathbb{P}(e)$

By the standard definition of the probability $\mathbb{P}(e)$ of an event $e$, we conclude that:

Lemma 2: For any $n \geq 2,\ i \geq 2$ and any given integer $i > u \geq 0$, the probability $\mathbb{P}(r_{i}(n) = u)$ that $r_{i}(n) = u$ is $1/i$, and the probability $\mathbb{P}(r_{i}(n) \neq u)$ that $r_{i}(n) \neq u$ is $1 - 1/i$.

We note the standard definition:

Definition 2: Two events $e_{i}$ and $e_{j}$ are mutually independent for $i \neq j$ if, and only if, $\mathbb{P}(e_{i}\ \cap\ e_{j}) = \mathbb{P}(e_{i}).\mathbb{P}(e_{j})$.

$\S 3$ The prime divisors of any integer $n$ are mutually independent

We then have that:

Lemma 3: If $p_{i}$ and $p_{j}$ are two primes where $i \neq j$ then, for any $n \geq 2$, we have:

$\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = \mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v)$

where $p_{i} > u \geq 0$ and $p_{j} > v \geq 0$.

Proof: The $p_{i}.p_{j}$ numbers $v.p_{i} + u.p_{j}$, where $p_{i} > u \geq 0$ and $p_{j} > v \geq 0$, are all incongruent and form a complete system of residues [2] $mod\ (p_{i}.p_{j})$. Hence:

$\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = 1/p_{i}.p_{j}$.

By Lemma 2:

$\mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v) = (1/p_{i})(1/p_{j})$.

The lemma follows. $\Box$

If $u = 0$ and $v = 0$ in Lemma 3, so that both $p_{i}$ and $p_{j}$ are prime divisors of $n$, we conclude by Definition 2 that:

Corollary 1: $\mathbb{P}((r_{p_{_{i}}}(n) = 0) \cap (r_{p_{_{j}}}(n) = 0)) = \mathbb{P}(r_{p_{_{i}}}(n) = 0).\mathbb{P}(r_{p_{_{j}}}(n) = 0)$.

Corollary 2: $\mathbb{P}(p_{i} | n\ \cap\ p_{j} | n) = \mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n)$.

Theorem 1: The prime divisors of any integer $n$ are mutually independent. [3]

$\S 4$ The probability that $n$ is a prime

Since $n$ is a prime if, and only if, it is not divisible by any prime $p \leq \sqrt{n}$, it follows immediately from Lemma 2 and Lemma 3 that:

Lemma 4: For any $n \geq 2$, the probability $\mathbb{P}(n \in \{p\})$ of an integer $n$ being a prime $p$ is the probability that $r_{p_{_{i}}}(n) \neq 0$ for any $1 \leq i \leq k$ if $p_{k}^{2} \leq n < p_{k+1}^{2}$. $\Box$

Lemma 5: $\mathbb{P}(n \in \{p\}) = \prod_{i = 1}^{\pi(\sqrt{n})}(1 - 1/p_{i}) \sim 2e^{-\gamma}/log_{e}\ n$ [4]. $\Box$

$\S 5$ The Prime Number Theorem

The number of primes less than or equal to $n$ is thus given by:

Lemma 6: $\pi(n) \approx \sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})$. $\Box$

This now yields the Prime Number Theorem:

Theorem 2: $\pi(x) \sim x/log_{e}\ x$.

Proof: From Lemma 6 and Mertens’ Theorem that
[5]:

$\prod_{p \leq x}(1 - 1/p_{i}) = e^{o(1)}.e^{-\gamma}/log_{e}\ x$

it follows that:

$(\pi(n).log_{e}\ n)/n \approx (log_{e}\ n/n)\sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})$

$(\pi(n).log_{e}\ n)/n \approx (log_{e}\ n/n)\sum_{j = 1}^{n}(2.e^{o(1)}.e^{-\gamma})/log_{e}\ n$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)\int_{2}^{x}(1/log_{e}\ t).dt$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)[log_{e}.log_{e}\ t + log_{e}\ t + \sum_{2}^{\infty}(log_{e}\ t)^{k}/(k. k!)]_{2}^{^{x}}$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)[log_{e}.log_{e}\ x + log_{e}\ x + \sum_{2}^{\infty}(log_{e}\ x)^{k}/(k. k!)]$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x).f(log_{e}\ x)$

The behaviour of $(\pi(x).log_{e}\ x)/x$ as $x \rightarrow \infty$ is then seen by differentiating the right hand side, where we note that $f(log_{e}\ x)' = 1/log_{e}\ x$:

$(c.(log_{e}\ x/x).f(log_{e}\ x))' = c/x + c.f(log_{e}\ x).(1/x^{2} - log_{e}\ x/x^{2})$

$(c.(log_{e}\ x/x).f(log_{e}\ x))' = c/x + (c.f(log_{e}\ x).(1 - log_{e}\ x))/x^{2}$

$(c.(log_{e}\ x/x).f(log_{e}\ x))' = o(1/x)$

Hence $(\pi(x).log_{e}\ x)/x$ does not oscillate as $x \rightarrow \infty$. $\Box$

Acknowledgements

I am indebted to my erstwhile classmate, Professor Chetan Mehta, for his unqualified encouragement and support for my scholarly pursuits over the past fifty years; most pertinently for his patiently critical insight into the required rigour without which the argument of this 1964 investigation would have remained in the informal universe of seemingly self-evident truths.

References

HW60 G. H. Hardy and E. M. Wright. 1960. An Introduction to the Theory of Numbers 4th edition. Clarendon Press, Oxford.

Ti51 E. C. Titchmarsh. 1951. The Theory of the Riemann Zeta-Function. Clarendon Press, Oxford.

Notes

Return to 3: In the previous post we have shown how it immediately follows from Theorem 1 that integer factorising is necessarily of order $O(n/log_{e}\ n)$; from which we conclude that integer factorising cannot be in the class $P$ of polynomial-time algorithms.