Only finitely many $n$ such that $\phi(n) = m$

Solution 1:

First, note that for any $r$ there at most two numbers $s$ satisfying

• $s$ is a prime power and
• $\phi(s)=r$.

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.

Solution 2:

It is known that $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$. Therefore, if $\phi(n) = m$, then $n \le 2m^2$.

Solution 3:

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.

Solution 4:

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$?