Advances in Pure Mathematics
Vol.08 No.07(2018), Article ID:86354,12 pages
10.4236/apm.2018.87041
There Are Infinitely Many Mersnne Composite Numbers with Prime Exponents
Fengsui Liu
Department of Mathematics, Nanchang University, Nanchang, China
Copyright © 2018 by author and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: May 5, 2018; Accepted: July 28, 2018; Published: July 31, 2018
ABSTRACT
By extending both arithmetical operations into finite sets of natural numbers, from the entire set of natural numbers successively deleting some residue classes modulo a prime, we invented a recursive sieve method or algorithm on natural numbers and their sets. The algorithm mechanically yields a sequence of sets, which converges to the set of all primes p such that 2p + 1 divides the Mersenne number Mp. The cardinal sequence corresponding to the sequence of sets is strictly increasing. So that we have captured enough usable structures, without any estimation, the existing theories of those structures allow us to prove an exact result: there are infinitely many Mersenne composite numbers with prime exponents Mp.
Keywords:
Mersenne Composite Numbers, Sophie German Primes, Recursive Algorithm, Order Topology, Limit of Sequence of Sets
1. Introduction
A Mersenne number is a number of the form
They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century.
If the exponent x is a composite number, obviously is a composite number. One only discusses the primality of a Mersenne number with a prime exponent.
On January 3, 2018, the Great Internet Mersenne Prime Search has discovered the largest known prime number, 277232917−1, having 23,249,425 digits. A computer volunteered by Jonathan Pace made the find on December 26, 2017 [1] .
One has a conjecture and an open problem about Mersenne numbers.
There are infinitely many Mersenne primes.
There are infinitely many Mersenne composite numbers.
In 1750 Euler stated and in 1775 Laglange proved the following theorem [2] .
Let is prime. Then is also primeif and only if divides Mp.
When p and both are prime, the prime p is said to be a Sophie Germain prime.
If we prove that there are infinitely many Sophie Germain primes of the form , then we prove that there are infinitely many Mersenne composite numbers.
In normal sieve theory, like the twin prime conjecture, it is hopeless to prove the Sophie German prime conjecture.
Primes have some obvious structures. We don’t know if they also have some additional structures. Because ofthis, we have been unable to settle many questions about primes [3] .
In 2014, Simon Davis provided a probabilistic proof of infinite extent of the sequence of Mersenne composite numbers with prime exponents [4] .
In 2011, author used the recursive sieve method, which reveals some exotic structures for sets of primes, to prove the Sophie Germain prime conjecture: there are infinitely many primes p such that is also prime [5] .
In this paper we extend the above structural result to prove: there are infinitely many Sophie Germain primes of the form , then we solve the open problem about Mersenne composite numbers.
In order to be self-contained, we repeat some contents in the paper [5] .
2. A Formal System
For expressing a recursive sieve method by well formed formulas, we extend both arithmetical operations addition +, multiplication × on natural numbers into finite sets of natural numbers.
We use small letters to denote natural numbers and capital letters to denote sets of natural numbers.
For arbitrary both finite sets of natural numbers we write
,
.
We define
, (2.1)
Example:
For the empty set we define and .
We write for the set difference of A and B.
Let
be several residue classes modulo a.
We define the solution of the system of congruences
,
to be
(2.2)
where is the solution of the system of congruences
If the greatest common divisor equals 1, by the Chinese remainder theorem, every solution exists with , every solution is computable and unique.
Except extending +, × into finite sets of natural numbers, we continue the traditional interpretation of the formal language 0, 1, +, ×, . The reader who is familiar with model theory may know, we have founded a new model or structure of second order arithmetic by a two-sorted logic
(2.3)
where N is the set of all natural numbers and is the power set of N.
We denote this model by .
Given a interpretation of the formal language 0, 1, +, ×, , the set of true sentences in , the theory of the model, is entirely determined. The entities in have intrinsic objective nature. Example the set of all primes p such that have intrinsic objective nature, infinite or not.
Mathematicians assume that is the standard model of Peano theory PA,
(2.4)
Similarly, we assume that is the standard model of a new arithmetical theory ,
. (2.5)
This is a joint theory of PA and ZF, in other words, is not only a model of Peano theory PA but also is a model of set theory ZF.
As a model of Peano theory PA the natural numbers in the model and the natural numbers in the model N are the same.
As a model of set theory ZF the natural numbers are atoms, urelements, or objects that have no element. We discuss sets of natural numbers and sets of sets of natural numbers.
The model and the theory construct a new formal system. In this formal system , we may formalize natural numbers and sets of natural numbers as individuals, terms, or points.
We do not know if the theory can solve the open problem, but we know that the new formal language 0, 1, +, ×, has more stronger expressive power. The new formal system has more richer mathematical structures.
In the formal system , we may introduce a recursive algorithm and produce some recursive sequences of sets. A new notation, the sequence of sets, reveals structures for some prime sets. Based on the theory and the existing theories of those structures, we can carefully construct a logical deduction, which is built into the structures of the natural numbers and their sets, to solve some old prime problems in pure mathematics.
“A well chosen notation can contribute to making mathematical reasoning itself easier, or even purely mechanical.” [6] .
We do not further discuss this formal system in view from logic and mathematical foundation
3. A Recursive Algorithm or Sieve Method
From the entire set of natural numbers successively deleting some residue classes modulo a prime, we invented a recursive sieve method or algorithm on natural numbers and their sets. Now we introduce the algorithm for Sophie Germain primes of the form .
Let be i-th prime, . For every prime , let
(3.1)
be the solution of the congruence
Example:
Let
(3.2)
From the residue class we successively delete the residue classes , , leave the residue class . Then the left residue class is the set of all numbers x of the form such that does not contain any prime as a factor .
Let
(3.3)
be the solution of the system of congruences
Let be the set of least nonnegative representatives of the left residue class .
In the formal system we obtain a recursive formula for the set , which describe the recursive algorithm or sieve method for Sophie Germain primes of the form .
(3.4)
The number of elements of the set is
(3.5)
We exhibit the first few terms of formula (3.4) and briefly prove that the algorithm is valid by mathematical induction.
The residue class is the set of all numbers x of the form . Now the set is equivalent to the set
,
from them we delete the solution of the system of congruences , and leave
The residue class is the set of all numbers x of the form such that . Now the set is equivalent to the set
from them we delete the solution of the system of congruences
and leave
The residue class is the set of all numbers x of the form such that . And so on.
Suppose that the residue class is the set of all numbers x of the form such that . We delete the residue class from them. In other words, we delete the solution of the system of congruences
Now the residue class is equivalent to the residue class
From them we delete the solution , which is the set of all numbers x of the form such that . It follows that the left residue class is the set of all numbers x of the form , and . Our algorithm is valid. It is easy to compute
by the above algorithm.
We may rigorously prove formulas (3.4) and (3.5) by mathematical induction, the proof is left to the reader.
In the next section we refine formula (3.4) and solve the open problem
4. A Main Theorem
We call a Sophie Germain primes of the form a S-prime.
Let be the set of all S-primes
. (4.1)
By the recursive sieve method we shall determine an additional exotic structure for the set based on the limit of a sequence of sets ( ),
Next we prove that the cardinality of the set is infinite by existing theories of those structures,
Based on the recursive algorithm, formula (3.4), we successively delete all numbers x of the form such that contains the least prime factor . We delete non S-primes or non S-primes together with a S-prime. The sifting condition or “sieve” is
(4.2)
We modify the sifting condition to be
(4.3)
According to this new sifting condition or “sieve”, we successively delete the set of all numbers x such that either x or is composite with the least prime factor ,
(4.4)
but remain the S-prime x if .
We delete all sets with from the set of all natural numbers x of the form , and leave the set
(4.5)
The set of all S-primes is
(4.6)
The recursive sieve (4.3) is a perfect tool, with this tool we delete all non S-primes and leave all S-primes. So that we only need to determine the number of all S-primes . If we do so successfully, then the parity obstruction, a ghost in house of primes, has been automatically evaporated.
With the recursive sieve (4.3), each non S-prime is deleted exactly once, there is need neither the inclusion-exclusion principle nor the estimation of error terms, which cause all the difficulty in normal sieve theory.
Let be the set of all S-primes x less than
. (4.7)
From the recursive formula (3.4), we deduce that the left set is the union of the set of S-primes and the residue class .
(4.8)
Now we intercept the initial segment from the left set , which is the union of the set of S-primes and the set of least nonnegative representatives. Then we obtain a new recursive formula
(4.9)
Except remaining all S-primes x less than in the initial segment , both sets and are the same.
For example
Note: the is a prime. For all S-prime , , the is a Mersenne composite number. Example: .
Formula (4.9) expresses the recursively sifting process according to the sifting condition (4.3), and provides a recursive definition of the initial segment . The initial segment is a well chosen notation. We shall consider some properties of the initial segment, and reveal some structures of the sequence of the initial segments to determine the set of all S-primes and its cardinality.
Let be the number of S-primes less than . Then the number of elements of the initial segment is
(4.10)
From formula (3.5) we deduce that the cardinal sequence is strictly increasing
(4.11)
Based on order topology obviously we have
(4.12)
Intuitively we see that the initial segment approaches the set of all S-primes , and the corresponding cardinality approaches infinity as . Thus the set of all S-primes is limit computable and is an infinite set.
Next we give a formal proof based on set theory and order topology
4.1. A Formal Proof
Let be the subset of all S-primes in the initial segment
. (4.13)
We consider the structures of both sequences of sets and to solve the open problem.
Lemma 4.1:
The sequence of the initial segments and the sequence of its subsets of S-primes both converge to the set of all S-primes .
First from set theory, next from order topology we prove this Lemma.
Proof:
For the convenience of the reader, we quote a definition of the set theoretic limit of a sequence of sets [7] .
Let be a sequence of sets, we define and as follows
(4.14)
(4.15)
It is easy to check that is the set of those elements x, which belongs to for infinitely many n. Analogously, x belongs to if and only if it belongs to for almost all n, that is it belongs to all but a finite number of the .
If
.
we say that the sequence of sets converges to the limit
. (4.16)
We know that the sequence of left sets is descending
(4.17)
According to the definition of the set theoretic limit of a sequence of sets, we obtain that the sequence of left sets converges to the set
(4.18)
The sequence of subsets of S-primes is ascending
(4.19)
We obtain that the sequence of subsets converges to the set ,
(4.20)
The initial segment is located between two sets and
(4.21)
Thus the sequence of the initial segments converges to the set
(4.22)
According to set theory, we have proved that both sequences of sets and converge to the set of all S-primes .
(4.23)
Next we prove that according to order topology both sequences of sets and converge to the set of all S-primes .
We quote a definition of the order topology [8] .
Let X be a set with a linear order relation; assume X has more one element. Let B be the collection of all sets of the following types:
1) All open intervals in X.
2) All intervals of the form , where is the smallest element (if any) in X.
3) All intervals of the form , where is the largest element (if any) in X.
The collection B is a bases of a topology on X, which is called the order topology.
According to the definition there is no order topology on the empty set or sets with a single element.
The recursively sifting process, formula (4.9), produces both sequences of sets together with the set theoretic limit point .
(4.24)
We further consider the structures of sets and using the recursively sifting process (4.9) as an order relation
(4.25)
The set has no repeated term. It is a well ordered set with the order type using the recursively sifting process (4.9) as an order relation. Thus the set may be endowed an order topology.
The set may have some repeated terms. We have computed out the first few S-primes x. The set contains more than one element, may be endowed an order topology using the recursively sifting process (4.9) as an order relation.
Obviously, for every neighborhood of there is a natural number , for all , we have and , thus both sequences of sets and converge to the set of all S-primes .
(4.26)
(4.27)
According to the order topology, we have again proved that both sequences of sets and converge to the set of all S-primes . We also have
(4.28)
The formula is a recursive asymptotic formula for the set of all S-primes .
end proof.
In general, if , the set only has a single element, which has no order topology. In this case formula (4.28) is not valid and our method of proof may be useless [5] .
Lemma 4.1 reveals an order topological structure and a set theoretic structure for the set of all S-primes on the recursive sequences of sets. Based on the existing theories of those structures, we easily prove that the cardinality of the set of all S-primes is infinite.
Theorem 4.2:
The set of all S-primes is an infinite set.
We give two proofs.
Proof A:
We consider the cardinalities and of sets on two sides of the equality (4.28), and the order topological limits of cardinal sequences and , as the sets and both tend to .
From general topology we know, if the limits of both cardinal sequences and on two sides of the equality (4.28) exist, then both limits are equal; if does not exist, then the condition for the existence of the limit is not sufficient [8] .
For S-primes, the set is nonempty, the formula (4.28) is valid, obviously the order topological limits and on two sides of the equality (4.28) exist, thus both limits are equal
(4.29)
From formula (4.12) we have
(4.30)
Usually let be the counting function, the number of S-primes less than or equal to n. Normal sieve theory is unable to provide non-trivial lower bounds of because the parity obstruction. Let n be a natural number. Then the number sequence is a subsequence of the number sequence (n), we have
(4.31)
By formula (4.13), the is the set of all S-primes less than , and the is the number of all S-primes less than , thus . We have
. (4.32)
From formula (4.30) we prove
(4.33)
We directly prove that the number of all S-primes is infinite with the counting function. Next we give another proof by the continuity of the cardinal function.
End proof.
Proof B:
Let be the cardinal function . from the order topological space X to the order topological space Y
(4.34)
It is easy to check that for every open set in Y the pre-image is also an open set in X. So that the cardinal function is continuous at with respect to the above order topology.
Both order topological spaces are first countable, hence the cardinal function is sequentially continuous. By a usual topological theorem [9] (Theorem 21.3, p130), the cardinal function preserves limits
(4.35)
Order topological spaces are Hausdorff spaces. In Hausdorff spaces the limit
point of the sequence of sets and the limit point of cardinal sequence
are unique.
We have proved Lemma 4.1, , and formula (4.12), . Substitute, we obtain that the set of all S-primes is an infinite set,
(4.36)
End proof.
By Euler-Lagrange theorem we have solved the open problem about Mersenne numbers.
Theorem 4.3:
There are infinitely many Mersenne composite numbers with prime exponents.
4.2. Conclusions
In pure mathematics, without any statistical data, without the Riemann hypothesis, by the recursive algorithm, we well understand the recursive structure, set theoretic structure and order topological structure for the set of all S-primes on sequences of sets. We choose a well notation, the sequences of set, which makes mathematical reasoning itself easier, or even purely mechanical. Then we obtain a formal proof of the open problem about Mersenne composites.
In general, we may discuss Shophe German primes of the form , then treat another prime problems, in this paper we do not discuss them.
Cite this paper
Liu, F.S. (2018) There Are Infinitely Many Mersnne Composite Numbers with Prime Exponents. Advances in Pure Mathematics, 8, 687-698. https://doi.org/10.4236/apm.2018.87041
References
- 1. GIMPS Project Discovers Largest Known Prime Number: . Mersenne Research, Inc. https://www.mersenne.org/primes/press/M77232917.htm
- 2. Tao, T. (2007) Open Question: The Parity Problem in Sieve Theory. http://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory
- 3. Davis, S. (2014) Arithmetical Sequences for the Exponents of Composite Mersenne Numbers. Notes on Number Theory and Discrete Mathematics, 20, 19-26.
- 4. Caldwell, C.K. Proof of a Result of Euler and Lagrange on Mersenne Divisors.http://primes.utm.edu/notes/proofs/MerDiv2.html
- 5. Liu, F.S. (2011) On the Sophie Germain Prime Conjecture. WSEAS Transactions on Mathematics, 10, 421-430.
- 6. Harrison, J. (2008) Formal Proof—Theory and Practice. Notices of AMS.http://www.ams.org/notices/200811/tx081101395p.pdf
- 7. Kuratowsky, K. and Mostowsky, A. (1976) Set Theory, with an Introduction to Descriptive Set Theory. North-Holland Publishing, 118-120.
- 8. Hazewinkel, M. Encyclopaedia of Mathematics, Limit. http://eom.springer.de/l/l058820.htm
- 9. Munkres, J.R. (2000) Topology. 2nd Edition, Prentice Hall, Upper Saddle River, 130.