1
$\begingroup$

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.

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

5 Answers 5

5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .