# Is there an integer $N>0$ such that $\varphi(n) = N$ has infinitely many solutions?

Let $\varphi: \mathbb{N} \to \mathbb{N}$ be the totient function.

Is there an integer $N > 0$ such that there are infinitely many integers $n > 0$ such that $$\varphi(n) = N?$$

• Pardon me? Is not the totient function invertible? – Megadeth Aug 28 '14 at 14:50
• Hint: $n > \varphi(n) > \sqrt{\frac{n}{2}}$ so $n<N-1$ and $n>2N^2$ cannot be solutions to $\varphi(n) = N$ – Winther Aug 28 '14 at 15:03
• @Winther: Useful, hitting the point. But where is the lower bound from? – Megadeth Aug 28 '14 at 15:06
• Click on "Hint". It's a fairly simple proof, you can also find it in on the last page in this paper. btw much stronger bounds are found here and reads $\varphi(n) > \frac{n}{e^\gamma \log\log n + \frac{3}{\log\log n}}$ – Winther Aug 28 '14 at 15:08
• Thanks! I have just found a stronger lower bound that $\varphi(n) \geq \sqrt{n}.$ Please see mathworld.wolfram.com/TotientFunction.html – Megadeth Aug 28 '14 at 15:21

No. Let $M\in\mathbb{Z}^{+}$ and let $p$ be the smallest prime such that $p> M+1$. Let $n\in\mathbb{Z}$ such that $\varphi(n)=M$. Now, suppose $q\ge p$ is a prime factor of $n$. Then, write $n=q^k\cdot m$, fro some $k\ge 1$ and $q\nmid m$. Then, we get $$\varphi(n)=\varphi(q^k\cdot m)=\varphi(q^k)\varphi(m)\ge q-1\ge p-1>M,$$ contradiction. Thus, no prime divisor of $n$ can be greater than $M+1$.

Thus, the prime divisors of $n$ make up a finite set, say $\{p_1,\ldots,p_m\}$. Now, write $n=p_1^{e_1}\cdots p_m^{e_m}$, for $e_i>0$. Then,

$$\varphi(n)=\varphi(p_1^{e_1})\cdots\varphi(p_m^{e_m})=\prod_{i=1}^{m}p_i^{e_i-1}(p_i-1).$$ Now, note that for each prime $p_i$, we have $\varphi(n)\ge p_i^{e_i-1}(p_i-1)>M$ for a sufficiently large choice of $e_i$. Thus, for each $p_i$ there are only finitely many valid choices for the $e_i$, and it follows that the set of all $n$ s.t. $\varphi(n)=M$ is finite.

• Why you first assume $\varphi(n) = M$ and later have $\varphi(n) > M$? – Megadeth Aug 28 '14 at 14:54
• @Brian That yields a contradiction allowing us to say that no prime dividing $n$ is greater than $M+1$. – tc1729 Aug 28 '14 at 15:02
• Ah yes, I just saw the "for suff. large ...". – Megadeth Aug 28 '14 at 15:04
• Where is the first contradiction? – Jossie Calderon Feb 21 at 5:22

No.

We use the fact that if $n = p_1^{e_1} \cdots p_k^{e_k}$, with the $p_i$ different primes and the $e_i$ positive, we have $\phi(n) = p_1^{e_1-1}(p_1-1) \cdots p_k^{e_k-1}(p_k-1)$.

Now consider an integer $N>0$ and suppose that $\phi(n) = N$. Then $n$ cannot be divisible by primes larger than $N+1$, since if $q > N+1$ divides $n$, we have $N+1 \leq q-1 \mid \phi(n) = N$, contradiction. The set of primes that may divide $n$, therefore, is finite. Let $p$ be such a prime. Then if $p^k \mid n$ we have $p^{k-1} \mid N$, which leaves a finite number of possibilities for $k$. Thus the number of primes that may divide $n$ is bounded and the exponent of each prime is bounded as well, thus there are at most finitely many $n$ for which $\phi(n) = N$.