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

Improve this question
$\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$
    – Wadim Zudilin
    Commented 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$
    – Gerry Myerson
    Commented 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
    Commented 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$
    – Kevin O'Bryant
    Commented 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$
    – Max Alekseyev
    Commented Jul 14, 2010 at 22:32

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .