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).