An inequality for the Euler totient function

Question

Is it true that $2\varphi(n)>n$ if $n=2^k-1$ with any odd k (checked by Sage for k<137 at the moment)?

Answer 1

Let $p$ be a prime such that $p \equiv 7 \bmod 8$, then $2$ is a quadratic residue mod $p$ and $\frac{p-1}{2}$ is odd.

Hence, if we take $k= \prod_{p \le x, p \equiv 7 \bmod 8} \frac{p-1}{2}$, then $n$ is divisible by all $p \le x$ of the form $p \equiv 7 \bmod 8$, and $k$ is odd. We get $$\frac{\phi(n)}{n} = \prod_{p \mid n} (1-\frac{1}{p}) \le \prod_{p \le x, p \equiv 7 \bmod 8} (1-\frac{1}{p}) \le e^{-\sum_{p \le x, p \equiv 7 \bmod 8} \frac{1}{p}},$$ which goes to 0 as $x \to \infty$, by Dirichlet's theorem on primes in arithmetic progressions. Hence, the answer is 'no'.

Answer 2

No it's not true. An equivalent question is whether the product of $(1-1/p)$, where $p$ ranges over all the primes for which 2 has odd order mod $p$, is greater than or equal to $1/2$. However an explicit calculation shows that if you take the product over all primes $p$ less than 57 million with this property then the product is just less than $1/2$, so there will be a counterexample; however $k$ will be astronomical (the lowest common multiple of these millions of orders, many of which will be a million or more). Computing the product instead of the lowest common multiple gives some value of $k$ which has 6482632 digits (the product becomes less than $1/2$ when $p=55685687$), but the smallest counterexample will be smaller than that because the LCM will save you something (although it will still be astronomical).