Return to Answer

UPD. Bound simplified.

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $k\leq 1+\frac{\log(m)}{\log(p)}\leq 1+\frac{\log(m)}{\log(2)}$. Then the number of such $a$ is bounded by $$\prod_{d\mid m} (2+\frac{\log(m)}{\log(2)}) = (2+\frac{\log(m)}{\log(2)})^{\tau(m)}.$$

For $m>40$, we have $2+\frac{\log(m)}{\log(2)}\leq 2\log(m)$, and thus we generously bound the number of solutions by $$(2\log(m))^m=2^me^{\log(m)^2}.$$

UPD. Bound simplified.

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $k\leq 1+\frac{\log(m)}{\log(p)}\leq 1+\frac{\log(m)}{\log(2)}$. Then the number of such $a$ is bounded by $$\prod_{d\mid m} (2+\frac{\log(m)}{\log(2)}) = (2+\frac{\log(m)}{\log(2)})^{\tau(m)}.$$

For $m>40$, we have $2+\frac{\log(m)}{\log(2)}\leq 2\log(m)$, and thus we generously bound the number of solutions by $$(2\log(m))^m.$$

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $(p-1)^k \leq p^{k-1}(p-1)\leq m$. Thus for $p\geq 3$, we have $k\leq \frac{\log(m)}{\log(p-1)}$, while for $p=2$, $k\leq\frac{\log(m)}{\log(2)}+1$. Then the number of such $a$ is bounded by $$(2+\frac{\log(m)}{\log(2)})\prod_{d\mid m\atop d\geq 2} (1+\frac{\log(m)}{\log(d)})< \frac{\log(4m)}{\log(2)}\exp\left(\sum_{d\mid m\atop d\geq 2} \frac{\log(m)}{\log(d)}\right) = \frac{\log(4m)}{\log(2)}m^E,$$ where $$E:=\sum_{d\mid m\atop d\geq 2} \frac{1}{\log(d)} \leq \frac{1}{\log(2)} + \int_{2}^{m} \frac{\mathrm{d}t}{\log(t)}=\frac{1}{\log(2)} + \mathrm{Ei}(\log(m))-\mathrm{Ei}(\log(2)) < 1 + \gamma + \frac{11}{36}\log(m)^2,$$ $\mathrm{Ei}(x)$ is the exponential integral and $\gamma$ is Euler-Mascheroni constant.

So, we can generously bound the number of solutions to $\phi(x)=m$ by $$\frac{\log(4m)}{\log(2)}m^{1+\gamma}e^{\frac{11}{36}\log(m)^3}.$$

UPD. Bound simplified.

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $k\leq 1+\frac{\log(m)}{\log(p)}\leq 1+\frac{\log(m)}{\log(2)}$. Then the number of such $a$ is bounded by $$\prod_{d\mid m} (2+\frac{\log(m)}{\log(2)}) = (2+\frac{\log(m)}{\log(2)})^{\tau(m)}.$$

For $m>40$, we have $2+\frac{\log(m)}{\log(2)}\leq 2\log(m)$, and thus we generously bound the number of solutions by $$(2\log(m))^m=2^me^{\log(m)^2}.$$

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $(p-1)^k \leq p^{k-1}(p-1)\leq m$. Thus for $p\geq 3$, we have $k\leq \frac{\log(m)}{\log(p-1)}$, while for $p=2$, $k\leq\frac{\log(m)}{\log(2)}+1$. Then the number of such $a$ is bounded by $$(2+\frac{\log(m)}{\log(2)})\prod_{d\mid m\atop d\geq 2} (1+\frac{\log(m)}{\log(d)})< \frac{\log(4m)}{\log(2)}\exp\left(\sum_{d\mid m\atop d\geq 2} \frac{\log(m)}{\log(d)}\right) = \frac{\log(4m)}{\log(2)}m^E,$$ where $$E:=\sum_{d\mid m\atop d\geq 2} \frac{1}{\log(d)} = \frac{1}{\log(2)} + \int_{2}^{m} \frac{\mathrm{d}t}{\log(t)}=\frac{1}{\log(2)} + \mathrm{Ei}(\log(m))-\mathrm{Ei}(\log(2)) < 1 + \gamma + \frac{11}{36}\log(m)^2,$$ $\mathrm{Ei}(x)$ is the exponential integral and $\gamma$ is Euler-Mascheroni constant.

So, we can generously bound the number of solutions to $\phi(x)=m$ by $$\frac{\log(4m)}{\log(2)}m^{1+\gamma}e^{\frac{11}{36}\log(m)^3}.$$

Here is a constructive bound for the number of solutions to $\phi(x)=m$.

Let $\varphi(a) = m$. If $p^k\mid a$ for some $k\geq 1$, then $p^{k-1}(p-1)\mid m$, and thus $(p-1)^k \leq p^{k-1}(p-1)\leq m$. Thus for $p\geq 3$, we have $k\leq \frac{\log(m)}{\log(p-1)}$, while for $p=2$, $k\leq\frac{\log(m)}{\log(2)}+1$. Then the number of such $a$ is bounded by $$(2+\frac{\log(m)}{\log(2)})\prod_{d\mid m\atop d\geq 2} (1+\frac{\log(m)}{\log(d)})< \frac{\log(4m)}{\log(2)}\exp\left(\sum_{d\mid m\atop d\geq 2} \frac{\log(m)}{\log(d)}\right) = \frac{\log(4m)}{\log(2)}m^E,$$ where $$E:=\sum_{d\mid m\atop d\geq 2} \frac{1}{\log(d)} \leq \frac{1}{\log(2)} + \int_{2}^{m} \frac{\mathrm{d}t}{\log(t)}=\frac{1}{\log(2)} + \mathrm{Ei}(\log(m))-\mathrm{Ei}(\log(2)) < 1 + \gamma + \frac{11}{36}\log(m)^2,$$ $\mathrm{Ei}(x)$ is the exponential integral and $\gamma$ is Euler-Mascheroni constant.

So, we can generously bound the number of solutions to $\phi(x)=m$ by $$\frac{\log(4m)}{\log(2)}m^{1+\gamma}e^{\frac{11}{36}\log(m)^3}.$$