Find All $n \in \mathbb{Z^+}$ Such That $\phi(n)=4

Sorry, we no longer support your browser Please upgrade to Microsoft Edge, Google Chrome, or Firefox. Learn more about our browser support.

1. 1. Home
   2. Questions
   3. Tags
   4. Users
   5. Unanswered
2. Teams

   Ask questions, find answers and collaborate at work with Stack Overflow for Teams.

   Try Teams for free Explore Teams
3. Teams

4. Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Teams

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Learn more about Teams Find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$ Ask Question Asked 7 years, 10 months ago Modified 2 years, 3 months ago Viewed 4k times 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.

• number-theory
• elementary-set-theory
• solution-verification

Share Cite Follow edited Aug 7, 2022 at 17:28 Shaun♦ 47k2020 gold badges7171 silver badges183183 bronze badges asked Jan 2, 2017 at 20:25 ChrisChris 2,84211 gold badge1717 silver badges3535 bronze badges $\endgroup$ 3

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

Add a comment |

1 Answer 1

Sorted by: Reset to default Highest score (default) Date modified (newest first) Date created (oldest first) 3 $\begingroup$

This seems to be completely correct to me.

Share Cite Follow answered Jan 2, 2017 at 20:35 Stella BidermanStella Biderman 31.3k66 gold badges4848 silver badges9494 bronze badges $\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 Commented Jan 2, 2017 at 20:46
• 3 $\begingroup$ Yes, this technique is general, though the casework can be a difficult computation. $\endgroup$ – Stella Biderman Commented Jan 2, 2017 at 20:53
• 3 $\begingroup$ @Chris, for the general case, see math.stackexchange.com/questions/23947/…. $\endgroup$ – lhf Commented 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 Commented Jul 31, 2022 at 16:41

Add a comment |

You must log in to answer this question.

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

• number-theory
• elementary-set-theory
• solution-verification

.

• Featured on Meta
• More network sites to see advertising test
• We’re (finally!) going to the cloud!

Linked

0 Euler's totient function determining $\phi(m)$= 2 using the product formula. 18 How to solve the equation $\phi(n) = k$? 0 Find smallest $N_0$ such that $\phi(n)\geq 5 \; \forall n\geq N_0$

Related

1 Sum of All Multiplication of Partitions 4 Prove that it is sufficient to check $\lceil \log(k) \rceil$ pairs to tell if a set of integers is pairwise coprime 6 For any sequence of real numbers, one can always find a subsequence that is monotone 2 Are there numbers $N$ such that $N^2=n_1^2+n_2^2+\cdots+n_k^2+1$ 7 The set of all finite subsets of $\mathbb{Z}_+$ is countable. Is my proof correct? 3 Upper bound of prime counter function

Hot Network Questions

• Why does 写真に収めとこ mean take a picture? And what is the purpose of とこ in this case?
• Installing MacTex on new machine -- where do my .cls and .sty files go?
• What is the Calvinist/Reformed solution to the Problem of Hell?
• Was it really possible to damage my VGA card by programming it in assembly through its latches registers?
• What should I do with a package that is delivered to my address but the name is wrong?
• Discrimination on the grounds of unsavoury religious beliefs?
• How to handle a campaign where the players are trapped inside a monster controlled by another player?
• Are "Albergue de peregrinos" typically restricted to pilgrims?
• Why the second C in "recyceln" is pronounced [k] instead of [ts]?
• Did Superdana manufacture a 66 AC outlet power strip/surge protector?
• A dark animated movie about an orphaned girl working in an oppressive factory
• Darlington-driven PNP vs. MOSFET
• Superimposed triangles
• Can a contradiction exist in the antecedent of a sequent?
• How to protect against fake gold bars?
• How were lead sheets made in the Graeco-Roman world?
• Does the twin paradox hold in a universe that's empty except for the twins?
• Is my evaluation for this multiple linear regression correct?
• Do longer papers have lower chances of being accepted because they take up more "space" in a journal issue (STEM)
• Generator breaker trips when hooked up for backfeed
• Brushing pastries with jam
• Accused of violating NDA on thesis
• How does time dilation affect the synchronization of clocks in different gravitational potentials?
• Scandinavian film, 1980s, possibly called Royal Toilet?

more hot questions Question feed Subscribe to RSS Question feed

To subscribe to this RSS feed, copy and paste this URL into your RSS reader.