From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: number puzzle
Date: 2 Oct 1998 15:28:00 GMT

In article <360E2451.710C@hotmail.com>, thamyris  <joeblow8@hotmail.com> wrote:
>Find all n with the property that for all primes p<=sqrt(n), p|n.
>
>I get {1, 2, 3, 4, 6, 8, 12, 18, 24, 30}
>
>is this correct?

You want  Product{p ; p <= sqrt(n) }  to divide  n. This certainly requires
that this product be at most  n. But the product of all primes up to  x
behaves roughly like  exp(x)  in a very precise sense; certainly
a quantity roughly equal to  exp(sqrt(n))  will exceed  n  for large  n.
So we know before we begin that there are only finitely many solutions to
the problem at hand.

But we don't need such a precise estimate of the magnitude of the product
of many primes. Simply note that if for some  N  we have
	Product{p ; p <= sqrt(N) } >  k N
then since there is always a prime between  x  and  2x  we know 
	Product{p ; p <= sqrt(4N) } >  (k N)*sqrt(N) = (k*sqrt(N)/4)*(4N)
This is also more than  k*(4N)  as long as  N>16. Taking in particular
N = 50 we observe that  2*3*5*7 = 4.2 N, and so 
	Product{p ; p <= sqrt(N) } >  4.1 N
holds for N=50, 200, 800, ...

But then also if  N < n < 4N, we certainly have
	Product{p ; p <= sqrt(n) } >  Product{p ; p <= sqrt(N) } >  4.1 N > n
So we conclude the product of the primes less than sqrt(n) is always more
than  n  for  n > 50. You can examine the values of  n  less than 50
yourself.

dave