Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

2 Answers

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
    
+1 needed & deserved here! –  amWhy May 7 '13 at 0:33
add comment

Your Answer

 
discard

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.