3
$\begingroup$

How do you calculate the inverse of Euler's totient function?

For example, what is $\phi^{-1}(12)$?

I'm confused as my lecture notes give no explanation, they just state that e.g. $\phi^{-1}(2)=-1$ and $\phi^{-1}(3)=-2$.

When I search for Inverse of Euler's totient function I get answers for how to solve $\phi(n)=k$, which is not what I'm looking for, so maybe I'm asking the wrong question?

I'm more confused by the fact the answer that I'm given is $\phi^{-1}(12)=2$ because if $\phi^{-1}(2)=-1$ and $\phi^{-1}(3)=-2$, assuming $\phi^{-1}$ is multiplicative, $\phi^{-1}(12)=(\phi^{-1}(2))^2\phi^{-1}(3)=(-1)^2(-2)=-2.$

$\endgroup$
  • 3
    $\begingroup$ The solutions to $\phi(n)=12$ are $13,21,26,28,36,42$. But if this is not what you mean by inverse, what do you mean? $\endgroup$ – Henry May 31 '17 at 21:00
  • 1
    $\begingroup$ Well, yes. They are equivalent problems to solve. If you know that $f(x)=y$ then we know that $f^{-1}(y)=x$. In your case, solving $\phi^{-1}(12)=x$ is equivalent to solving $\phi(x) =12$ $\endgroup$ – Brevan Ellefsen May 31 '17 at 21:03
  • $\begingroup$ Did you get your notes from a lecturer as part of a course? It would be best to ask that person for clarification. $\endgroup$ – Matthew Conroy May 31 '17 at 21:13
6
$\begingroup$

They meant the Dirichlet inverse of $\phi(n)$, which is a multiplicative function : $$gcd(n,m) = 1 \quad\implies\quad \phi(nm) = \phi(n)\phi(m)$$ From $\phi(p^k)= p^{k-1}(p-1)$ we obtain $$\sum_{d | n} \phi(d) = n, \qquad \phi(n) = \sum_{d | n} \mu(d) \frac{n}{d}$$ where $\mu(n)$ is the Möbius function. thus $$\phi^{-1}(n) = \sum_{d | n} d \mu(d)$$ Which is multiplicative too. Therefore

$$\phi^{-1}(3) = 1-3 = -2, \qquad \phi^{-1}(2) = 1-2 = -1$$

$$\phi^{-1}(12) = \phi^{-1}(3)\phi^{-1}(4)= (1-3)(1-2) = 2$$

$\endgroup$
  • $\begingroup$ Excellent, thank you. That clears things up. Please could you clarify why $\phi^{-1}(12)= 2$ and not $-2$? I would have thought $\phi^{-1}(6)= 2$ but may be mistaken. $\endgroup$ – math_apprentice Jun 1 '17 at 9:54
  • $\begingroup$ @math_apprentice I wrote how I get $\phi^{-1}(12)=2$. It is not true that $\phi^{-1}(12) = \phi^{-1}(3) (\phi^{-1}(2))^2$ : $\phi^{-1}(n)$ is not completely multiplicative. $\endgroup$ – reuns Jun 1 '17 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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