# Computing $n$ such that $\phi(n) = m$

Is there a general procedure for computing an inverse of the euler totient function? I did find an old SE post that seemed to have some pointers -How to solve the equation $\phi(n) = k$?

However, I am interested in the case $\phi(n) = 72$. The procedure outline in the link above leads me to write out $n = 2^\alpha3^\beta\prod_{p_i|n}p_i$. However, since 72 + 1 = 73 is a prime, this clearly fails to find all n.

Would someone be willing to point in the right direction for this case?

-
There is one example done in detail at that link, and links to four other discussions of the problem --- is there really nothing there you can't use to solve your problem with $72$? – Gerry Myerson Jan 22 '13 at 4:40
@GerryMyerson two of the links have to do with the computational complexity of the problem, one of them discusses the existence of solutions, and the remaining link (along with the question) start out by expressing n as a product of primes with certain powers based on the factorization of $\phi(n)$. I attempted to start off with that, but that has immediately excluded a certain n (n = 73). Because the strategy presented doesn't seem to be working, I am asking for help. – Rebecca Kuang Jan 22 '13 at 4:45
I think you're misunderstanding the last bit, but, anyway, see if my answer helps. – Gerry Myerson Jan 22 '13 at 4:50
By working moderately systematically, we can get a complete list. I have written out an approach, which I can post after suitable delay to give you a chance to work things out. – André Nicolas Jan 22 '13 at 6:23

If $\phi(n)=72$, and $p$ is a prime dividing $n$, then $p-1$ divides $72$ (why?), so the first thing to do is write down all the divisors of $72$ and see which ones are $1$ less than a prime.

1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.

2, 3, 4, 5, 7, 9, 10, 13, 19, 25, 37, 73.

The primes in this second list are 2, 3, 5, 7, 13, 19, 37, and 73, so these are the only possible prime divisors of $n$.

If $p^r$ divides $n$ for some $r\ge2$, then $p^{r-1}$ divides $72$ (why?), so $p^r$ is one of the numbers 4, 8, 16, 9, 27 (why?).

So now you have the complete list of possible prime and prime-power divisors of $n$. You test them systematically to see which combinations work.

For example, if $73$ is a divisor of $n$, that doesn't leave much room for anything else --- $n$ must be $73$ or $2\times73$.

If $37$ is a divisor of $n$, then you're just looking for a factor of $2$, so you can use $3\times37$, or $4\times37$, or $6\times37$.

And so on.

-
Might also help observing that $n$ cannot have more than 3 odd prime divisors. – N. S. Jan 22 '13 at 5:16
@N.S., yes, there are a number of observations one might make to diminish the number of cases to look at. I hope OP will discover some of them. – Gerry Myerson Jan 22 '13 at 5:18

There are a total of 17 such $n$ and they are:

73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270.

Regards

-
They are the n's that OP asked for. I changed the response based on your comment to make it clearer. Thanks and regards – Amzoti Jan 22 '13 at 7:04