Difficulty proving if $k$ is a positive integer such that equation $\phi(n) = k$ has unique positive integer solution $n$, show $4 \,\, | \,\,k$.

Question

I am having difficulty solving the following problem:

Suppose $k$ is a positive integer such that the equation $\phi(n) = k$ has a unique positive integer solution $n$. Show that $4$ divides $k$.

This is what I have so far:

$$ \begin{align} \phi(n) &= \phi(2^{x}b)\\ &= \phi(2^{x})\phi(b)\\ &= 2^{x - 1}\phi(b)\\ &= 4(2^{x - 3})\phi(b) \end{align} $$

Which proves that $4 \,\, | \,\, k$ if $x \geq 3$. However, I don't know how to prove that $4 \,\, | \,\, k$ if $\phi(n) = k$ has a unique positive integer solution $n$.

If anybody could provide me with the right direction, that would be greatly appreciated.

Answer 1

We show the contrapositive, that if $4\nmid k$ for a given positive integer $k$, then $\varphi(n)=k$ has multiple solutions.

Let $n=\prod p^{n_p}$ be a positive integer and $k=\varphi(n)$. The expansion $$\varphi(n)=\varphi\left(\prod p^{n_p}\right)=\prod\varphi(p^{n_p})=\prod p^{n_p-1}(p-1),$$ shows that if $4\nmid k$ then $n$ is not divisible by an prime $p\equiv1\pmod{4}$, and not divisible by two distinct odd prime numbers, and not divisible by $2^3$. In fact we see that either $n=1,2,4$, $n=p^m$ or $n=2p^m$ for some prime number $p\equiv3\pmod{4}$ and some nonnegative integer $m$. But then the identities \begin{eqnarray*} \varphi(1)&=&\varphi(2)\\ \qquad\varphi(3)&=&\varphi(4)\\ \varphi(2p^m)&=&\varphi(2)\varphi(p^m)=\varphi(p^m), \end{eqnarray*} show that $n$ is not the unique solution to $\varphi(n)=k$.

Answer 2

We can write $n=2^am$ where $a\geq 0$ and $m$ odd.

• If $a=0$ then $\phi (2n)= \phi(2)\phi (n) = k$ so given equation has 2 solution.

• If $a=1$ then $\phi(m) = \phi(2)\phi (m) =\phi (n)= k$ so given equation has 2 solution again.

• If $a\geq 2$ and $m\geq 3$ then $k= \phi(n) = \phi(2^a)\phi (m) = 2^{a-1}\cdot\underbrace{\phi(m)}_{even}$ so $4\mid k$.

• If $a\geq 3$ and $m=1$ then $k= \phi(n) = \phi(2^a) = 2^{a-1}$ so $4\mid k$.

• If $a=2$ and $m=1$ we have $n=4$ so $k =2$, but then $\phi(3) =2$ so we have 2 solutions again.

Now we see that if we don't have two solution then $4\mid k$.