Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$

Question

I am trying to figure out easy understandable approach to given small number of $n$, list all possible is with proof, I read this paper but it is really beyond my level to fathom,

attempt for $\phi(n)=110$,

$$\phi(n)=110=(2^x)\cdot(3^b)\cdot(11^c)\cdot(23^d)\quad\text{ since }\quad p-1 \mid \phi(n)=110$$ and $x =\{0,1\}$, $b=\{0,1\}$, $c=\{0,1,2\}$, $d=\{0,1\}$ .

So total $2\cdot2\cdot3\cdot2 =24$ options to test if the $\phi(n)=110$,

I am not sure if this is a enough to show or there are no other numbers.

look at this paper http://arxiv.org/pdf/math/0404116v3.pdf

Answer 1

If $$n=\prod_{p\,{\rm prime}}p^{\alpha(p)}\ ,$$ then you need $$\prod_{p\,{\rm prime}}p^{\alpha(p)-1}(p-1)=110\ .$$ Since $11\mid110$ you must have $p=11$ as one of the factors on the LHS. (It can't be $p-1=11$ as $12$ is not prime.). Then the exponent must be $\alpha(11)-1=1$ since $11^2\not\mid110$, and the $p-1$ factor is $10$. This accounts for all the non-trivial factors on the LHS, but you could also have a factor of $1$ in the form $$1=2^{1-1}(2-1)\ .$$ So there are two solutions, $n=11^2=121$ and $n=2\times11^2=242$.

Answer 2

Suppose that $\phi(n)=110=2\cdot 5\cdot 11$. We factor $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$. Since $\phi$ is multiplicative, $\phi(n)=\phi(p_1^{a_1})\phi(p_2^{a_2})\cdots \phi(p_k^{a_k})$. We also can evaluate the totient at any prime power, so $$\phi(n)=\frac{n}{p_1p_2\cdots p_k}(p_1-1)(p_2-1)\cdots(p_k-1)$$

Note that each $p_i-1$ is even for any odd prime $p_i$. Since $110$ has only one power of 2, we conclude that $n$ can have at most one odd prime divisor, i.e. $n=2^ap^b$, for some $a,b$ nonnegative integers.

Answer 3

Note that $$ \phi(n) \geq \sqrt {\frac{n}{2}}, $$ so this is a finite search

Is the Euler phi function bounded below?