10
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ Number of numbers $m$ with Euler $\phi(m) = n$ is tabulated at oeis.org/A014197 $\endgroup$ Apr 18 at 0:05
  • 2
    $\begingroup$ Cf. this question $\endgroup$ Apr 18 at 0:06
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 19 at 22:26
  • $\begingroup$ @JoeSilverman, thank you for the comment, Professor ! You're one of my mathematical heroes. $\endgroup$
    – Eureka
    Apr 20 at 5:59

2 Answers 2

13
$\begingroup$

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)

$\endgroup$
0
12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you ! The content of the paper is too abstract to grasp. I'll check it anyways. $\endgroup$
    – Eureka
    Apr 18 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.