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.

This question already has an answer here:

I need to show that if $n=2\phi(n)$, then $n=2^j$, where $n,j\in\mathbb{N}$.

I have a strong feeling that this can only be shown by contradiction. Therefore, I assumed that both $n=2\phi(n)$ and $n\neq2^j$. Then if we let, say, $n=5$, it follows that $5=2\cdot\phi(5)=8$, which is a contradiction. Hence, it must be the case that $n=2^j$.

Is this a valid proof?

share|improve this question

marked as duplicate by Martin Sleziak, Claude Leibovici, Newb, Yiyuan Lee, Shuchang Mar 22 at 6:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
No, it's not a valid proof. What if $n$ is not $2^j$ and it's not $5$ either? –  Arturo Magidin Apr 4 '12 at 15:08

2 Answers 2

up vote 3 down vote accepted

Let $n=2^jm$ with $m$ odd.

Then

$$2^jm= 2 \phi(2^j) \phi(m)=2^j \phi(m)$$

Thus

$$m= \phi(m)$$

which implies that $m=1$(Why?)

share|improve this answer

You cannot pick an alternative to $n=2^j$ out of thin air and work only on that alternative. What if $n=7$? What if $n=573428901367503218567329178542$? You never considered those.

Write $n=p_1^{a_1}\cdots p_r^{a_r}$, as the prime factorization of $n$, with $p_1\lt p_2\lt\cdots\lt p_r$ distinct primes, $a_i\gt 0$ for each $i$. Then $$\phi(n) = (p_1-1)p_1^{a_1}\cdots (p_r-1)p_r^{a_r-1}.$$ If $r\gt 1$, then the largest power of $p_r$ that divides $2\phi(n)$ is $a_r-1$ (prove it; it takes half a line), while the largest power of $p_r$ that divides $n$ is of course $a_r$. Since $a_r-1\neq a_r$, we get a contradiction. Thus, $r=1$, so $n$ is a prime power.

Therefore, $n=p_1^{a_1}$, $\phi(n) = (p_1-1)p_1^{a_1-1}$, and $p_1^{a_1} = 2(p_1-1)p_1^{a_1-1}$. Therefore...

share|improve this answer

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