# If $n=2\phi(n)$, then $n=2^j$. [duplicate]

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?

-

## marked as duplicate by Martin Sleziak, Claude Leibovici, Newb, Yiyuan Lee, ShuchangMar 22 '14 at 6:42

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
@Josue This only proves that $n \neq 5$. – Nima Bavari Mar 3 at 21:07

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

-

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

-