From: Bob Silverman Subject: Re: Euler's phi function Date: Thu, 02 Dec 1999 20:56:24 GMT Newsgroups: sci.math Keywords: lower bounds for Euler's phi function In article <8267h7$fu2$1@nnrp1.deja.com>, ray steiner wrote: > It is known that if n is a composite > natural number then > phi(n) <= n - sqrt(n)--a good > upper bound for phi(n). > Is there a good lower bound for > phi(n)? Let n = 2 * 3 * 5 * 7 * .....p phi(n) = n(1-1/2)(1-1/3)(1-1/5).... This is asymptotically n * exp(-gamma)/log(p) from Mertens' Thm. Since p ~ log(n) we get the lower bound of n * exp(gamma)/loglog n. gamma is Euler's constant. -- Bob Silverman "You can lead a horse's ass to knowledge, but you can't make him think" Sent via Deja.com http://www.deja.com/ Before you buy.