User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      