MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Motivation: It's an elementary exercise to show that the number of solutions to the equation $\phi(x)=n$ is finite for any $n$, where $\phi$ is the Euler-phi function. Of course, counting the number of solutions is another matter.

Question: For a given $n$, can we describe the number of solutions to $|\phi^{-1}(n)|=m$? In other words, I want to know about how often the number of solutions to the equation $\phi(x)=n$ is $m$, for a given $m$, as $n$ varies. Since it wouldn't surprise me if this is way too hard, can we at least say something similar about finiteness?

share|cite|improve this question
Proving that your number is always non-zero is already pretty hard. This reference will get you going: K. Ford, The number of solutions of $\phi(x)=m$ , Annals of Math. 150 (1999), 283--311. – Felipe Voloch Oct 2 '12 at 10:22
Yours is the totient valence function, and it is a result of Erdős dating back to 1958 that if for some $m$ there exists at least one $n$ such that $|\phi^{-1}(n)|=m$ then $|\phi^{-1}(n)|=m$ for infinitely many $n$; see P. Erdős, Some Remarks on Euler's $\phi$-Function, Acta Math. (1958), Vol. 4, pp. 10-19. – Salvo Tringali Oct 2 '12 at 10:23
To add something to Felipe's comment, the question is related to a long-standing conjecture, mostly referred to as Carmichael's totient function conjecture, with a story behind it: Carmichael had published an alleged proof (Carmichael, On Euler's $\phi$-Function, Bull. AMS, Vol. 13 (1907), pp. 241-243), and even developed a method of finding a solution for each m (R.D. Carmichael, Notes on the Simplex Theory of Numbers, Bull. AMS, Vol. 15 (1909), pp. 217-223), to the extent of proposing the question as an exercise in his 1914 monograph on the theory of numbers. It took more than... (TBC) – Salvo Tringali Oct 2 '12 at 10:56
...a decade before Carmichael himself realized an error in his earlier "proof" (R.D. Carmichael, Note on Euler's $\phi$-Function, Bull. AMS, Vol. 28 (1922), pp. 109-110), with the result that the question is still today broadly open. In spite of the fact that Dickson, in the 2005 edition of his History of the Theory of Numbers (Vol. 1, p. 137), states that the conjecture was proved in Carmichael's original 1907 paper. – Salvo Tringali Oct 2 '12 at 10:57
@Salvo, to be fair to Dickson, that volume was published in 1919. The later "editions" are unaltered reprints of the 1919 text. – Gerry Myerson Oct 3 '12 at 1:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.