\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Two Mersenne Prime Conjectures}
\vskip 1cm
\large
Samuel S. Wagstaff, Jr.\\
Center for Education and Research in Information Assurance and Security\\
and\\
Department of Computer Sciences\\
Purdue University\\
West Lafayette, IN 47907-1398\\
USA \\
\href{mailto:ssw@cerias.purdue.edu}{\tt ssw@cerias.purdue.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
We discuss two conjectures about Mersenne numbers,
an old one and a new one.
Heuristic arguments support both conjectures.
\end{abstract}

\section{Introduction}
The Mersenne numbers,
Sequence \seqnum{A083420} in the
{\it On-Line Encyclopedia of Integer Sequences}
(OEIS) \cite{OEIS},
are the integers $M_p=2^p-1$ for all primes $p$.
If $M_p$ is prime, then $p$ must be prime.
These exponents $p$ form Sequence \seqnum{A000043}
and the prime $M_p$ are Sequence \seqnum{A000668}.
There are only 52 primes $p$ for which $M_p$ is known to be prime.
Mersenne numbers have been studied for centuries.
We recall a conjecture about them made in 1989 and then
examine a new conjecture made in 2025.
We give evidence that both conjectures are probably true.

\section{The 1989 New Mersenne Conjecture} \label{newmc}
In 1644, Mersenne made a famous conjecture about which Mersenne
numbers with $1<p\le257$ are prime.
In 1989, Bateman, Selfridge, and the author \cite{BSW} made the
following conjecture about Mersenne numbers that might help
explain how Mersenne made his conjecture.
See \cite{BSW} for details.

\begin{conjecture}
If two of the following statements about
an odd positive integer $p$ are true, then the third one is also true.
\begin{enumerate}
 \item[(a)] $p=2^k\pm1$ or $p=4^k\pm3$ for some positive integer $k$.
 \item[(b)] $M_p$ is prime.
 \item[(c)] $(2^p+1)/3$ is prime.
\end{enumerate}
\end{conjecture}

The prime numbers $(2^p+1)/3$ in (c) are Sequence \seqnum{A000979}
(Wagstaff primes) and their exponents $p$ are Sequence \seqnum{A000978}.
This conjecture holds in the range of all known Mersenne primes,
that is, for $p$ up to about $10^8$.
It is easy to find examples in this range where exactly 0, 1, or 3
of the statements hold.
All three of the statements are true when $p<10^8$ only for $p=3$, $5$,
$7$, $13$, $17$, $19$, $31$, $61$, and $127$ (Sequence \seqnum{A107360}).
The sequence of $p$ in Statement (a) clearly grows exponentially.
A heuristic argument by the author \cite{Wag83} concludes that the
sequence of $p$ in Statement (b) also grows exponentially.
A similar heuristic argument by Bateman, Selfridge, and the author
\cite{BSW} says that the sequence
of $p$ in Statement (c) grows exponentially.
The heuristic argument in support of the
New Mersenne Conjecture is that the intersection of two
sequences of random integers that grow exponentially is
likely empty or at least finite.
Thus, if there is no $p$ between $128$ and $10^8$ for which more
than one statement holds, then probably there is no larger such $p$.
We expect that all three statements hold only for the nine
primes $p$ mentioned above and that no more than one statement
is true for each $p>127$.
See the web pages \cite{Mplus} and \cite{NewM} for recent work
on this conjecture.  

\section{Chen's Mersenne Conjecture of 2025} \label{chenconj}
Fermat's little theorem implies that $M_p\equiv1\pmod{p}$ if $p$ is prime.
(We have $2^{p-1}\equiv1\pmod{p}$, so $2^p\equiv2\pmod{p}$
and $M_p=2^p-1\equiv2-1=1\pmod{p}$.)
Recently, Chen \cite{Chen} made this conjecture.

\begin{conjecture}
If $M_p$ is prime, then it is the smallest Mersenne prime $\equiv1\pmod{p}$.
\end{conjecture}

If the conjecture were false for $M_p$, then there would be a prime $q<p$
such that $M_q$ is prime and $M_q\equiv1\pmod{p}$.
Chen \cite{Chen} writes

\begin{quote}
For example, $M_{127}$ is prime, and it is the smallest Mersenne
prime $\equiv1\pmod{127}$.
Although $M_{29}$, $M_{43}$, $M_{71}$, and $M_{113}$ are all
$\equiv1\pmod{127}$, none of these Mersenne numbers is prime,
so $M_{127}$ is not a counterexample.
Also, $M_{17}$ is a Mersenne prime $\equiv1\pmod{257}$, but $M_{257}$
is not prime, so $M_{257}$ is not a counterexample either.
\end{quote}

One can construct other false counterexamples
if one assumes that certain composite Mersenne numbers are prime.
True counterexamples might occur if certain double Mersenne numbers
are prime (Sequence \seqnum{A103901}).
For example, $2^{89}\equiv1\pmod{2^{89}-1}$
because $M_{89}$ is prime.  Since 89 divides 19936, we have
$2^{19936}\equiv1\pmod{2^{89}-1}$,
so $M_{19937}=2^{19937}-1\equiv1\pmod{M_{89}}$.
If $M_{M_{89}}$ is prime, then it would be a counterexample to
Chen's conjecture because the earlier Mersenne prime $M_{19937}$
is also $\equiv1\pmod{M_{89}}$.
Since $86243\equiv1\pmod{107}$, if $M_{M_{107}}$ is prime,
it and $M_{86243}$ would give another counterexample.

We used the list \cite{Mf} of all 52 known Mersenne primes
to check that there is no counterexample with one of these
numbers as $M_p$.
We next describe how we performed this check.

For prime $p$, let $n_p$ be the order of $2$ modulo $p$.
That is, $n_p$ is the smallest positive integer $n$ for which
$2^n\equiv1\pmod{p}$.
If $q<p$ and $M_q$ is a counterexample to the conjecture
for $M_p$, then
$2^q-1=M_q\equiv1\pmod{p}$ or $2^q\equiv2\pmod{p}$.
Since $p$ must be odd we have $2^{q-1}\equiv1\pmod{p}$,
so $n_p$ divides $q-1$.
For each known Mersenne prime $M_p$ with odd $p$ we computed $n_p$.
These values are shown in Table 1.
This table also shows the ratio $t_p=(p-1)/n_p$ to be used later.
We checked that for each $p$ in Table 1, $n_p$ does not
divide $q-1$ for each Mersenne prime $M_q$ with $q<p$.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|r r r|r r r|r r r|} \hline
$p$ & $n_p$ & $t_p$ & $p$ & $n_p$ & $t_p$ & $p$ & $n_p$ & $t_p$\strut \\ \hline
3 & 2 & 1 &		4253 & 4252 & 1 &	2976221 & 2976220 & 1 \\
5 & 4 & 1 &		4423 & 737 & 6 &	3021377 & 1510688 & 2 \\
7 & 3 & 2 &		9689 & 4844 & 2 &	6972593 & 871574 & 8 \\
13 & 12 & 1 &		9941 & 9940 & 1 &	13466917 & 4488972 & 3 \\
17 & 8 & 2 &		11213 & 11212 & 1 &	20996011 & 6998670 & 3 \\
19 & 18 & 1 &		19937 & 9968 & 2 &	24036583 & 12018291 & 2 \\
31 & 5 & 6 &		21701 & 21700 & 1 &	25964951 & 12982475 & 2 \\
61 & 60 & 1 &		23209 & 967 & 24 &	30402457 & 1266769 & 24 \\
89 & 11 & 8 &		44497 & 2781 & 16 &	32582657 & 1018208 & 32 \\
107 & 106 & 1 &		86243 & 86242 & 1 &	37156667 & 1955614 & 19 \\
127 & 7 & 18 &		110503 & 6139 & 18 &	42643801 & 21321900 & 2 \\
521 & 260 & 2 &		132049 & 11004 & 12 &	43112609 & 10778152 & 4 \\
607 & 303 & 2 &		216091 & 43218 & 5 &	57885161 & 28942580 & 2 \\
1279 & 639 & 2 &	756839 & 378419 & 2 &	74207281 & 7420728 & 10 \\
2203 & 734 & 3 &	859433 & 61388 & 14 &	77232917 & 77232916 & 1 \\
2281 & 190 & 12 &	1257787 & 139754 & 9 &	82589933 & 82589932 & 1 \\
3217 & 804 & 4 &	1398269 & 1398268 & 1 & 136279841 & 13627984 & 10 \\ \hline
\end{tabular}
\caption{Order of $2$ modulo $p$ for Mersenne prime exponents}
\label{tablenp}
\end{center}
\end{table}

Now we offer a heuristic argument similar to that in Section \ref{newmc}
to support Chen's conjecture.

Now $t_p=1$ if and only if $2$ is a primitive root modulo $p$,
and this is the most popular value for $t_p$.
Note that $t_p$ is usually a small positive integer.
Assuming the Generalized Riemann Hypothesis
one can compute, for each positive integer $t$, the fraction of all
primes $p$ for which $t_p=t$.
The answer is stated for general base $a$ as Theorem 2.2 of
Wagstaff \cite{Wag82} and specifically for $a=2$ in the first
example on Page 143 of that paper.  The fraction for $t$ is 
$c(t)/t^2$, where $c(t)$ is a positive constant that depends only
on the residue class of $t$ modulo 8.  As $t$ increases,
the fractions decrease in proportion to $t^{-2}$.
Since $t_p$ is small for most primes $p$, $n_p$ is almost
always a large fraction of $p$.

If $M_q$ is a counterexample to Chen's conjecture
for $M_p$, then $q$ must satisfy all four of these conditions:
\begin{enumerate}
 \item[(a)] $2<q<p$,
 \item[(b)] $q$ is prime,
 \item[(c)] $M_q$ is prime, and
 \item[(d)] $n_p$ divides $q-1$.  
\end{enumerate}
We noted in Section \ref{newmc} that the sequence of $q$
for which $M_q$ is prime grows exponentially, so it has
few members in the interval $n_p-2<q<p$.
Since $n_p$ is a large integer
these four conditions on $q$ make it
very unlikely that Chen's conjecture is false.

On January 16, 2011, Joerg Arndt added this comment to the OEIS Sequence
\seqnum{A000043} of exponents $p$ with $M_p$ prime.
\begin{quote}
The (prime) number $p$ appears in this sequence if and
only if there is no prime $q<2^p-1$ such that the order
of $2$ modulo $q$ equals $p$; \ldots.
\end{quote}
This statement uses some of the words in this section, but it is not
a restatement of Chen's conjecture.
Our definition of {\em order of} $2$ {\em modulo} $q$ requires the
order to be $<q$.  Arndt uses an alternate definition of this
order as a positive integer $n$ for which $2^n\equiv1\pmod{q}$.
With this definition it is easy to prove (the contrapositive of) his comment:
If $M_p$ is composite, then some prime $q<2^p-1$ divides $M_p=2^p-1$,
so $2^p\equiv1\pmod{q}$.
If some prime $q<2^p-1$ satisfies $2^p\equiv1\pmod{q}$, then $q$
divides $2^p-1=M_p$, so $M_p$ is composite.

\section{Acknowledgments}
I am grateful to the CERIAS Center at Purdue University for
their support of this work.
I thank Xinyao Chen for helpful comments about earlier versions
of this paper.

\begin{thebibliography}{1}

\bibitem{BSW}
  P. T. Bateman, J. L. Selfridge, and S. S. Wagstaff, Jr.,
  The Editor's Corner: The new Mersenne conjecture,
  \textit{Amer. Math. Monthly} {\bf 96} (1989), 125--128.

\bibitem{Chen}
Xinyao Chen.
\newblock Personal communication, August 18 2025.

\bibitem{Mf}
  Great Internet Mersenne Prime Search,
  List of known Mersenne primes.
  Available at \url{https://www.mersenne.org/primes} ,
  accessed on August 20 2025.

\bibitem{Mplus}
  Mersenneplustwo,
  Mersenneplustwo factorizations.
  Available at \url{https://sites.google.com/site/bearnol/math/mersenneplustwo} ,
  accessed on August 29 2025.

\bibitem{NewM}
  New Mersenne Conjecture,
  New Mersenne conjecture.
  Available at \url{http://www.hoegge.dk/mersenne/NMC.html} ,
  accessed on August 29 2025.

\bibitem{OEIS}
  N. J. A. Sloane et al.,
  {\it The On-Line Encyclopedia of Integer Sequences}, 2025.
  Available at \url{https://oeis.org}.

\bibitem{Wag82}
  S. S. Wagstaff, Jr.,
  Pseudoprimes and a generalization of Artin's conjecture,
  \textit{Acta Arith.} {\bf 41} (1982), 141--150.

\bibitem{Wag83}
  S. S. Wagstaff, Jr.,
  Divisors of Mersenne numbers,
  \textit{Math. Comp.} {\bf 40} (1983), 385--397.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11Y55; Secondary 11Y11, 11A51.

\noindent
\emph{Keywords}: Mersenne number, Mersenne prime, Wagstaff prime.

\bigskip
\hrule
\bigskip

\noindent
(Concerned with sequences
\seqnum{A000043},
\seqnum{A000668},
\seqnum{A000978},
\seqnum{A000979},
\seqnum{A083420},
\seqnum{A103901}, and
\seqnum{A107360}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 1 2025;
revised version received September 27 2025.
Published in {\it Journal of Integer Sequences}, December 4 2025.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in


\end{document}

                                                                                

