If $n = 2 \varphi(n)$, then $n = 2^j$ for some positive integer $j$.

Question

Let $n$ be a positive integer such that $n=2\varphi(n)$. Show that $n=2^j$ for a positive integer $j$.

Basically I'm completely stumped on this question, I have no idea where to begin or what to do.

Answer 1

Look at the formula $$\phi(n) = n\prod_{p\mid n} \left(1-\frac{1}{p}\right)$$

and compare this with what you require:

$$\phi(n) = \frac12 n$$

This tells you that the only possible prime factors of $n$ is 2 ...

Answer 2

Hint Note that $n$ is even, because $n=2\phi(n)$, and so already $2,4,6,\ldots,n-2,n$ are not coprime to $n$ (count them).

Now look at the remaining $\{1,3,5\ldots,n-1\}$, can any of these not be coprime to $n$ ? Why? What does that imply?

Answer 3

Write $n=2^k m$ such that $gcd(m,2)=1$. Your equation leads to $\phi(m)=m$, hence $m=1$. QED

Answer 4

Well... $\phi (n)$ divides $n/p$, $p>2$ prime, whenever $n/p$ is an integer. This then implies that $n = k\cdot p\cdot \phi (n)$, where $k \in \mathbb{Z^{+}}$. So, $p \leq 2$. This completes the proof.

Answer 5

$n$ is even. Write $n=2^ka$ where $a$ is odd.

Then

$$2^ka=2\phi(2^ka)=2\phi(2^k)\phi(a)=2^k\phi(a)$$

Thus you get

$$\phi(a)=a$$

It is easy to prove that this implies $a=1$.