10
$\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$
4
  • $\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
  • $\begingroup$ See also A Method for Solving $\Phi (x) =n$ L. L. Pennisi The American Mathematical Monthly Vol. 64, No. 7 (Aug. - Sep., 1957), pp. 497-499 (3 pages) Published By: Taylor & Francis, Ltd. doi.org/10.2307/2308462 jstor.org/stable/2308462 $\endgroup$
    – Chris
    Jul 31, 2022 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .