1
$\begingroup$

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?

  • 0
    @Josue This only proves that $n \neq 5$.2016-03-03

2 Answers 2

3

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

1

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