4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Felipe Voloch
    Commented Oct 2, 2012 at 10:22
  • $\begingroup$ 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. $\endgroup$
    – Salvo Tringali
    Commented Oct 2, 2012 at 10:23
  • 2
    $\begingroup$ 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) $\endgroup$
    – Salvo Tringali
    Commented Oct 2, 2012 at 10:56
  • 2
    $\begingroup$ ...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. $\endgroup$
    – Salvo Tringali
    Commented Oct 2, 2012 at 10:57
  • $\begingroup$ @Salvo, to be fair to Dickson, that volume was published in 1919. The later "editions" are unaltered reprints of the 1919 text. $\endgroup$
    – Gerry Myerson
    Commented Oct 3, 2012 at 1:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .