I recently attempted to solve the following question (exercise 0.2.10 from Dummit & Foote - Abstract Algebra):
Prove for any given positive integer $N$ there exist only finitely many integers $n$ with $\varphi(n) = N$, where $\varphi$ denotes Euler’s $\varphi$-function. Conclude in particular that $\varphi(n)$ tends to infinity as $n$ tends to infinity.
I ended with something much similar to:
- Is there an integer $N>0$ such that $\varphi(n) = N$ has infinitely many solutions?
- Prove for any given positive integer $N$ there exist only finitely many integers n with $φ(n)=N$
Which show that, for any given $N$, there are finitely many $n$ such that $\varphi(n) = N$. I am OK with this. However, the question also asks whether $\varphi(n)$ tends to infinite as $n$ does; 2. attempts to conclude that from 1, and that doesn't feel right to me. Let me explain:
All answers reach a point where for $\varphi(n) = N$, then $n$ must be a product of finitely many bounded primes, each raised to a bounded exponent. However, nothing is said about a lower bound on such $n$, and thus it seems wrong to conclude that $N$ grows with $n$; what if $N$ oscillates without a lower bound as $n$ grows bigger? The argument doesn't seem to address this possibility.
I know that $\varphi(n)$ is in fact bounded below, and many good answers can be found here: Is the Euler phi function bounded below?
What I ask, then, is whether that conclusion is false, needs some tinkering to work, or is fine and I missed something.
The conclusion is fine. From the observation that the solution set of $\varphi(x) = N$ is finite for each fixed $N$, it follows that $\varphi$ does not "oscillate" like that. The proof follows, so skip the rest if you'd like to work it out yourself!
Recall that the sequence $\varphi$ tends to infinity precisely if for any $M \in \mathbb{R}$ we can find an integer $K$ such that for all $n > K$, $a_n > M$.
So take any number $M$. There are finitely many integers $i$ that lie between $0$ and $M$. We know by our observation that for each of these finitely many integers $i$ the solution set of the equation $\varphi(x) = i$ is itself finite. But the union of finitely many finite sets is still finite, so there are finitely many solutions to $\varphi(i) \leq M$. The finite set of solutions has a maximal element, denote it $K$. Now for all $n > K$, $n$ is not a solution to $\varphi(n) \leq M$, so in fact we have $\varphi(n) > M$.