My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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!
brangelito is offline  
 
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.
brangelito is offline  
August 8th, 2010, 04:41 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
brangelito is offline  
August 8th, 2010, 07:20 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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! :)
brangelito is offline  
August 8th, 2010, 01:38 PM   #7
EPH
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.
EPH is offline  
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.
brangelito is offline  
August 8th, 2010, 04:20 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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. )
CRGreathouse is offline  
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# ).
brangelito is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.