# 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 '10 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 '10 at 12:49
– lhf Jul 13 '10 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 '10 at 2:12
I have implementation of $\varphi^{-1}(n)$ in PARI/GP at cse.sc.edu/~maxal/gpscripts – Max Alekseyev Jul 14 '10 at 22:32

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

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

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.

-