*This argument laid the foundation for this later post and this investigation.*

(*Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.*)

* Abstract*: We show the joint probability that two unequal primes divide any integer is the product . We conclude that the prime divisors of any integer are independent; and that Integer Factorising is necessarily of the order .

** The residues **

We define the residues for all and all as below:

**Definition 1:** where .

Since each residue cycles over the values , these values are all incongruent and form a complete system of residues ^{[1]} .

We note that:

**Lemma 1:** if, and only if, is a divisor of .

** The probability **

By the standard definition of the probability ^{[2]} of an event , we then have that:

**Lemma 2:** For any and any given integer , the probability that is , and the probability that is .

We note the standard definition ^{[3]}:

**Definition 2:** Two events and are mutually independent for if, and only if, .

** The prime divisors of any integer are mutually independent**

We then have that:

**Lemma 3:** If and are two primes where then, for any , we have:

where and .

**Proof:** The numbers , where and , are all incongruent and form a complete system of residues ^{[4]} . Hence:

.

By Lemma 2:

.

The lemma follows.

If and in Lemma 3, so that both and are prime divisors of , we conclude by Definition 2 that:

**Corollary 1:** .

**Corollary 2:** .

**Theorem 1:** The prime divisors of any integer are mutually independent.

Since is a prime if, and only if, it is not divisible by any prime we may, without any loss of generality, take integer factorising to mean determining at least one prime factor of any given .

** Integer Factorising is not in **

It then immediately follows from Theorem 1 that:

**Corollary 3:** Integer Factorising is not in .

**Proof:** We note that any computational process to identify a prime divisor of must necessarily appeal to a logical operation for identifying such a factor.

Since may be the square of a prime, it follows from Theorem 1 that we necessarily require at least one logical operation for each prime in order to logically identify a prime divisor of .

Moreover, since the number of such primes is of the order , any deterministic algorithm that always computes a prime factor of cannot be polynomial-time—i.e. of order for any —in the length of the input .

The corollary follows if is the set of such polynomial-time algorithms.

**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**

**GS97** Charles M. Grinstead and J. Laurie Snell. 1997. *Introduction to Probability.* Second Revised Edition, 1997, American Mathematical Society, Rhode Island, USA.

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

**Ko56** A. N. Kolmogorov. 1933. *Foundations of the Theory of Probability.* Second English Edition. Translation edited by Nathan Morrison. 1956. Chelsea Publishing Company, New Yourk.

**An05** Bhupinder Singh Anand. 2005. *Three Theorems on Modular Sieves that suggest the Prime Difference is .* Private investigation.

**Notes**

Return to 1: HW60, p.49.

Return to 2: Ko56, Chapter I, Section 1, Axiom III, p.2; see also GS97, Chapter 1, Section 1.2, Definition 1.2, p.19.

Return to 3: Ko56, Chapter VI, Section 1, Definition 1, pg.57 and Section 2, pg.58; see also GS97, Chapter 4, Section 4.1, Theorem 4.1, pg.140.

Return to 4: HW60, p.52, Theorem 59.

## Leave a comment

Comments feed for this article