Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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$. –  Marc Nov 19 '13 at 1:48
    
@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! –  mathematics2x2life Nov 19 '13 at 1:54
    
The phrasing could have been better, so don't feel bad. –  Marc Nov 19 '13 at 1:58
    
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}, $$ –  Will Jagy Nov 19 '13 at 2:41
    
FYI, I have given a proof here. –  ccorn Dec 4 '13 at 14:21

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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! –  mathematics2x2life Nov 19 '13 at 1:53
    
You are welcome. One of these nights happens to all of us. –  André Nicolas Nov 19 '13 at 2:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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