Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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.) –  Paul Albert Jun 25 '11 at 15:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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