21
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ It's a quite known equation. There were papers by Igor Shparlinsky on it. No reasonable algorithm is known so far... $\endgroup$ Jul 13, 2010 at 12:22
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 13, 2010 at 12:49
  • 3
    $\begingroup$ See arxiv.org/abs/math/0404116 , also ams.org/journals/mcom/2006-75-254/S0025-5718-06-01826-6/… $\endgroup$
    – lhf
    Jul 13, 2010 at 12:49
  • 1
    $\begingroup$ The number of solutions of φ(x)=m , Annals of Math. 150 (1999), 283--311. Available at math.uiuc.edu/~ford/papers.html $\endgroup$ Jul 14, 2010 at 2:12
  • 1
    $\begingroup$ I have implementation of $\varphi^{-1}(n)$ in PARI/GP at cse.sc.edu/~maxal/gpscripts $\endgroup$ Jul 14, 2010 at 22:32

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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