6
$\begingroup$

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

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

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

So, $\forall i \in \{1,2,...,k \} \implies p_i-1|4 $ . And from this, we have that

$$p_i-1\in\{1,2,4 \} \implies p_i\in \{2,3,5\} \in P$$ Now, we can see the primes that $n$ containts: $n=2^{n_1}3^{n_2}5^{n_3}, \ n_1,n_2,n_3 \in \mathbb{Z}^+$. So, $$\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 \ (*)$$

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$
  • 2
    $\begingroup$ Look good to me. $\endgroup$ – Igor Rivin Jan 2 '17 at 20:26
  • 2
    $\begingroup$ Yes, its right! ( only a typo: n_2=n_3=1) $\endgroup$ – Martín Vacas Vignolo Jan 2 '17 at 20:29
  • $\begingroup$ Thank you for your answers. I fixed the typo. $\endgroup$ – Chris Jan 2 '17 at 20:35
3
$\begingroup$

This seems to be completely correct to me.

$\endgroup$
  • $\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 '17 at 20:46
  • 2
    $\begingroup$ Yes, this technique is general, though the casework can be a difficult computation. $\endgroup$ – Stella Biderman Jan 2 '17 at 20:53
  • 3
    $\begingroup$ @Chris, for the general case, see math.stackexchange.com/questions/23947/…. $\endgroup$ – lhf Jan 2 '17 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.