The Inverse of the Euler Totient Function How can we calculate the cardinality of the inverse of Totient function of any positive integer n ?
I tried going through this paper, but I couldn't understand the procedure.
Thanks
 A: I assume you are asking about $N(m)$, the number of distinct integers $n$ which satisfy $\phi(n)=m$ where $\phi$ is the Euler Totient function.  
There are many results regarding upper and lower bounds for the size of $N(m)$, as well as the mean and variance.  In particular, Carmichael conjectured that $N(m)$ is never equal to $1$.
Pomerance gave the upper bound $$N(m)\leq  m\exp{-(1+o(1))\log m \frac{\log \log \log m}{\log \log m}}$$ and also showed that there are infinitely many $m$ for which $$N(m)\geq m^{\frac{5}{9}}.$$ 
Bateman showed that $$\sum_{m\leq x} N(m)=\frac{\zeta(2)\zeta(3)}{\zeta(6)}x+O\left(xe^{-c\sqrt{\log x\log \log x}}\right),$$ and we also have that $$\sum_{m\leq x} N(m)-\frac{\zeta(2)\zeta(3)}{\zeta(6)}x=\Omega\left(x^\frac{5}{9}\right)$$
For more details, see the following paper of Pomerance: Popular Values of Euler's Function.
A: See also my recent paper "Computing the (number or sum of) inverses of Euler's totient and other multiplicative functions", which presents a generic dynamic programming algorithm for finding the inverses of a multiplicative function for a given integer value.
Please let me know if something is unclear.
A: f you are interested in a computational approach, there is software that can compute
$\varphi^{-1}(n)$.
PARI/GP Scripts for Miscellaneous Math Problems by Max Alekseyev
check invphi.gp.
The original invphi.gp appears for quite old pari/gp and doesn't run on current pari,
I ported it here.
Here is a sample session:
? \r invphi2.gp 
? n=2*13*17;v=invphi(n);#v
%1 = 2
? v
%2 = [443, 886]
? eulerphi(v[1])==n
%3 = 1

A: Of course you should also take a look at
This OEIS entry, and to the references within.
A: Here is a naive attempt, which can be refined to give an upper bound on the cardinality.
 I will only look at the case that the inverse n is odd, the even case being mildly more
complicated.
So given $p$, I want to find how many odd $n$ satisfy $\phi(n)=p$.  Let $p=r2^w$ with $r$
odd.  To make things interesting assume $w>0$.  Pick $b \geq w$ and assume $n$ has at most
$b$ factors. Place the  $w$ 2's in $b$ buckets. If a prime factor $q$ of $r$ is not going into a bucket,
then we must put in one bucket enough to make $q-1$.  Otherwise,  distribute the prime factors
of $r$ into the buckets. Each bucket will contain those primes which multiply to form $q-1$, where
$q$ is a factor of $n$.  If $r$ has $c$ not necessarily distinct prime factors,
there are then at most $c^{b+1}$
ways to distribute the factors of $r$, and not all of them will work.
A recursive version is to assume the least prime factor of  $n$ is $q$, and then try to find solutions
to $\phi(m)=p/[(q-1)q^s]$ for appropriate values of $s$.  This may be quicker to implement but harder
to analyze.
Gerhard "Ask Me About System Design" Paseman, 2012.10.12
