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.

  • 4
    $\begingroup$ "I think I have it figured and would like to see if I am on the right track." Can you show us your reasoning? $\endgroup$ – Alex Becker Jul 17 '12 at 2:45
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ I like. Thank you. I think I had similar reasoning to this. $\endgroup$ – HowardRoark Jul 17 '12 at 2:54
  • $\begingroup$ Matter of taste. For representatives, I use $0$ to $m-1$, not $1$ to $m$. $\endgroup$ – 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}.$

  • $\begingroup$ 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. $\endgroup$ – HowardRoark Jul 19 '12 at 7:52
  • $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Jul 19 '12 at 12:52
  • $\begingroup$ 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! $\endgroup$ – 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}$

but this is true except one case(k=1).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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