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

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

• Step I: get an upper bound on the size of any prime $p$ dividing $n$. Step II: if $p\,|\,n$ for some prime $p$ get a bound on the exponent $a$ such that $p^a\,|\,n$. – lulu May 21 '18 at 9:43
• For your second question: note that $\varphi(n)$ is almost always even. – lulu May 21 '18 at 9:44

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.

• Why are them two options the only two possibilities? – the man May 21 '18 at 11:40
• @theman because if $s$ is prime then $\phi(s)=s-1$, whereas if $s=p^a$ is not prime ($a>1$) then $\phi(s)=p^{a-1}(p-1)$, and the largest prime factor of that is $p$. – Especially Lime May 21 '18 at 11:42

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.

• Ah, I see this is essentially the same proof as in Especially Lime's answer. – Barry Cipra May 21 '18 at 21:39

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

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