You are currently browsing the tag archive for the ‘modular arithmetic’ tag.

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

1. Since, by the Prime Number Theorem, the number of primes is , it would follow that determining a factor of requires at least one logical operation for each prime , and therefore cannot be done in polynomial time—whence —** IF** whether or not a prime divides an integer were independent of whether or not a prime divides the integer .

2. Currently, conventional approaches to determining the computational complexity of *Integer Factorising* apparently appeal critically to the belief that:

(i) either—explicitly (see *here*)—that whether or not a prime divides an integer is ** not** independent of whether or not a prime divides the integer ;

(ii) or—implicitly (since the problem is yet open)—that a proof to the contrary must imply that if is the probability that is a prime, then .

3. If so, then conventional approaches seem to conflate the two probabilities:

(i) The probability of *selecting* a number that has the property of being prime from a *given* set of numbers;

*Example 1*: I have a bag containing numbers in which there are twice as many composites as primes. What is the probability that the first number you blindly pick from it is a prime. This is the basis for setting odds in games such as roulette.

(ii) The probability of *determining* that a *given* integer is prime.

*Example 2*: I give you a -digit combination lock along with a -digit number . The lock only opens if you set the combination to a proper factor of which is greater than . What is the probability that the first combination you try will open the lock. This is the basis for RSA encryption, which provides the cryptosystem used by many banks for securing their communications.

4. In case 3(i), if the precise proportion of primes to non-primes in is definable, then clearly too is definable.

However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, *here*).

5. In case 3(ii) the following paper proves , since it shows that whether or not a prime divides a given integer ** is** independent of whether or not a prime divides :

*Why Integer Factorising cannot be polynomial time*

Not only does it immediately follow that (see *here*), but we further have that , with a binomial standard deviation. Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the de facto probability that a given is prime, with all its attended consequences for various prime-counting functions and the Riemann Zeta function (see *here*).

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

Abstract We define the residues for all and all such that if, and only if, is a divisor of . We then show that the joint probability of two unequal primes dividing any integer is the product . We conclude that the prime divisors of any integer are independent; and that the probability of being a prime is . The number of primes less than or equal to is thus given by . We further show that , and conclude that does not oscillate.

** The residues **

We begin by defining 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]} .

It immediately follows that:

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

** The probability **

By the standard definition of the probability of an event , we conclude that:

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

We note the standard definition:

**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 ^{[2]} . 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. ^{[3]}

** The probability that is a prime**

Since is a prime if, and only if, it is not divisible by any prime , it follows immediately from Lemma 2 and Lemma 3 that:

**Lemma 4:** For any , the probability of an integer being a prime is the probability that for any if .

**Lemma 5:** ^{[4]}.

** The Prime Number Theorem**

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

**Lemma 6:** .

This now yields the Prime Number Theorem:

**Theorem 2:** .

**Proof:** From Lemma 6 and Mertens’ Theorem that

^{[5]}:

it follows that:

The behaviour of as is then seen by differentiating the right hand side, where we note that :

Hence does not oscillate as .

**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 1: HW60, p.49.

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

Return to 3: In the previous post we have shown how it immediately follows from Theorem 1 that integer factorising is necessarily of order ; from which we conclude that integer factorising cannot be in the class of polynomial-time algorithms.

Return to 4: By HW60, p.351, Theorem 429, Mertens’ Theorem.

Return to 5: By the argument in Ti51, p.59, eqn.(3.15.2).

Return to 6: HW60, p.9, Theorem 7.

## Recent comments