3
$\begingroup$

I was skimming again through Dummit & Foote's Abstract Algebra and I came across this exercise:

Prove that for any given positive integer $N$ there exist only finitely many integers $n$ with $\varphi(n)=N$, where $\varphi$ denotes Euler $\varphi$-function. Conclude in particular that $\varphi(n)$ tends to infinity as $n$ tends to infinity.

I don't doubt that $\varphi(n) \to \infty$ as $n \to \infty$. However, if I recall Erdös proved that if there is an $x_0$ such that $\varphi(x_0)=N$, then there must be infinitely many integers such that $\varphi(x)=N$. See this article for a mention of this (it's in the very first $2$ lines).

Am I reading something wrong here? Has has Dummit and Foote actually asked the impossible? Or does the MathWorld site contain an error?

$\endgroup$
  • 2
    $\begingroup$ The link doesn't say quite what you think it does -- there are infinitely many integers with the same multiplicity, not infinitely many with the same solution to $\varphi (n) = N$. $\endgroup$ – user109775 Nov 19 '13 at 1:48
  • $\begingroup$ @Marc & André: I knew it was something obvious but I stared at this for a good half hour not seeing it. I guess it's just one of those nights. Thank you both for pointing out what I should have seen! $\endgroup$ – mathematics2x2life Nov 19 '13 at 1:54
  • $\begingroup$ The phrasing could have been better, so don't feel bad. $\endgroup$ – user109775 Nov 19 '13 at 1:58
  • $\begingroup$ Note that $$ \varphi(n) \geq \sqrt {\frac{n}{2}}, $$ for an easy example of a lower bound showing that $\varphi(n)$ tends to infinity. Also $$ \varphi(n) \geq \; 2 \; \left( \frac{n}{6} \right)^{2/3}, $$ $\endgroup$ – Will Jagy Nov 19 '13 at 2:41
  • $\begingroup$ FYI, I have given a proof here. $\endgroup$ – ccorn Dec 4 '13 at 14:21
2
$\begingroup$

The result you refer to does not say what you think it does. What it says is that if there is an $m_0$ such that $\varphi(x)=m_0$ has exactly $k$ solutions, then there exist infinitely many $m$ such that $\varphi(x)=m$ has exactly $k$ solutions.

For example, let $k=3$. There is an $m_0$, namely $2$, such that $\varphi(x)=m_0$ has exactly $k$ solutions. These are $3$, $4$, and $6$. We can conclude that there are infinitely many $m$ such that $\varphi(x)=m$ has exactly $3$ solutions.

$\endgroup$
  • $\begingroup$ I knew it was something obvious but I stared at this for a good half hour not seeing it. I guess it's just one of those nights. Thank you! $\endgroup$ – mathematics2x2life Nov 19 '13 at 1:53
  • 1
    $\begingroup$ You are welcome. One of these nights happens to all of us. $\endgroup$ – André Nicolas Nov 19 '13 at 2:03

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.