5. Squarefree and smooth numbers 11
Indeed, the number of integers not exceeding N that have a prime factor
p M is bounded above by
Mp≤N
N
p
N
pM
1
p
N/2,
so that more than N/2 of the natural numbers not exceeding N are divisible
only by primes p M.
We now show that there are too few integers only by primes
p M for this to be possible. There are at most
√divisible
N squares not exceeding
N and at most C :=
2π(M)
squarefree numbers composed only of primes not
exceeding M. Thus there are at most C

N natural numbers N having
all their prime factors M. But C

N N/2 once N
4C2.
In the last argument we needed an estimate for the number of integers up
to a given point with only small prime factors. This motivates the following
definition: Call a natural number y-smooth if all of its prime factors are
bounded by y. We let Ψ(x, y) denote the number of y-smooth numbers not
exceeding x; i.e.,
(1.8) Ψ(x, y) := #{n x : p | n p y}.
Smooth numbers are important auxiliary tools in many number-theoretic
investigations, and so there has been quite a bit of work on estimating the
size of Ψ(x, y) in various ranges of x and y. (For a survey of both the
applications and the estimates, see [Gra08b].) A trivial estimate yields an
easy proof of Theorem 1.1.
Lemma 1.6. For x 1 and y 2, we have
Ψ(x, y) 1 +
log x
log 2
π(y)
.
Proof. Let k = π(y). By the fundamental theorem of arithmetic, Ψ(x, y)
is the number of k-tuples of nonnegative integers e1,...,ek with
p11
e
p22
e
· · · pkk
e
x.
This inequality requires pi
ei
x, so that
ei log x/ log pi log x/ log 2,
so that there are at most 1 + log x/ log 2 possibilities for each ei.
Since every positive integer not exceeding N is a (possibly empty) prod-
uct of primes not exceeding N,
N = Ψ(N, N) (1 + log N/ log
2)π(N).
Previous Page Next Page