# 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, 2018 at 9:43
• For your second question: note that $\varphi(n)$ is almost always even.
– lulu
May 21, 2018 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? May 21, 2018 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$. May 21, 2018 at 11:42

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

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. May 21, 2018 at 21:39

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

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

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.

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