# A question on Euler's totient function

With reference to the Euler's totient function $$\phi(\cdot)$$, given any $$n \in \mathbb{Z}^+$$, it's quite straightforward to find $$\phi(n)$$.

In contrast, given $$n \in \mathbb{Z}^+$$, even though there are to find the $$k \in \mathbb{Z}^+$$ such that $$\phi(k) = n$$, I'm not aware of any method to determine the number of such $$k$$ values beforehand. What are the progress that has been made in this regard ?

• Number of numbers $m$ with Euler $\phi(m) = n$ is tabulated at oeis.org/A014197 Apr 18 at 0:05
• Apr 18 at 0:06
• Actually, your first sentence is not really true if by "straightforward" you mean "reasonably easy to compute." If, for example, $p$ and $q$ are thousand digit primes and $n=pq$, then it is currently completely infeasible to compute $\phi(n)$ (unless one has a quantum computer in one's basement!). The point is that computing $\phi(n)$ is equivalent to finding $p$ and $q$. RSA, and many other cryptographic algorithms, depend on the difficulty of this problem. However, I realize this isn't the gist of your question, which is interesting. Apr 19 at 22:26
• @JoeSilverman, thank you for the comment, Professor ! You're one of my mathematical heroes. Apr 20 at 5:59

Ford's theorem ($$1999$$) states that for any $$m\ge2,$$ there exists a totient number $$n$$ with multiplicity $$m$$ (that's for which there are $$m$$ solutions to $$\varphi (x)=n.$$)* This had been conjectured by Sierpiński.

Also, each multiplicity occurs infinitely often.

Furthermore, no number is known with multiplicity $$1.$$ Carmichael conjectured that there's no such number.

*See The Number of Solutions of $$\varphi (x)=m,$$ Annals of Mathematics, Second Series, Vol. 150, No. 1, Jul 1999, pp. 283-311 (29 pages)

You may like to check my paper "Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions".

There is also a PARI/GP implementation of the proposed algorithm.

• Thank you ! The content of the paper is too abstract to grasp. I'll check it anyways. Apr 18 at 2:48