0
$\begingroup$

This question already has an answer here:

I just came across this problem while studying the Euler-Totient function :

Find all integers such that $\phi(n)$ = $n$/2.

Now, I know that $\phi(n)$ gives the count of the total number of positive integers upto $n$ that are relatively prime to $n$. But I have no clue how to go about solving this question.

$\endgroup$

marked as duplicate by Dietrich Burde, Arthur, Ennar, Adam Hughes, André 3000 Nov 10 '16 at 14:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ There is a formula: $\frac{\phi(n)}{n} = \prod_{p\mid n} \frac{p-1}{p}$ where the product is taken over all primes $p$ which are divisors of $n$. $\endgroup$ – Thomas Andrews Nov 10 '16 at 14:37
  • $\begingroup$ More generally, you can solve $n\phi(x)=x$, where $n,x\in\mathbb Z^+$. math.stackexchange.com/a/1614135/236182 $\endgroup$ – user236182 Nov 10 '16 at 17:28
2
$\begingroup$

Suppose n= 2$^s$d where d is odd.

If $\phi(n)$=n/2, then 2 divides n, forcing s > 0.Thus $\phi(n)$ = $\phi(2^s)$.$\phi(d)$= 2$^{s-1}$$\phi(d)$.

This implies $\phi(d)$=d which can only happen when d=1. Hence, $\phi(n)$=n/2 only if n=2$^s$ for some s>0.

$\endgroup$
2
$\begingroup$

Recall the product formula for Euler's function.

$$\phi(n) = n\cdot \prod_{p|n}\left(1-{1\over p}\right)$$

Then in order for this to be exactly half of $n$ we need that the only prime dividing $n$ is $2$. Hence $n=2^k$.

$\endgroup$
0
$\begingroup$

If the highest power of prime $p$ that divides $n$ is $d(\ge1)$

For $p\ge3,$ the highest power of prime $p$ that divides $\phi(n)$ is $d-1$

So, $p\not\ge3$

Check for $n=2^k$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.