Inverting the totient function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T15:12:24Z http://mathoverflow.net/feeds/question/31691 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31691/inverting-the-totient-function Inverting the totient function falagar 2010-07-13T12:12:57Z 2011-06-03T07:49:49Z <p>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$?</p> <p>It obviously has no solutions for odd $n$. And the smallest even number for which it has no solutions is $14$.</p> http://mathoverflow.net/questions/31691/inverting-the-totient-function/31927#31927 Answer by Max Alekseyev for Inverting the totient function Max Alekseyev 2010-07-14T23:26:14Z 2010-07-14T23:26:14Z <p>See <a href="http://oeis.org/A002202" rel="nofollow">http://oeis.org/A002202</a> and further references there.</p> http://mathoverflow.net/questions/31691/inverting-the-totient-function/66791#66791 Answer by Dan Brumleve for Inverting the totient function Dan Brumleve 2011-06-03T03:39:31Z 2011-06-03T07:49:49Z <p>I recently answered <a href="http://math.stackexchange.com/questions/41061/what-is-the-inverse-of-the-carmichael-function/42517#42517" rel="nofollow">this related question about the Carmichael function on math.SE</a>. 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.</p> <p>Also related is <a href="http://en.wikipedia.org/wiki/Carmichael%27s_totient_function_conjecture" rel="nofollow">Carmichael's totient function conjecture</a> which is that there are no unique solutions to this equation.</p>