Inverse image of phi (totient)

  • Thread starter math_grl
  • Start date
  • #1
math_grl
49
0
So upon introduction to Euler's phi function, we can see that [tex]\phi (1) = 1[/tex] and [tex]\phi (2) = 1[/tex], 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 [tex]\phi^{-1}[/tex] that these are in fact the only numbers it could be?
 

Answers and Replies

  • #2
al-mahed
262
0
So upon introduction to Euler's phi function, we can see that [tex]\phi (1) = 1[/tex] and [tex]\phi (2) = 1[/tex], 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 [tex]\phi^{-1}[/tex] 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
 
  • #3
math_grl
49
0
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 [tex]f: \mathbb{N} \rightarrow \phi(\mathbb{N})[/tex] where [tex]f(n) = \phi(n)[/tex] 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...
 
Last edited by a moderator:
  • #4
al-mahed
262
0
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 [tex]f: \mathbb{N} \rightarrow \phi(\mathbb{N})[/tex] where [tex]f(n) = \phi(n)[/tex] 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

[tex]\varphi(n_1)=m_1[/tex]
[tex]\varphi(n_2)=m_2[/tex]
[tex]\varphi(n_3)=m_3[/tex]
[tex]\varphi(n_4)=m_4[/tex]
...

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
 
Last edited by a moderator:
  • #5
Petek
Gold Member
398
21
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:

[tex]\frac{1}{2} \sqrt{x}\ \leq \ \phi(x) \ \leq \ x [/tex]

for any positive integer x. It then follows that the equation [itex]\phi(x) = n[/itex] 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

[tex]n \ \leq x \ \leq \ 4n^2[/tex]

Hope that answers your question.
 
  • #6
Raphie
151
0
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
 
Last edited:

Suggested for: Inverse image of phi (totient)

  • Last Post
Replies
5
Views
312
  • Last Post
Replies
24
Views
855
  • Last Post
Replies
2
Views
605
Replies
34
Views
1K
  • Last Post
Replies
5
Views
587
Replies
2
Views
489
  • Last Post
Replies
2
Views
720
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
990
Top