8
$\begingroup$

I know that there is a similar post, but I 'm trying a different proof. I will write $P$ for the set of all positive prime numbers.

Question: If $\phi$ is Euler's Phi Function, we want to find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$.

Answer: Let $n=p_1^{n_1}\dotsb p_k^{n_k}\in \mathbb{Z}^+$ be the factorisation of $n$ in to primes. Then $$\phi(n)=p_1^{n_1-1} \dotsb p_k^{n_k-1}(p_1-1) \dotsb (p_k-1)=4.$$

So, for any $i \in \{1,2,\cdots,k\}$ we have $p_i-1|4$. Hence, $$p_i-1\in\{1,2,4\} \iff p_i\in \{2,3,5\} \subset P.$$ Now, we can see the primes that $n$ contains: $n=2^{n_1}3^{n_2}5^{n_3}$, where $n_1,n_2,n_3 \in \mathbb{Z}^+$. So,

\begin{align*} \phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4 \tag{*} \end{align*}

The possible cases for $n_i$ are:

  • $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively
  • $n_2=1 \implies \phi(3)=2$
  • $n_3=1 \implies \phi(5)=4$

All the posible combinations for the relation (*) are $\phi(5)$, $\phi(5)\phi(2)$, $\phi(3)\phi(2^2)$, $\phi(2^3)$. So, $$n \in \{5,10,12,8\}.$$

Is this completely right?

Thank you.

$\endgroup$
3
  • 2
    $\begingroup$ Look good to me. $\endgroup$
    – Igor Rivin
    Jan 2, 2017 at 20:26
  • 2
    $\begingroup$ Yes, its right! ( only a typo: n_2=n_3=1) $\endgroup$ Jan 2, 2017 at 20:29
  • $\begingroup$ Thank you for your answers. I fixed the typo. $\endgroup$
    – Chris
    Jan 2, 2017 at 20:35

1 Answer 1

3
$\begingroup$

This seems to be completely correct to me.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Can we work similarly to find all $n\in \mathbb{Z} ^+: \phi(n)=x$ for some $x>4$? $\endgroup$
    – Chris
    Jan 2, 2017 at 20:46
  • 3
    $\begingroup$ Yes, this technique is general, though the casework can be a difficult computation. $\endgroup$ Jan 2, 2017 at 20:53
  • 3
    $\begingroup$ @Chris, for the general case, see math.stackexchange.com/questions/23947/…. $\endgroup$
    – lhf
    Jan 2, 2017 at 21:08

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.