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

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)

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.

If $$n= p_1^{a_1}p_2^{a_2}...p_k^{a_k}$$ where $$a_i\geq 1$$ and $$p_1 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 ...

• That's nice. But is there a generalization for $\varphi(n)=k$ for any positive integer $k$? Feb 17, 2019 at 11:44
• I'm sorry, I don't know much theory about that. This is all I could do. Feb 17, 2019 at 11:51