Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For what values of $n$ does the equation $\phi(x) = n$ have at least one solution? Is there any efficient way to check it for a given $n$?

It obviously has no solutions for odd $n$. And the smallest even number for which it has no solutions is $14$.

share|improve this question
    
It's a quite known equation. There were papers by Igor Shparlinsky on it. No reasonable algorithm is known so far... –  Wadim Zudilin Jul 13 '10 at 12:22
1  
There are some types of numbers for which it is known that there is no solution, but those types are recognized by their factorization, so the general problem won't be any easier than factoring. There is no solution if $n=2p$ where $p$ is prime but $2p+1$ isn't - that's where 14 comes from. –  Gerry Myerson Jul 13 '10 at 12:49
3  
1  
The number of solutions of φ(x)=m , Annals of Math. 150 (1999), 283--311. Available at math.uiuc.edu/~ford/papers.html –  Kevin O'Bryant Jul 14 '10 at 2:12
1  
I have implementation of $\varphi^{-1}(n)$ in PARI/GP at cse.sc.edu/~maxal/gpscripts –  Max Alekseyev Jul 14 '10 at 22:32
show 1 more comment

2 Answers

I recently answered this related question about the Carmichael function on math.SE. The algorithm uses an unconditional lower bound so it should work just as well for the totient function because $\lambda(x) \le \phi(x)$. My answer (the only one) has not been accepted and the question has a bounty which expires tomorrow. I should not like to receive a bounty by default for an incorrect answer, so I am posting this here now as an invitation for you to correct me on math.SE. It is not an efficient algorithm as this MO question demands, but I proffer it because no algorithm has yet been given to answer it.

Also related is Carmichael's totient function conjecture which is that there are no unique solutions to this equation.

share|improve this answer
    
For Carmichael's conjecture, see also mathworld.wolfram.com/CarmichaelsTotientFunctionConjecture.html –  Alain Valette Jun 3 '11 at 7:33
add comment

See http://oeis.org/A002202 and further references there.

UPDATE: See also my recent paper "Computing the (number or sum of) inverses of Euler's totient and other multiplicative functions", which presents a generic algorithm for finding the inverses of a multiplicative function for a given integer value.

share|improve this answer
add comment

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.