14
$\begingroup$

Let $\varphi$ denote Euler's totient function. It's widely believed that $2^n-1$ is prime for infinitely many (prime) $n$, which, in turn, implies $$\limsup_{n \to \infty} \frac{\varphi(2^n-1)}{2^n-1} = 1. $$ But what about an unconditional proof? This is sort of a follow-up of a question asked by @kodlu yesterday.

$\endgroup$

1 Answer 1

30
$\begingroup$

Let $n$ be a large prime. Then $2^n-1=p_1\dots p_k$ (possibly with equal factors), where $n\mid p_i-1$ for all $i$. Therefore, $k\leq \log_n(2^n-1)<\frac{n}{\log_2n}$. Thus, $$ \frac{\varphi(2^n-1)}{2^n-1}\geq\prod_{i=1}^k\left(1-\frac1{p_i}\right) \geq \left(1-\frac1n\right)^{n/\log_2n}\to1, \quad n\to\infty, $$ as required.

$\endgroup$
1
  • 3
    $\begingroup$ That's beautiful. $\endgroup$ Commented Oct 18, 2017 at 11:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .