1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving that the totient function increases infinitely

  1. Oct 24, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that [itex]\varphi[/itex](n)→∞ as n→∞. n[itex]\in[/itex]Z


    2. Relevant equations
    [itex]\varphi[/itex](n) = the number of integers less than n that are coprime to n.


    3. The attempt at a solution
    My professor said that we need to show that [itex]\varphi[/itex](n) is always greater than some increasing estimate of itself. I'm really not sure how to even go about applying this. Any help you could offer would be really appreciated.

    What I was thinking of doing would be to say let k be the integer with the maximum value of the totient function. k=p1[itex]\alpha[/itex]1...pn[itex]\alpha[/itex]n where pi is a prime number. So [itex]\varphi[/itex](k) = [itex]\varphi[/itex](p1[itex]\alpha[/itex]1...pn[itex]\alpha[/itex]n)=[itex]\varphi[/itex](p1[itex]\alpha[/itex]1)...[itex]\varphi[/itex](pn[itex]\alpha[/itex]n). Multiply k by any prime greater than pn, called pl. Call this number j. Then [itex]\varphi[/itex](j)=[itex]\varphi[/itex](p1[itex]\alpha[/itex]1)...[itex]\varphi[/itex](pn[itex]\alpha[/itex]n)[itex]\varphi[/itex](pl[itex]\alpha[/itex]l). This new multiple is greater than zero (I would write out the basis case in order to guarantee this), so the second equation is greater than the first, so there cannot be an integer with the maximum value of the totient. In other words, as n increases, the totient function increases.
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Proving that the totient function increases infinitely
Loading...