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

divisibilityelementary-number-theorymodular arithmeticnumber theorytotient-function

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.

Best Answer

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

Related Question