About the number of solutions of $\varphi(n)=m$

106 Views Asked by At

Let's denote $N_m$ as the number of solutions of

$$\varphi(n)=m$$

for all $m\geqslant 2$,

where $\varphi$ is Euler totient function, i.e.

$$N_m:=\#\{n\in \mathbb N,\ \varphi(n)=m\}.$$

We can prove easily that $N_m=0$ if $m$ is odd.

We also know that $N_m<\infty$ for all $m$ (thanks to this).

I plotted the sequence $(N_m)$, and I putted red points when

$$m\equiv 0\pmod{12}.$$

enter image description here

enter image description here

The question.

Why is every "high" point (i.e. corresponding to a high value of $N_m$) a red point?

1

There are 1 best solutions below

0
On

Let $m\in\Bbb{N}$ be given, and let $n\in\Bbb{N}$ be such that $\varphi(n)=m$. If $m\neq0\pmod{12}$ then either $3\nmid m$ or $4\nmid m$. If $4\nmid m$ then either $n=p^k$ or $n=2p^k$ for some prime $p\equiv3\pmod{4}$, or $n=4$. Similarly, if $3\nmid m$ then $n$ is a product of primes congruent to $2\pmod 3$, or $3$ times such a product. Both conditions are quite restrictive, and so $N_m$ should be small.