MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Inverting the totient function

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

-
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 2010 at 12:22
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 2010 at 12:49
See arxiv.org/abs/math/0404116 , also ams.org/journals/mcom/2006-75-254/… – lhf Jul 13 2010 at 12:49
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 2010 at 2:12
I have implementation of $\varphi^{-1}(n)$ in PARI/GP at cse.sc.edu/~maxal/gpscripts – Max Alekseyev Jul 14 2010 at 22:32
show 1 more comment

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.

-
 For Carmichael's conjecture, see also mathworld.wolfram.com/… – Alain Valette Jun 3 2011 at 7:33

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

-