# $\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.

-
"I think I have it figured and would like to see if I am on the right track." Can you show us your reasoning? –  Alex Becker Jul 17 '12 at 2:45
@AlexBecker Definitely. So What I have is this. ($\implies$) suppose that $\phi(n)=\frac{n}{2}$. Let $n=2^ap_{1}^{e_{1}}p_{2}^{e_{2}}...p_{k}^{e_{k}}$ where $p_{i}$ for $1 \leq i \leq k$ are all distinct primes.Doing this arrives at an impossibility so all p's must be 2. and the other way is pretty straight forward. –  HowardRoark Jul 17 '12 at 2:51

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$.

-
I like. Thank you. I think I had similar reasoning to this. –  HowardRoark Jul 17 '12 at 2:54
Matter of taste. For representatives, I use $0$ to $m-1$, not $1$ to $m$. –  André Nicolas Jul 17 '12 at 3:17

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}.$

-
Just saw this proof. I am having trouble understanding your reasoning. From $q \ne p$... I just can seem to see it. you say q is prime but then say it is a multiple of p. –  HowardRoark Jul 19 '12 at 7:52
You misparsed the text: it means that both $\rm\:q\:$ and (the $\rm\:n/p\:$ multiples of $\rm\:p)\:$ are all not coprime to $\rm\:n\:$, i.e. the elements in $\rm\:[1,n]\:$ not-coprime to $\rm\:n\:$ contain not only all multiples of $\rm\:p\:$ but at least one additional element, viz. $\rm\:q\ \$ –  Bill Dubuque Jul 19 '12 at 12:52
OH! I see. I did misread it. It was late at night. I didn't see "the" n/p "multiples" of p. I read, "q and n/p are multiples of p". Thank you! –  HowardRoark Jul 19 '12 at 18:28

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.

-
If $n=2^k \Leftrightarrow \phi(n)=\phi(2^k)=2^k-2^{k-1}$, whenever k is graterthan 2
$\Leftrightarrow \phi(2^k)=2^{k-1}$
$\Leftrightarrow \phi(2^k)=\frac{2^k}{2}$
$\Leftrightarrow \phi(2^k)=\frac{n}{2}$