- #1

- 49

- 0

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?

- Thread starter math_grl
- Start date

- #1

- 49

- 0

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?

- #2

- 261

- 0

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

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?

I think you wanna 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

- 49

- 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"what you mean by "inverse"? do you mean multiplicative inverse ab=1 such that b = a^-1?

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

- 261

- 0

hi math-grlI 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...

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

- 363

- 8

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

- 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

Beyond Petek's reply, one can also calculate the maximal possible integer with a totient of

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:

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

And a couple related number sequences.

http://oeis.org/A032447

http://oeis.org/A058811

As for

- RF

Last edited:

- Replies
- 13

- Views
- 15K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 3K

- Last Post

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 6K

- Last Post

- Replies
- 7

- Views
- 4K

- Last Post

- Replies
- 1

- Views
- 3K

- Last Post

- Replies
- 6

- Views
- 3K

- Last Post

- Replies
- 15

- Views
- 7K