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

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.

• What is $\phi (n)$? The Euler-totient function? Commented Nov 16, 2013 at 21:56
• Yes. Sorry, I should have stated that. Commented Nov 16, 2013 at 21:57

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

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?

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

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

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.