Solving equation involving Euler's totient function

Given $m\in\mathbb{N}$, is there a general way to solve the equation $$\varphi(n)=m$$ where $\varphi$ is the Euler's totient function? For example, I want to solve for all the $n$'s such that $\varphi(n)=4$. Is there any way to solve it that are also applicable to many (if not general) cases?

• For related problems, see Ford's Theorem and Carmichael's Totient Conjecture. – JasonM Aug 5 '16 at 7:38

Let $n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}$, where $p_i$ are disntinct prime numbers.

Then, $\varphi(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1)=2^2=1\cdot 4=2\cdot 2$.

Now it is easy to conclude $r=1$, $p_1=2$, $k_1=3$ or $p_1-1=4$, $p_1=5$, $k_1=1$ (remain case $p_1-1=2=p_2-1$, isn't possible since $p_1\neq p_2$).

Solutions are $n=8$ and $n=5$.

• What about $p_1 = 5$ and $k_1 = 1$? – dhk628 Aug 5 '16 at 7:06
• @ dhk628 Thanks for observing that, I added that solution. – alans Aug 5 '16 at 7:10
• Thanks. Can you briefly explain how you get the equation $\varphi(n)=p_1^{k_1-1}(p_1-1)\cdots p_r^{k_r-1}(p_r-1)$? Sorry I am new to this function and do not know too much about the property of this function. – Hopf eccentric Aug 5 '16 at 7:27
• The number of integers $t\leq p_i^{k_i}$ that are divisible by $p_i$ is $p_i^{k_i-1}$. Thus the number of $t$ not divisible by $p_i$ (or in other words, coprime to $p_i^{k_i}$) is $p_i^{k_i}-p_i^{k_i-1}=p_i^{k_i-1}(p_i-1)$ – JasonM Aug 5 '16 at 7:33

Consider the wiki

https://en.wikipedia.org/wiki/Euler%27s_totient_function#Unsolved_problems

and look up "totient numbers". There are many nontotient numbers. The page as a whole is very informative.

• Thanks. Yeah I have actually looked up the page before, and I found that $n=5,8,10,12$ satisfy $\varphi(n)=4$, and it also seems that the larger the $n$, the larger the $\varphi(n)$, so it seems natural to conjecture that these four are the only $n$'s with $\varphi(n)=4$. However I have no any rigorous argument before the answer's given here. – Hopf eccentric Aug 5 '16 at 8:04