show that phi(n)=n/2 iff n=2^k for some positive integer k.
Proving that $\displaystyle
n = 2^a ,a \in \mathbb{Z}^ + \Rightarrow \phi \left( n \right) = \tfrac{n}
{2}
$ is a fairly easy so we will prove the converse $\displaystyle
\phi \left( n \right) = \tfrac{n}
{2} \Rightarrow n = 2^a ,a \in \mathbb{Z}^ +
$
I'll present 2 proofs
1)
If $\displaystyle n$ is odd, then $\displaystyle \tfrac{n}{2}$ is not an integer, so $\displaystyle \phi(n)=\tfrac{n}{2}$ is impossible since the LHS is an integer. Thus for that equality to hold, $\displaystyle n$ has to be even.
Then write $\displaystyle
n = 2^a \cdot b
$ with $\displaystyle a\in \mathbb{Z}^+$ and $\displaystyle (b,2)=1$
Now since $\displaystyle \phi$ is multiplicative : $\displaystyle
\phi \left( n \right) = \phi \left( {2^a \cdot b} \right) = \phi \left( {2^a } \right) \cdot \phi \left( b \right) = 2^{a-1} \cdot \phi \left( b \right)
$
If $\displaystyle b=1$ then $\displaystyle \phi(n)=\tfrac{n}{2}$ indeed holds, however if $\displaystyle b>1$ then $\displaystyle
\phi \left( b \right) < b
$ ( Since b is not coprime to itself now ), thus if $\displaystyle b>1 $ we have $\displaystyle
\phi \left( n \right) = 2^{a-1} \cdot \phi \left( b \right)<2^{a-1} \cdot b = \tfrac{n}{2}
$ thus $\displaystyle \phi(n)= \tfrac{n}{2}$ is impossible when $\displaystyle b>1$ and we are done.
2)
We have $\displaystyle
\phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
{p}} \right)}
$ so we have: $\displaystyle
n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
{p}} \right)} = \tfrac{n}
{2}
\Leftrightarrow \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}
{p}} \right)} = \tfrac{1}
{2}
$ $\displaystyle
\Leftrightarrow 2 \cdot \prod\limits_{\left. p \right|n} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n} p
$
This means that $\displaystyle
2\left| {\left( {\prod\limits_{\left. p \right|n} p } \right)} \right.
$ So 2 must be one of the primes there $\displaystyle
\Rightarrow 2 \cdot \prod\limits_{\left. p \right|n;p > 2} {\left( {p - 1} \right)} = 2 \cdot \prod\limits_{\left. p \right|n;p > 2} p
$ $\displaystyle
\Rightarrow \prod\limits_{\left. p \right|n;p > 2} {\left( {p - 1} \right)} = \prod\limits_{\left. p \right|n;p > 2} p
$ (now the product goes over the prime divisors of n which are greater than 2). But this obviously can't hold ( $\displaystyle
p - 1 < p
$) if there's a prime $\displaystyle q>2$ such that $\displaystyle q|n$. This means that 2 is the only prime dividing $\displaystyle n$ and we are done.