Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$ 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
 A: 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$.
A: 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.
A: Note that $$ \phi(n) \geq \sqrt {\frac{n}{2}},  $$ so this is a finite search
Is the Euler phi function bounded below?
