Find all positive integers $n$ such that $\phi(n)=6$.

I am asked to find all positive integers $n$ such that $\phi(n)=6$, and to prove that I have found all solutions.

The way I am tackling this is by constructing all combinations of prime powers such that when passed to Euler's function will yield $6$.

For example, I know that $\phi(7)=6$, $\phi(3^2)=6$, and $\phi(2)=1$. Therefore, the numbers should be $7$, $7\cdot2=14$, $3^2=9$, and $3^2\cdot2=18$.

I believe that there cannot possibly be any others because of the way the $\phi$ function is defined. What do you guys think?

We give an "examination of all cases" solution. Use the fact that $\varphi(n)$ is multiplicative. Let $$n=2^a p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$ where the $p_i$ are distinct odd primes, the $e_i$ are $\ge 1$, and $a \ge 0$. Then $$\varphi(n)=\varphi(2^a)\varphi(p_1^{e_1})\varphi(p_2^{e_2})\cdots \varphi(p_k^{e_k}).$$

We find all $n$ such that $\varphi(n)=6$. If $k \ge 2$, then since $\varphi(p_i^{e_i})$ is even, $\varphi(n)$ is divisible by $4$, so cannot be equal to $6$.

If $k=0$, then $\varphi(n)=\varphi(2^a)$. But $\varphi(2^a)=1$ if $a=0$ and $\varphi(2^a)=2^{a-1}$ if $a \ge 1$. So if $k=0$ we cannot have $\varphi(n)=6$. We conclude that $k=1$. Thus $n$ must have the shape $2^ap^e$, where $a \ge 0$ and $p$ is an odd prime.

But $\varphi(p^e)=p^{e-1}(p-1)$. It follows that $p \le 7$. If $p=7$, then $p-1=6$, so we must have $e=1$ and $\varphi(2^a)=1$. This gives the solutions $n=7$ and $n=14$.

We cannot have $p=5$, for $4$ divides $\varphi(5^e)$.

Let $p=3$. If $e \ge 3$, then $\varphi(3^e)\ge (3^2)(2)$. So we are left with the possibilities $e=1$ and $e=2$.

If $e=1$, then $\varphi(n)=\varphi(2^a)(2)$. This cannot be $6$.

Finally, we deal with the case $e=2$. Note that $\varphi(3^2)=6$. So to have $\varphi(2^a3^2)=6$, we need $\varphi(2^a)=1$, which gives $n=9$ and $n=18$.

Following condition has to be satisfied :

$$\frac{n}{e^{\gamma}\ln(\ln n)+\frac{3}{\ln(\ln n)}} < 6 \leq n-1$$

where $\gamma \approx 0.577$

Hence : $n\in [7,27]$

Therefore you have to check integers from this interval only...

Solution should be : $n \in\{7,9,14,18\}$