Given an integer $n$ find smallest integer $x$ such that $\varphi(x) = n$.

$$10^5 < n < 10^8$$

I know that lower bound for searching is $n+1$ and the upper bound is

$$\frac{n}{e^{0.577}\log(\log(n))} + \frac{3}{\log(\log(n))}$$

But my problem is that for such a large values of $n$ my program with precomputed $\varphi(x)$ values has to do a lot of searching and is highly inefficient.

Can you please provide any other method for doing the same .


  • $\begingroup$ My apologies if I am missing something basic here, but what function is it that you are defining to mean $\varphi(x)$? $\endgroup$
    – Amzoti
    Commented Dec 26, 2012 at 18:31
  • $\begingroup$ Euler totient function.. phi(x)... gives the number of integers less than x which are coprime to x $\endgroup$ Commented Dec 26, 2012 at 18:35
  • $\begingroup$ So I don't waste time, you are asking for an efficient algorithm for inverting the Euler Totient function. Correct? $\endgroup$
    – Amzoti
    Commented Dec 26, 2012 at 19:26
  • $\begingroup$ yes.. which can work for large test cases $\endgroup$ Commented Dec 26, 2012 at 19:48
  • 1
    $\begingroup$ I would recommend changing your title to be more descriptive in case others are searching for this too and there have been previous questions regarding approaches. Regards $\endgroup$
    – Amzoti
    Commented Dec 27, 2012 at 2:19

3 Answers 3


Warning, you are going to have to do some work to get your hands around this answer, but I provided enough details for you to work through it and it answers your question.

Goal: Given an integer $n$ find the smallest integer $x$ such that $\varphi(x) = n$.


One can calculate all of the possible integers with a totient of $n$ using "Inverse Totient Trees."

For instance, take the integers with a totient of $24$. Then,

$\varphi(N) = 24$

$\varphi(24) = 8$

$\varphi(8) = 4$

$\varphi(4) = 2$

$\varphi(2) = 1$

There are $5$ "links" (designate this as $L$) in the totient chain so to speak, with $4$ intervals. In general, the greatest integer that can have a totient of $n$ is $2*3^{(L-1)}$, which means that $2*3^{(5 - 1)}$ $= 162$ is the upper bound of an integer with a totient of $24$.

In fact, via a simple proof by exhaustion, one can easily check a table and see that the smallest integer where $\varphi(x) = 24$ is $x = 35$ (see the list below).

$$\varphi(x)= n = 24 \rightarrow x = 35, 39, 45, 52, 56, 70, 72, 78, 84, 90$$

Here are a couple of related number sequences which include references for you to investigate this approach.

A032447 Inverse function of phi( )

A058811 Number of terms on the n-th level of the Inverse-Totient-Tree (ITT)

So, the next obvious question, is there a program that is related or tangentially related that can generate all of those values in the range specified using some approach?

Yes, see Solving $\varphi^{-1}(x) = n$, where $\varphi(x) = n$ is Euler's totient function - testing Carmichael's conjecture. Please see the references there for further details on this program - including the C-source code.

Lets do the example above and the some examples within your range (note that numbers are obviously never odd because $\varphi(x)$ is always even for $n \ge 3$).

$n = 24$: Enter $n = 24, e = 0, f = 0$: and look at the resulting $10$-bolded numbers and compare that list to the above. If you sort that list from low to high, it is all of the $x's$ that produce that desired $n$. Of course, you only want the minimal (last bolded number in the display) one. So $\varphi^{-1}(35) = 24$.

$n = 10^{5}$: Enter $n = 100000, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 100651$.

$n = 10^5 + 1$: Enter $n = 100001, e = 0, f = 0$: Odd numbers are not permissible by statement above.

$n = 10^{5} + 2$: Enter $n = 100002, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 100003$.

$n = 5*10^{5}$: Enter $n = 500000, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 640625$.


$n = 10^{8}$: Enter $n = 100000000, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 100064101$.


This is a very interesting problem and has been asked before, so I am summarizing some of the other discussions and references I found in case others want to consider more approaches.

There are several papers on the topic of finding the inverse of the Euler Totient function:

Euler's Totient Function and Its Inverse, by Hansraj Gupta

The number of solutions of $\phi(x) = m$, by Kevin Ford

On the image of Euler’s totient function, R.Coleman

Complexity of Inverting the Euler Function, by Scott Contini, Ernie Croot, Igor Shparlinski

There have been several questions along these lines, for example, the-inverse-of-the-euler-totient-function, inverting-the-totient-function and finding-the-maximum-number-with-a-certain-eulers-totient-value

There are some other code examples that use different methods for you to consider, see, for example:

Inversion of Euler Totient Function by Max Alekseyev and you can experiment with this since PARI/GP is free. Play around with the function and see if you can modify your approach with this approach.

Discussion and implementation of an efficient algorithm for finding all the solutions to the equation EulerPhi[n] = m, by Maxim Rytin is a nice article off of wolfram that gives an efficient algorithm for computing the inverse of the Euler totient function. Download the invphi.nb file at the bottom and get Mathreader. As an alternative, you can see oeis A006511.

MAGMA - see FactoredEulerPhiInverse(n)


  • $\begingroup$ Thanks a lot for your descriptive answer :) $\endgroup$ Commented Dec 27, 2012 at 8:19
  • $\begingroup$ @Purva Gupta, you are very welcome! We are all here to learn from each other and MSE is a wonderful site! $\endgroup$
    – Amzoti
    Commented Dec 27, 2012 at 9:01
  • $\begingroup$ 2∗3^(L−1) is it applicable for all or only specific numbers? $\endgroup$ Commented Dec 27, 2012 at 9:18
  • $\begingroup$ All, it is an upper bound using this method for the largest n, recalling that n must be even numbers only from the note. $\endgroup$
    – Amzoti
    Commented Dec 27, 2012 at 13:08
  • 1
    $\begingroup$ Several typos in the above answer use "phi-inverse" where it ought to read "phi". These include the link to "Solving phi-inverse(x) = n" and the statement "phi-inverse(35) = 24". $\endgroup$
    – Dan Asimov
    Commented Jun 5, 2021 at 16:13

See also my recent paper "Computing the (number 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.

  • $\begingroup$ I have gone through all the details however I found little difficulties in understanding some steps. May I get your email id please so that I can communicate with you in this regard? My email id is anjan(dot)debnath(at)thc(dot)edu(dot)in $\endgroup$
    – KON3
    Commented Jun 9, 2020 at 4:18

I made an efficent java implementation of the Inverse Euler Totient (invphi) using the algorithm described by Hansraj Gutpa. It also uses the fastest factorization implemented in java since factorization is one of the bottlenecks.

See: https://github.com/thomasegense/bigmathfast


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .