Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.


share|improve this question
Your link seems to be broken. –  Eric Naslund Oct 13 '12 at 4:06
The correct link: new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/… –  Harun Šiljak Oct 13 '12 at 7:54

5 Answers 5

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.

share|improve this answer
I liked your preprint. I would like it more if you gave a gentler introduction to your main equation (the one with the big O symbols) and defined or set up more components before displaying the equation. One way that might work is to claim and write down an equation for Min, then say Min is a context and that the Min example is a special case of, and then present the general form. My mind appreciates a graspable example just before a syntactically similar generalization. –  The Masked Avenger Jan 24 at 17:34
@The Masked Avenger: Thank you for insightful comments. This preprint was composed in rush (for a conference submission) and I plan to improve it significantly in further revisions. –  Max Alekseyev Jan 24 at 17:45
This impresses me as a (potentially very instructive) example of applied category theory. Even if it turns out to be an instance of something that (say) Michael Barr wrote up some time ago, I could see this as motivation to learn more category theory. –  The Masked Avenger Jan 24 at 18:17
I've just posted an updated version to arxiv. Please let me know if it addresses your concerns. –  Max Alekseyev Apr 22 at 0:30

Of course you should also take a look at This OEIS entry, and to the references within.

share|improve this answer

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
share|improve this answer
I've tested invphi.gp on PARI/GP 2.6.2 and it works fine. Could you please tell me what exactly the problem you are experiencing with my code? Thanks! –  Max Alekseyev Jan 21 at 18:27
@MaxAlekseyev I suppose I backported it to older pari/gp for backwards compatibility (pari/gp versions are not fully compatible and the code didn't work for me at the time). Your code indeed works on new pari/gp. –  joro Jan 21 at 18:48

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

share|improve this answer

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.

share|improve this answer
thanks Eric, but for calculations what's o(1) ? –  pranay Oct 13 '12 at 8:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.