While reading about Euler's totient function, I came across this question:

Prove that for a fixed $n$, the equation $\phi (x)=n$ has only a finite number of solutions.

I have thought a lot about it but could not arrive at a proof. I know that $\phi(m_1m_2)=\phi(m_1)\phi(m_2)$ (for $m_1,m_2$ co-prime), but it doesn't seem to help. Any hints/ideas on how to tackle this problem?

Note: I dont think this is a duplicate of Euler Totient Issues, as that question doesn't prove the result. It just clarifies the OP's misinterpretation of another result.


marked as duplicate by Dietrich Burde, Xander Henderson, Chris Custer, trancelocation, Arnaud D. May 15 '18 at 8:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Which prime powers might divide an $x$ with $\phi(x) = n$? $\endgroup$ – Daniel Fischer Jul 3 '15 at 18:19
  • 2
    $\begingroup$ there are explicit lower bounds for $\phi(x)$ that depend on $x.$ Some of the bounds are easy and show up on MSE as homework problems. The one I remember is $\phi(x) \geq \sqrt {x/2}$ $\endgroup$ – Will Jagy Jul 3 '15 at 18:20
  • $\begingroup$ @DanielFischer, all prime powers that divide n divide x? $\endgroup$ – Apurv Jul 3 '15 at 18:23
  • $\begingroup$ found my version, math.stackexchange.com/questions/301837/… $\endgroup$ – Will Jagy Jul 3 '15 at 18:25
  • $\begingroup$ No, e.g. $\phi(3) = 2$, and $2 \nmid 3$. The multiplicativity of $\phi$ gives a constraint. $\endgroup$ – Daniel Fischer Jul 3 '15 at 18:25

If $p$ is a prime divisor of $x$ and $x=p^k\cdot n$ where $p$ does not divide $n$, then


This is because the Euler totient function is "multiplicative", as you note: $\gcd(a,b)=1\implies \phi(ab)=\phi(a)\phi(b)$.

Therefore, $\phi(x)\ge p-1$ and $\phi(x)>p^{k-1}$ for any prime divisor of $x$.

Think now how large $x$ can get. If there are too many prime divisors of $x$, $p-1$ gets larger than the given value of $\phi(x)$. If the powers of the primes get too large, $p^{k-1}$ gets larger than the given value of $\phi(x)$.

Now formalize that argument.

  • $\begingroup$ Should read: For any prime divisor of $x$ $\endgroup$ – ccorn Jul 3 '15 at 18:29
  • $\begingroup$ @ccorn: Yes, of course, how silly of me. I'll add that to the beginning and correct that in the middle now. Thanks for the correction. $\endgroup$ – Rory Daulton Jul 3 '15 at 18:30

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