Given $m\in\mathbb{N}$, is there a general way to solve the equation \begin{equation} \varphi(n)=m \end{equation} 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?

  • 1
    $\begingroup$ For related problems, see Ford's Theorem and Carmichael's Totient Conjecture. $\endgroup$ – 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$.

  • $\begingroup$ What about $p_1 = 5$ and $k_1 = 1$? $\endgroup$ – dhk628 Aug 5 '16 at 7:06
  • $\begingroup$ @ dhk628 Thanks for observing that, I added that solution. $\endgroup$ – alans Aug 5 '16 at 7:10
  • $\begingroup$ 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. $\endgroup$ – Hopf eccentric Aug 5 '16 at 7:27
  • 3
    $\begingroup$ 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)$ $\endgroup$ – JasonM Aug 5 '16 at 7:33

Consider the wiki


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

  • $\begingroup$ 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. $\endgroup$ – Hopf eccentric Aug 5 '16 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.