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.

For which Natural $n\ge2$ does this occur with?: $\phi(n)=n/2$

share|improve this question
    
What have you tried? –  Tobias Kildetoft Feb 5 '13 at 20:19
    
Tried breaking it down to a multiplication of prime numbers and kinda stuck there, its really late here and I'm tired, my test is tomorrow, could really use the help without any hints and stuff like that..thanks.. –  Rachel Bernoulli Feb 5 '13 at 20:21
add comment

3 Answers

up vote 4 down vote accepted

$$n=\prod_{k=1}^rp_k^{a_k}\;\;,\;\;p_k\,\,\text{primes}\,\,,\,\,0<a_k\in\Bbb N\Longrightarrow$$

$$\phi(n)=n\prod_{k=1}^r\left(1-\frac{1}{p_k}\right)$$

and then

$$\frac{n}{2}=\phi(n)\Longleftrightarrow 2\prod_{k=1}^r\left(1-\frac{1}{p_k}\right)=1\Longleftrightarrow\ldots$$

Can you take it from here?

share|improve this answer
    
not really, I mean I understood all of that but don't see how to continue –  Rachel Bernoulli Feb 5 '13 at 20:29
    
Well, it must be that the product in the last line equals $\,1/2\,$, right? So what exactly are the possible primes that participate in that product (and, thus that are part of the prime decomposition of $\,n\,$)? –  DonAntonio Feb 5 '13 at 20:36
1  
The Ritalin affect wore off, I'm sorry, but all i can think of is Pk=2 and then n=2.. –  Rachel Bernoulli Feb 5 '13 at 20:39
    
Your Ritalin worked all right: it's clear that if there's a prime different from $\,2\,$ in the prime decomposition of $\,n\,$ then that last product cannot be $\,1/2\,$ ...! –  DonAntonio Feb 5 '13 at 20:46
1  
Well, Allrighty then! thanks you very much kind sir :] –  Rachel Bernoulli Feb 5 '13 at 20:57
show 1 more comment

We need $n$ even so that $n/2$ is an integer. So write $n=2^\beta p_1^{a_1}\cdots p_k^{a_k}$ where $\beta\geq 1$, and the $p_i$ are odd primes.

By multiplicativity of the totient function, $\phi(n)=n/2$ means $$ 2^{\beta-1}p_1^{a_1-1}\cdots p_k^{a_k-1}(2-1)(p_1-1)\cdots(p_k-1)=2^{\beta-1}p_1^{a_1}\cdots p_k^{a_k}. $$ Rearranging, we see that this is equivalent to $$ (p_1-1)\cdots (p_k-1)=p_1\cdots p_k. $$ Since the $p_i$ are all odd primes, the LHS is even, while the RHS is odd. So this is impossible if $k\geq 1$. (This could also be concluded by the obvious fact that the LHS is strictly less than the RHS.) So necessarily $n=2^\beta$ for some $\beta$. It should be clear that all numbers of this form satisfy the property $\phi(n)=n/2$.

share|improve this answer
add comment

Hint: $n$ is even, or $n/2$ wouldn't be an integer. Hence $n=2^km$ with $m$ odd and $k\ge1$. You have $\phi(2^km)=2^{k-1}\phi(m)$ which must equal $n/2$.

share|improve this answer
    
my conclustion is that phi(m)=m -> Which number satisfy that? –  user1932595 Apr 4 '13 at 6:44
    
@user1932595: Well, m would have to be coprime to 1, 2, ..., n. How many numbers do you know which are coprime to themselves? –  Charles Apr 4 '13 at 14:49
    
That gives you the odd part m; of course k can be any positive integer. –  Charles Apr 4 '13 at 14:49
add comment

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.