- #1

math_grl

- 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?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter math_grl
- Start date

- #1

math_grl

- 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

al-mahed

- 262

- 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?

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

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

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:

Share:

- 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