Exercise 2.3.33 (Smallest positive integer $n$ so that $\phi(x) = n$ has no solution)

Proof.

a)

The equation $\varphi (x)=1$ has two solutions, $x=1$ or $x=2$. The equation $\varphi (x)=2$ has three solutions, $x=3$, $x=4$ or $x=6$.

We prove now that the equation $\varphi (x)=3$ has no solution. Let $x=p_1^{a_1}\cdots p_k^{a_k}$ be a solution, where $a_i\ge 1$. Then

$$3=p_1^{a_1-1}(p_1-1)\cdots p_k^{a_k-1}(p_k-1).$$

Therefore $p_i-1\mid 3$ for every index $i$, thus $p_i-1=1$ or $3$, so $p_i=2$. The only prime divisor of $x$ is $2$. Therefore $x=2^a$ is a power of $2$.

If $a=0$, $x=1$ and $\varphi (x)=\varphi (1)=1\ne 3$, so $x=2^0=1$ is not a solution.

If $a\ge 1$, then $\varphi (x)=2^{a-1}\ne 3$. This proves that $\varphi (x)=3$ has no solution.

The smallest positive integer $n$ so that $\varphi (x)=n$ has no solution is $3$.

b)

The equation $\varphi (x)=1$ has two solutions $1$ and $2$. We show that there is no other solution. If $x=p_1^{a_1}\cdots p_k^{a_k}>1$ is a solution, then $$1=p_1^{a_1-1}(p_1-1)\cdots p_k^{a_k-1}(p_k-1).$$

By the same reasoning $p_i-1\mid 1$, thus $p_i=2$, so $x=2^a$. If $a>1$, then $\varphi (x)=2^{a-1}=1$, and this is impossible. The only solutions are $1$ and $2$.

The smallest positive integer $n$ so that $\varphi (x)=n$ has exactly two solutions is $1$.

c)

The equation $\varphi (x)=2$ has $3$ solutions, $3,4$, and $6$. We show that there is no other solution. If $x=p_1^{a_1}\cdots p_k^{a_k}>1$ is a solution, then $$2=p_1^{a_1-1}(p_1-1)\cdots p_k^{a_k-1}(p_k-1).$$

Then $p_i-1\mid 2$, thus $p_i=2$ or $p_i=3$.

$$x=2^a{3}^b.$$

If $a>1$, then $2^{a-1}\mid \varphi (x)=2$, thus $a\le 2$.

If $b>1$, then $3^{b-1}\mid \varphi (x)=2$, so $3\mid 2$: this is impossible, so $0\le b\le 1$. This gives

$$x=2^a{3}^b,a=0,1,2,b=0,1,$$

so $x\in \{1,2,4,3,6,12\}$.

But $\varphi (1)=1,\varphi (2)=2,\varphi (12)=4$, so $1,2,12$ are not solutions. The only solutions are $3,4$ and $6$.

The smallest positive integer $n$ so that $\varphi (x)=n$ has exactly three solutions is $2$.

d)

The equation $\varphi (x)=4$ has $4$ solutions, $5,8,10,$ and $12$. We show that there is no other solution. If $x=p_1^{a_1}\cdots p_k^{a_k}>1$ is a solution, then $$4=p_1^{a_1-1}(p_1-1)\cdots p_k^{a_k-1}(p_k-1).$$

Therefore $p_i-1\mid 4$ for every index $i$, so $p_i\in \{2,3,5\}$, and

$$x=2^a{3}^b{5}^c.$$

If $c>1$, then $5\mid \varphi (n)=4$. This is false, so $c=0$ or $c=1$.

If $b>1$, then $3\mid \varphi (n)=4$. Same contradiction, so $b=0$ or $b=1$.

If $a>1$, then $2^{a-1}\mid 4$, thus $a-1\le 2$, $a\le 3$. This gives

$$x=2^a{3}^b{5}^c,a=0,1,2,3,b=0,1,c=0,1.$$

If $b=c=1$, then $2\times 4=8\mid \varphi (x)=4$. This is false, so $b=0$ or $c=0$. Therefore

$$x\in \{1,2,4,8,3,6,12,24,5,10,20,40\}.$$

The corresponding values of $\varphi (n)$ are given in the following array.

$$\begin{array}{ccccccccccccc}\hfill x\hfill & \hfill 1\hfill & \hfill 2\hfill & \hfill 4\hfill & \hfill 8\hfill & \hfill 3\hfill & \hfill 6\hfill & \hfill 12\hfill & \hfill 24\hfill & \hfill 5\hfill & \hfill 10\hfill & \hfill 20\hfill & \hfill 40\hfill \\ \hfill \varphi (x)\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 2\hfill & \hfill 4\hfill & \hfill 2\hfill & \hfill 2\hfill & \hfill 4\hfill & \hfill 8\hfill & \hfill 4\hfill & \hfill 4\hfill & \hfill 8\hfill & \hfill 16\hfill \end{array}$$

Therefore the only solutions of $\varphi (x)=4$ are $5,8,10$ and $12$.

The smallest positive integer $n$ so that $\varphi (x)=n$ has exactly four solutions is $4$.