Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$

Attempt: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies \frac{n}{2}=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$ $\implies p_1p_2\dots p_k=2(p_1-1)(p_2-1)\cdots (p_k-1)$.

Unable to go further. Please help.

The converse part: If $n=2^k$ then $\phi(n)=\phi(2^k)=2^k(1-1/2)=n/2.$ (proved)


Expanding on Thomas's hint, and writing out the comments:

Wikipedia on Euclid's Lemma:

If a prime divides the product of two numbers, it must divide at least one of those numbers.

I'll leave you to figure out why this can be applied to a product of more than two numbers.

$p_k$ is the largest prime factor, and it's a factor of $2(p_1−1)(p_2−1)⋯(p_k−1)$.

Euclid's lemma says it must divide at least one of them. So which one does it divide?

Assume $p_k > 2$. Then $p_k \nmid 2$

Does $p_k | (p_1-1)$? $p_k | (p_2-1)$? Etc.

For the other case, $p_k = 2$, the problem is over.

  • $\begingroup$ Thank you for the answer. I understand the solution. Now $p_k=max({p_i})=2$, then $p_i=2$ for all $i=1,2,\cdots k-1$. Then $n=p_1\dots p_k=2^k$. Is it not correct? $\endgroup$ – user1942348 Apr 26 '15 at 9:21
  • $\begingroup$ I don't know. I'd have to look more closely at your entire argument to tell. One thing that's throwing me off is that you use $k$ in several places in your argument, but I'm not sure you intend for it to be the same $k$. Sorry I couldn't help you. Good luck. $\endgroup$ – r12 Apr 26 '15 at 10:37

Hint: Let $p_k$ be the largest prime factor. It is a factor of:

$$2(p_1-1)(p_2-1)\cdots (p_k-1)$$

  • $\begingroup$ Please explain in details. $\endgroup$ – user1942348 Apr 25 '15 at 14:54
  • $\begingroup$ Sorry, that's it for today. This is a nearly complete hint. $\endgroup$ – Thomas Andrews Apr 25 '15 at 14:55
  • $\begingroup$ @user1942348 but $p_k$ is co-prime to any $m$ if $m<p_k$, so $p_k-1 \dots p_1-1$ are all co-prime to $p_k$ so $p_k|2$. $\endgroup$ – Alexey Burdin Apr 25 '15 at 14:59
  • $\begingroup$ @AlexeyBurdin Not understand, would you please explain. $\endgroup$ – user1942348 Apr 25 '15 at 15:06
  • $\begingroup$ @user1942348: Let $p_k$ be the largest prime among $p_1,\dots,p_k$, so $p_i-1<p_k$ , so $(p_i-1,p_k)=1$ due to $p_k$ is a prime and $p_i-1<p_k$. So $((p_1-1)(p_2-1)\dots(p_k-1),p_k)=1$. But $p_k|2(p_1-1)(p_2-1)\dots(p_k-1)$ so $p_k|2$. $\endgroup$ – Alexey Burdin Apr 25 '15 at 15:24

Write $n$ as $n=2^km$, where $\gcd(m,2) = 1$. This gives us $$\phi(n) = \phi(2^k) \phi(m) = 2^{k-1} \phi(m) \,\,\,\, (\spadesuit)$$ We are also given that $$\phi(n) = \dfrac{n}2 = 2^{k-1}m \,\,\,\, (\clubsuit)$$ Comparing $(\spadesuit)$ and $(\clubsuit)$, we obtain that $\phi(m) = m$. This means $m=1$ is the only possibility, since for $m > 1$, we have $\phi(m) < m$. Hence, we obtain $n=2^k m$.


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.