6
$\begingroup$

Find all positive integers $n$ such that $\varphi(\varphi(n)) = 2.$

Let $\varphi(n)=m$ so I need the integers $m$ such that $\varphi(m)=2$. I know that $3,4,6$ work but I need to see if there are no others.

If $m$ is prime then $m=3$

Suppose that $m$ is even then $m=2^a(x)$ such that $x$ is odd.

$\varphi(2^a(x))$ since the $gcd(2^a,x)=1$ you have that $\varphi(2^a(x))=2^{a-1}\varphi(x)$. So if $a$ is $1$ then you have that $\varphi(m)=\varphi(x)$ so $x$ is composite let $x=uv$ where $u$ and $v$ are relatively prime and greater then one. So I get that $\varphi(x)=\varphi(u)\varphi(v)$ which $\varphi(u)\geq 2$ and $\varphi(v)\geq(2)$ then $\varphi(x)\geq4$. Also if $m$ is odd you can use the same argument to show that $\varphi(m) \geq 4$

I'm having trouble tying it together to show that you will only get $4$ and $6$ as the only solutions in the case where $m$ is not prime.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

We're solving $\varphi(m)=2$.

If $m$ has two different odd prime factors $p$ and $q$, then $\varphi(m)$ is a multiple of $(p-1)(q-1) \ge 4$. So, $m$ has at most one odd prime factor $p$.

Write $m=2^a p^b$.

If $b>1$, then $\varphi(m)$ is a multiple of $p$ and so cannot be $2$. So, $b\le1$.

If $b=0$, then $m=2^a$ and so $a=2$ and $m=4$.

If $b=1$ and $a\ge 1$, then $\varphi(m)=2^{a-1}(p-1)$. Then $a=1$ and $p=3$, and so $m=6$.

Otherwise, $b=1$ and $a=0$ and so $m=3$.

$\endgroup$

You must log in to answer this question.

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