# Find all integers such that ϕ(n) =n/2 [duplicate]

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.

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

• 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$. – Thomas Andrews Nov 10 '16 at 14:37
• More generally, you can solve $n\phi(x)=x$, where $n,x\in\mathbb Z^+$. math.stackexchange.com/a/1614135/236182 – user236182 Nov 10 '16 at 17:28
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. 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$. 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\$