2
$\begingroup$

n is an even nontotient if n is even and Euler phi(m) = n has no solution. I am looking for a search limit L(n) depending on n. By this I mean:

If for all k, 1 <= k <= L(n) phi(k) = n has no solution then phi(m) = n has no solution.

Is there a provable limit? (My conjecture: L(n) = 2n is sufficient.)

1 Answers 1

2

The question in essence asks about a tight lower bound on the $\varphi$-function.

I believe that the best more or less universal bound is that for $n>2$, $\varphi(n)> \frac{n}{e^\gamma \log(\log n) +\frac{3}{\log(\log n)}}$ where $\gamma$ is the Euler-Mascheroni constant. The term $3/(\log(\log n))$ is there to take care of smallish $n$, and could be almost removed for large numbers, but I do not know the details.

However, crucially for your question, the term $e^\gamma \log(\log n)$ cannot be improved on.

If we look at how knowledge about the bound affects your problem, we can see that $\varphi(2n)$ can be significantly smaller than $n$ for huge $n$, so a search up to $2n$ would not be enough to rule out the existence of a solution of $\varphi(x)=n$.

The function $\log(\log n)$ grows exceedingly slowly. If you know roughly the range of values over which the search will take place, you can use the known bounds to find a suitable constant $c$ that enables you to replace $2n$ by $cn$.

  • 0
    Excellent! Thank you very much! (I am sorry that I am not able to vote you up. Perhaps another reader will do it for me.)2011-06-25