Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
"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

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer
    
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}.$

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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