2
$\begingroup$

Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$

I know $$x=\prod_\limits{i} p_i^{a_1} =p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3} \ldots p_n^{a_n}$$ $$\phi(x)=x\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\left(1-\frac{1}{p_3}\right)\ldots \left(1-\frac{1}{p_n}\right)$$

But still don't know to solve it. Can anyone help me?

$\endgroup$
3
  • 5
    $\begingroup$ This was an answer (a hint) here. It is not good to start a new question there without reference. $\endgroup$ Jan 15 '16 at 21:35
  • $\begingroup$ This is not an answer just a formula @DietrichBurde $\endgroup$
    – mod
    Jan 15 '16 at 21:37
  • 1
    $\begingroup$ More generally, you can solve $n\phi(x)=x$ with $n,x\in\mathbb Z^+$. See this answer. All the solutions are $(n,x)=(1,1),\left(2,2^a\right),\left(3,2^b3^c\right)$ for any $a,b,c\in\mathbb Z^+$. $\endgroup$
    – user236182
    Jan 17 '16 at 15:32
3
$\begingroup$

Hint: $\phi(n) = n \prod_{p | n} \left( 1 - \frac{1}{p} \right)$, so if $\phi(n)=n/2$, then $$\prod_{p | n} \left( 1 - \frac{1}{p} \right)=\frac{1}{2}.$$ If $n$ is a power of $2$, what can we conclude?

If $n$ is not a power of $2$, what can we conclude?

$\endgroup$
2
$\begingroup$

Let $x=2^kh$ with $k\in\mathbb Z_{\ge 0}$, $h\in\mathbb Z_{\ge 1}$, $h$ odd.

$2\phi(x)=x$ implies $k\ge 1$, so $\phi(2^kh)=2^{k-1}h$.

Now use the multiplicativity of the $\phi$ function: $2^{k-1}\phi(h)=2^{k-1}h$,

i.e. $\phi(h)=h$, i.e. $h=1$, i.e. $x=2^k$, which is a solution for all $k\in\mathbb Z_{\ge 1}$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.