# The equation $\phi (x)=n$ has only a finite number of solutions. [duplicate]

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

• Which prime powers might divide an $x$ with $\phi(x) = n$? – Daniel Fischer Jul 3 '15 at 18:19
• 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}$ – Will Jagy Jul 3 '15 at 18:20
• @DanielFischer, all prime powers that divide n divide x? – Apurv Jul 3 '15 at 18:23
• found my version, math.stackexchange.com/questions/301837/… – Will Jagy Jul 3 '15 at 18:25
• No, e.g. $\phi(3) = 2$, and $2 \nmid 3$. The multiplicativity of $\phi$ gives a constraint. – 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

$$\phi(x)=p^{k-1}(p-1)\phi(n)$$

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.

• Should read: For any prime divisor of $x$ – ccorn Jul 3 '15 at 18:29
• @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. – Rory Daulton Jul 3 '15 at 18:30