My Math Forum Euler Phi

 Number Theory Number Theory Math Forum

 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:
 Originally Posted by CRGreathouse Phi is multiplicative, and phi(n) > 1 for n > 1, so phi(pq)/pq > phi(p)/p.
1. phi(n) > 1 for n > 2

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:
 Originally Posted by CRGreathouse The easy way is to just look at primes, since phi(p)/p > phi(q)/q for p > q prime.
Ah, that was simple, thank you! :)

 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)=p-1>phi(n) This is, when a prime appears its totient is greater than the totients of all numbers below. So: phi(p)/p=(p-1)/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:
 Originally Posted by EPH If p>n is a prime then: phi(p)=p-1>phi(n) This is, when a prime appears its totient is greater than the totients of all numbers below. So: phi(p)/p=(p-1)/p > phi(n)/n, if p>n. phi(p)/p tend to 1 as p grows.
Yeah, I know. Thanks for trying to help though. :)

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:
 Originally Posted by CRGreathouse For that direction, use primorials. (And don't use p and q when you mean natural numbers rather than primes; it confuses me. :D )
Wikipedia says that phi(n)*phi(m) = phi(n*m) if GCD(n,m) == 1.
So yeah, phi( (n+1)# ) > phi( n# ).

 Tags euler, phi

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top