How Can We Determine the Inverse Image of Euler's Totient Function?

[math_grl]

So upon introduction to Euler's phi function, we can see that $$\phi (1) = 1$$ and $$\phi (2) = 1$$, where it turns out that these are in fact the only numbers in N that map to 1. Now what I'm wondering is if there is some general way to find the inverse image of numbers in the image of phi?

Also, how would one go about showing that once we find $$\phi^{-1}$$ that these are in fact the only numbers it could be?

 

[al-mahed]

So upon introduction to Euler's phi function, we can see that $$\phi (1) = 1$$ and $$\phi (2) = 1$$, where it turns out that these are in fact the only numbers in N that map to 1. Now what I'm wondering is if there is some general way to find the inverse image of numbers in the image of phi?

Also, how would one go about showing that once we find $$\phi^{-1}$$ that these are in fact the only numbers it could be?

what you mean by "inverse"? do you mean multiplicative inverse ab=1 such that b = a^-1?

I think you want to know if a given number is a phi of one or more numbers, and I think there is no general way to do it yet, only by hand

for instance, given 14, is it a phi of at least one number? no, and I think there is no known way to characterize such numbers yet

 

[math_grl]

what you mean by "inverse"? do you mean multiplicative inverse ab=1 such that b = a^-1?

I don't think there should be any confusion in my terminology but in case a refresher is needed check out http://en.wikipedia.org/wiki/Image_(mathematics)#Inverse_image"

It might also help make it clear that $$f: \mathbb{N} \rightarrow \phi(\mathbb{N})$$ where $$f(n) = \phi(n)$$ cannot have an inverse as it's onto but not injective.

Other than that, yes, what I was asking if there was a way to find all those numbers that map to 14 (for example) under phi...

 

[al-mahed]

I don't think there should be any confusion in my terminology but in case a refresher is needed check out http://en.wikipedia.org/wiki/Image_(mathematics)#Inverse_image"

It might also help make it clear that $$f: \mathbb{N} \rightarrow \phi(\mathbb{N})$$ where $$f(n) = \phi(n)$$ cannot have an inverse as it's onto but not injective.

Other than that, yes, what I was asking if there was a way to find all those numbers that map to 14 (for example) under phi...

hi math-grl

so what you want is to find the n's such that

$$\varphi(n_1)=m_1$$
$$\varphi(n_2)=m_2$$
$$\varphi(n_3)=m_3$$
$$\varphi(n_4)=m_4$$
...

knowing only the m's, correct?

there is a conjecture related to it, although what you want is far more difficult than the conjecture

http://en.wikipedia.org/wiki/Carmichael's_totient_function_conjecture

 

[Petek]

Hi math_grl,

I think that your question does have an answer. The following inequalities can be proved directly from the definition of the totient function, or by using the product formula:

$$\frac{1}{2} \sqrt{x}\ \leq \ \phi(x) \ \leq \ x$$

for any positive integer x. It then follows that the equation $\phi(x) = n$ has only finitely many solutions for a given positive integer n. In fact, given n, the inequalities imply that all solutions to the equation satisfy

$$n \ \leq x \ \leq \ 4n^2$$

Hope that answers your question.

 

[Raphie]

Hi math_grl,

Beyond Petek's reply, one can also calculate the maximal possible integer with a totient of n via recourse to the mathematics associated with "Inverse Totient Trees."

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

phi (N) = 24
phi (24) = 8
phi (8) = 4
phi (4) = 2
phi (2) = 1

There are 5 "links" (designate: L_x) 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 not very exhausting proof by exhaustion, one can easily check a table and see that the greatest integer where phi(n) = 24 is 90.

phi (n) = 24 --> 35, 39, 45, 52, 56, 70, 72, 78, 84, 90

And a couple related number sequences.

A032447 Inverse function of phi( ).
http://oeis.org/A032447
A058811 Number of terms on the n-th level of the Inverse-Totient-Tree (ITT).
http://oeis.org/A058811

As for why the 2*3^(L-1) formula works, I am as curious as anyone and would be more than happy if anyone could provide some insight on that.

- RF