August 8th, 2010, 02:21 AM  #1 
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Euler Phi
Hello. I'm looking for a way of proving that phi(n)/n has no upper boundary. Given p, there should always exist a larger integer q, such that phi(q)/q > phi(p)/p. Thank you in advance! 
August 8th, 2010, 03:01 AM  #2 
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Euler Phi
After some initial research, I can say that it is equivalent to proving that: phi(p*q)/(p*q) > phi(p)/p .. where q is a integer coprime to p. 
August 8th, 2010, 04:41 AM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Euler Phi
Phi is multiplicative, and phi(n) > 1 for n > 1, so phi(pq)/pq > phi(p)/p.

August 8th, 2010, 04:52 AM  #4  
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Euler Phi Quote:
2. phi(3*5)/(3*5) < phi(3)/3 Edit: This also makes my second statement invalid, hum. Edit2: My mistake is writing phi(n)/n instead of n/phi(n), which is what I actually calculated on.  
August 8th, 2010, 07:20 AM  #5 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Euler Phi
Sorry, I was thinking sigma when I wrote phi... The easy way is to just look at primes, since phi(p)/p > phi(q)/q for p > q prime. 
August 8th, 2010, 07:27 AM  #6  
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Euler Phi Quote:
 
August 8th, 2010, 01:38 PM  #7 
Member Joined: Dec 2009 From: Spain Posts: 51 Thanks: 0  Re: Euler Phi
If p>n is a prime then: phi(p)=p1>phi(n) This is, when a prime appears its totient is greater than the totients of all numbers below. So: phi(p)/p=(p1)/p > phi(n)/n, if p>n. phi(p)/p tend to 1 as p grows. 
August 8th, 2010, 04:08 PM  #8  
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Euler Phi Quote:
Can we prove the inverse as well? Given p, there should always exist a larger integer q, such that q/phi(q) > p/phi(p). Like I said in my second post, (p*q)/phi(p*q) > p/phi(p) if q is coprime to p.  
August 8th, 2010, 04:20 PM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Euler Phi
For that direction, use primorials. (And don't use p and q when you mean natural numbers rather than primes; it confuses me. )

August 8th, 2010, 05:13 PM  #10  
Senior Member Joined: Apr 2010 Posts: 215 Thanks: 0  Re: Euler Phi Quote:
So yeah, phi( (n+1)# ) > phi( n# ).  

Tags 
euler, phi 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Euler's Paradoxes  unm  Number Theory  0  December 3rd, 2012 06:05 PM 
Euler method/ Euler formula  FalkirkMathFan  Calculus  1  November 5th, 2011 12:57 AM 
Euler method/ Euler formula  FalkirkMathFan  Real Analysis  0  November 4th, 2011 04:08 AM 
Euler method/ Euler formula  FalkirkMathFan  Calculus  0  November 3rd, 2011 04:52 PM 
Euler's table  fran1942  Number Theory  1  December 31st, 1969 04:00 PM 