Find at least $5$ integers $n$ such that $\varphi(n)=16$

Question

Let $\varphi(n)$ denote Euler's totient function. Find all integers such that $\varphi(n)=16$.

Answers given were $17,32,34,40,48.$

I am thinking a generalisation of this problem: is there a way to find all positive integers $n$ such that $\varphi(n)=k$ for a specific $k$? Is there a way to do it other than trial and error? (which is what I did BTW)

Answer 1

Here is a very good page on this problem.

It has a calculator that finds all solutions to inverting the Euler totient $\phi$. I put in $16$ and it found that there are exactly six solutions: $$34, 60, 40, 48, 32, 17.$$

It also gives links describing the algorithm used to them (which involves traversing some tree) and the complexity of the problem.

Answer 2

If $$n= p_1^{a_1}p_2^{a_2}...p_k^{a_k}$$ where $a_i\geq 1$ and $p_1<p_2<...<p_k$ then we have $$\phi(n) = p_1^{a_1-1}p_2^{a_2-1}...p_k^{a_k-1} (p_1-1)...(p_k-1)$$

$$16= p_1^{a_1-1}p_2^{a_2-1}...p_k^{a_k-1} (p_1-1)...(p_k-1)$$

---

If $p_1=2$ and $k>1$ $$2^4= 2^{a_1-1}p_2^{a_2-1}...p_k^{a_k-1} (p_2-1)...(p_k-1)$$

then $a_i=1$ for all $i>1$, so we have $$2^4= 2^{a_1-1} (p_2-1)...(p_k-1)$$

Now if $a_1 = 1$ then $k\leq 5$ so $$ 2^4= (p_2-1)...(p_k-1)$$ and thus $p_k\leq 17$.

We see that $k=2$ and $p_2 = 17$ does works, so $\boxed{ n_1=34}$ and it is the only one if $a_1=1$

If $a_1 = 2$ then $k\leq 4$ so $$ 2^3= (p_2-1)...(p_k-1)$$ and thus $p_k\leq 7$. We see that $p_2 =3$ and $p_3=5$ works, so $\boxed{ n_2 = 60}$

If $a_1 = 3$ then $k\leq 3$ so $$ 2^2= (p_2-1)...(p_k-1)$$ and thus $p_k\leq 5$. We see that $p_2 =5$ works, so $\boxed{ n_3 = 40}$

If $a_1 = 4$ then $k=2$ so $$ 2= p_2-1$$ so $p_2 =3$ works, so $\boxed{n_4 = 48}$

If $a_1 =5$ then o $\boxed{n_5 = 32}$ and we have 5 numbers

---

If $p_1 >2$ then ...