4
$\begingroup$

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.

$\endgroup$

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
5
$\begingroup$

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.

$\endgroup$
  • $\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.