2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ For related problems, see Ford's Theorem and Carmichael's Totient Conjecture. $\endgroup$
    – JasonM
    Aug 5 '16 at 7:38
  • 5
    $\begingroup$ Does this answer your question? How to solve the equation $\phi(n) = k$? $\endgroup$
    – MCCCS
    Aug 4 '20 at 16:21
3
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ What about $p_1 = 5$ and $k_1 = 1$? $\endgroup$ 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$ 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
  • $\begingroup$ Solutions are $5$, $8$, $10$, $12$ $\endgroup$
    – MCCCS
    Aug 4 '20 at 16:26
0
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Aug 5 '16 at 8:04

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