It is unknown whether $2^n-1$ is (a Mersenne) prime for infinitely many values of $n$. Such $n$ must necessarily be prime itself due to the factorization below $$(2^{ab}-1)=(2^a-1)(2^b+2^{b-1}+\cdots+2+1).$$

I am aware that there are related results on the size of the largest prime divisor of Mersenne numbers $M_n=2^n-1$ from this Mathoverflow question. But my question is somewhat different.

The question: How much do we need to weaken the question of primality to get a result that holds infinitely often. Is a statement such as $$ \varphi(2^n-1) \geq 2^n-1-K,\quad \textrm{for infinitely many }n\quad(1) $$ where $K$ is a bounded positive integer likely to hold, or proven? I think this is probably false.

Alternatively, how slowly growing a function of $n$, call it $K(n)$ can we specify so that $$ \varphi(2^n-1) \gg 2^n-1-K(n),\quad \textrm{for infinitely many }n\quad(2) $$ holds? In the light of Noam D. Elkies' comment, hopefully the following is better posed: Is it possible to find a constant $c \in (0,1)$ such that $$ \varphi(2^n-1) \geq c(2^n-1),\quad \textrm{for infinitely many }n\quad(3) $$ Experimentally, from Mathematica with $2\leq n\leq 220$ all but 2 $n$ satisfy (3) with $c=1/3$ and all but roughly 20% of $2\leq n \leq 220$ satisfy (3) with $c=1/2.$

  • 6
    $\begingroup$ If $N$ is not prime then $N$ has a prime factor no larger than $\sqrt N$, whence $\phi(N) \leq N - \sqrt N$. Thus for any constant $K$ the condition $\phi(2^n-1) \geq 2^n - 1 - K$ is equivalent with primality of $2^n-1$ once $n$ is larger than about $2 \log_2 K$. Likewise if $K=K(n)$ grows slower than $2^{n/2}$. $\endgroup$ – Noam D. Elkies Oct 19 '15 at 0:35
  • $\begingroup$ @NoamD.Elkies, thanks for the comment which shows the question is ill-posed. $\endgroup$ – kodlu Oct 19 '15 at 3:32

It is not so hard to prove that $\phi(2^p-1)/(2^p-1) \to 1$ as $p\to \infty$ along prime values. This follows from the usual formula for $\phi(n)/n$ as a product over primes along with the observation that $\sum_{q\mid 2^p-1,~q\text{ prime}} 1/q \to 0$, as $p\to\infty$. This last fact can be seen by noting that --- from the maximal order of the distinct prime divisors function --- there are only $O(p/\log{p})$ distinct primes dividing $2^p-1$, while every prime dividing $2^p-1$ is congruent to $1$ modulo $p$, and so exceeds $p$.

In fact, $\phi(2^n-1)/(2^n-1)$ has a distribution function, in the sense of probabilistic number theory. As a consequence, given any $\epsilon > 0$, there is a $c >0$ such that $\phi(2^n-1)/(2^n-1) > c$ away from a set of $n$ of upper density $< \epsilon$. This distribution function result can be deduced from the general results of

Luca, Florian; Shparlinski, Igor E.(5-MCQR-CP) Arithmetic functions with linear recurrence sequences. (English summary) J. Number Theory 125 (2007), no. 2, 459–472.

(The full distribution function result is deeper than the consequence I noted above; that consequence follows, e.g., from a first moment argument.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.