Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Phi(x) math

  1. Nov 18, 2004 #1
    for n- fixed integer prove that
    phi(x)=n has a finite number of solutions
    I looked at 2 cases when x is even and when x is odd
    1) if x is even then phi(2x)>phi(x) and I showed why it has a finite number of solutions
    2) i'm not sure how to show for the case when x is odd.. any ideas?

    thanks :)
  2. jcsd
  3. Nov 18, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    You don't need to split into even/odd. Have you seen the inequality [tex]\phi(x)\geq \sqrt{x}[/tex]? (valid if x is not 2 or 6). This isn't too difficult to show and gives a bound on the number of x's for a given n. Though if you have the even case already, you could prove the above inequality is always true for odd x.

    You could also use the fact that phi is multiplicative. Show that there are a finite number of primes p that will satisfy [tex]\phi(p)\leq n[/tex]. For each of these primes there is a finite number of exponents k that will satisfy [tex]\phi(p^k)\leq n[/tex]. Conclude there are finitely many x with [tex]\phi(x)\leq n[/tex].
  4. Nov 18, 2004 #3
    i think i got it.. i proved it using the fact that it's multiplicative thanks :rofl:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook