# How often is $2^n-1$ a number with few divisors?

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.$

• 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}$. – Noam D. Elkies Oct 19 '15 at 0:35
• @NoamD.Elkies, thanks for the comment which shows the question is ill-posed. – 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