Let $\phi(n)$ be Euler's totient function.
How do I show that there are only finitely many such $n$ with $\phi(n) = m$, for each positive integer $m$?
I've written $n$ as a product of primes; $n = p_1^{c_1} \cdots p_k^{c_k}$, and then $\phi(n) = p_1^{c_1 - 1}(p_1 -1) \cdots p_k^{c_k - 1}(p_k - 1)$, I feel like this should help me but I can't seem to see why!
Also, out of interest, is it possible to represent every single integer $m$ in terms of the Euler totient function $\phi(n)$?
On
It is known that $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$. Therefore, if $\phi(n) = m$, then $n \le 2m^2$.
On
If there is a solution to $\phi(n) = m$ for a given $n$, what are the minimum and maximum possible values of $n$?
Assume that $m + 1$ is prime. Then $n = m + 1$ gives us the minimum possible solution. Of course if $m + 1$ is composite then the minimum $n$ will be correspondingly larger.
As for the maximum possible value of $n$, I figured it out a couple of years ago and then saw it confirmed in a book published before I was born, which is to say, very, very long ago.
Unfortunately I don't remember what it was. It was something like $m^2 - m$ for $m > 2$. No, that's overshooting it... The point is that if solutions exist, there is a minimum $n$ and a maximum $n$, and therefore the set of solutions is finite.
As for your last question, how would you handle numbers like $14$ and $26$?
On
If $p^r\mid\mid n$, then $p^{r-1}(p-1))\mid\phi(n)$, which implies $\phi(n)\ge\max(p-1,p^{r-1})\ge\max(p-1,2^{r-1})$. Now if $m=\phi(n_1)=\phi(n_2)=\phi(n_3)=\cdots$ with $n_1\lt n_2\lt n_3\lt\cdots$, then for any prime power $p^r$ dividing any of the $n_k$'s we must have $p\le m+1$ and $r\le1+\log_2 m$. This put a finite upper bound on the sequence: If $n\gt((m+1)!)^{1+\log_2m}$, then $\phi(n)\gt m$.
Remark: The result here is nowhere near as good as the result $n\gt2m^2\implies\phi(n)\gt m$ in lhf's answer, but the proof here is nowhere near as complicated as the proof(s) linked to there.
On
The Euler totient function satisfies $$\lim_{n \rightarrow +\infty} \varphi(n) = +\infty$$
Let's prove it. Take $n \geq 2$ and write $n=p_1^{m_1} ... p_r^{m_r}$ as a product of distinct primes. Of course $$n \geq p_1...p_r \geq 2^r$$ so $r \leq \log_2(n)$.
Now, if you fix $p_1 < p_2 < ... < p_r$, you have then $p_i \geq i+1$, so $$\varphi(n) = n \prod_{i=1}^r \left(1- \frac{1}{p_i} \right) \geq n \prod_{i=1}^r \left(1- \frac{1}{i+1} \right) = \frac{n}{r+1} \geq \frac{n}{\log_2(n)+1}$$
which tends to $+\infty$ as $n$ tends to $+\infty$.
On
It's really a one-liner once you realize that $$p_1^{r_1-1}p_2^{r_2-1}\dots p_m^{r_m-1}(p_1-1)(p_2-1)\dots (p_m-1)=k$$ has to have atmost finitely many solutions as both $$f(p_1,\dots p_m)=p_1^{r_1-1}\dots p_m^{r_m-1}$$ and $$g(p_1,\dots p_m)=(p_1-1)\dots (p_m-1)$$ are increasing functions in each of the variables.
On
If there is a solution $n$ to the equation $\phi(n)=m$, then $m$ is called totient number, otherwise $m$ is non-totient number. Odd numbers $>1$, are non-totient. But, not all even numbers are totient. For example $\phi(n)=14$ has no solutions. $m=14$ is the first non-totient even number.
In the link https://en.wikipedia.org/wiki/Euler%27s_totient_function, totients numbers section there is an estimation for the number of totient numbers counted with multplicities. With $x=m$ and $k=1$ it is:
$$|\{n: \phi(n)\leq m\}|=\frac{\zeta(2)\zeta(3)}{\zeta(6)}m+O\left(\frac{m}{\ln m}\right).$$ So, $|\{n: \phi(n) = m\}|$ is finite too. Mostly it is zero. Carmichael's totient function conjecture states that $|\{n: \phi(n) = m\}|$ can not be $1$. I wondered Ford's theorem. It states that $|\{n: \phi(n) = m\}|$ can be $\geq 2$.
First, note that for any $r$ there at most two numbers $s$ satisfying
This is because the only possible options are $r+1$ or $\frac{pr}{p-1}$ where $p$ is the largest prime dividing $r$.
Second, we can write $n=s_1s_2\cdots s_k$ where each $s_i$ is a power of a different prime. Then if $\phi(s_i)=r_i$ for each $i$, we have $\phi(n)=r_1r_2\cdots r_k$ and we have at most one $i$ with $r_i=1$ (since this only occurs if $s_i=2$). There are only finitely many ways to write $m$ as a product of some positive integers $r_i$ with at most one $r_i=1$, and for each such product there are finitely many ways to reconstruct the $s_i$.
For the second question, numbers which don't appear as the totient function of other numbers are called "nontotients" - see the wikipedia article on them for more details.