$\phi(n)=\frac{n}{2}$ if and only if $n=2^k$ for some positive integer k

Show that $\phi(n)=\frac{n}{2}$ if and only if $n=2^k$ for some positive integer k. I think I have it figured and would like to see if I am on the right track. Thank you.

Solution 1:

Suppose that $n=2^k$ where $k$ is positive. Then the numbers in the interval $0 \le a \le 2^k-1$ which are relatively prime to $2^k$ are precisely the odd numbers in this interval. Since half the numbers in our interval are odd and half are even, $\varphi(n)=n/2$.

Conversely, suppose that $\varphi(n)=n/2$. Then $n$ is even. Let $n=2^k b$ where $b$ is odd. Then by the multiplicativity of $\varphi$, we have $\varphi(n)=2^{k-1}\varphi(b)$. If this is equal to $n/2$, then $2^{k-1}\varphi(b)=2^{k-1}b$, and therefore $\varphi(b)=b$. This is only possible if $b=1$. (If $b\gt 1$, then $0$ is not relatively prime to $b$.)

Remark: The proof can be done at a lower level, just using the definition of $\varphi(n)$. Suppose that $\varphi(n)=n/2$. Then $n=2^kb$ for some positive $k$ and odd $b$. There are $n/2$ even numbers in the interval $0\le a \lt 2^kb$, and none is relatively prime tp $n$. So if $\varphi(n)=n/2$, all the rest must be. But if $b \gt 1$, then $b$ is not relatively prime to $n$, so $\varphi(n)\lt n/2$. It follows that $b=1$.

Solution 2:

Hint $\ $ The proof is just as simple for any prime power, namely

Theorem $\rm\ \ \phi(n)\, =\, n - {\bf \color{#0A0}{n/p}}\, \iff\, n = p^k$

Proof $\rm\ (\Leftarrow)\ \, $ The integers $\rm\in[1,n]\,$ not coprime to $\rm\,n = p^k\,$ are $\rm\,k\!\ p,\ k = 1,2,\ldots, {\bf \color{#0A0}{n/p}}.$

$(\Rightarrow)\ \, $ $\rm\phi(n)\, =\, n-n/p\in\mathbb Z\:\Rightarrow\:p\:|\:n,\,$ so if $\rm\:n\ne p^k\,$ then some prime $\rm\:q\ne p\,$ also divides $\rm\,n,\,$ hence both $\rm\:\bf\color{#C00}q\:$ and the $\rm\:\bf\color{#0A0}{n/p}\:$ multiples of $\rm\,p\,$ are not coprime to $\rm\:n,$ thus $\rm\:\phi(n) \le n - {\bf\color{#0A0}{n/p}} - {\bf \color{#C00}1}.$

Solution 3:

Since $\phi(n)=n/2$, $n$ is even. We have, $\phi(n)/n=\prod_{p|n}(1-1/p)=1/2\prod_{p|n, p\neq2}\frac{p-1}{p}$. Note that $\frac{p-1}{p}<1$ for any prime $p$. and so it multiplied to $1/2$ must be less than 1/2.