Solutions manual for NTB - 1.1 Divisibility and primality
Exercise 1.1. Let
with
. Show that
if and only if
. Proof
(q.e.d).
Exercise 1.2. Let
be a composite integer. Show that there exists a prime
dividing
with
. Proof We use strong induction. Let
be the proposition that for all composite integer
, there exists a prime
dividing
with
. Base case:

is true. Inductive step: Now we must show that
imply
for all composite integer
. Since
is a composite, there exists
so that
with
(if
, we just swap them). If
is a prime, then
is true since
divides
and
. If
is a composite, then according to the induction assumption, there exists a prime
that divides
. This prime
also divides
with
. So P(n) is true. Therefore, the claim is true by strong induction for all composite integer n (q.e.d).
Exercise 1.3. Let
be a positive integer. Show that for every real number
, the number of multiples of
in the interval
is
; in particular, for every integer
, the number of multiples of
among
is
. Proof * The first claim: applying Theorem 1.4 with
and
, we have: there exits unique
such that
. It's easy to see that
is the number of multiples of m in the interval
. Page 4 of NTB shows that
. By the first claim of Exercise 1.5, we know that
, which proves the claim. * The second claim: just apply the first claim with
, we have
with
(q.e.d).
Exercise 1.4. Let
. Show that
. Proof Let
with
. In other words, there exists
so that
. We have:
, which proves the first inequality. For the second inequality, observes that
and
for all
and
. We have:
, which proves the inequality (q.e.d).
Exercise 1.5. Let
and
with
. Show that
; in particular
for all positive integers
. Proof We prove a stronger claim (which is copied from [Graham, Knuth, Patashnik]). Consider function

with

and

. It's easy to see that f is a continuous, monotonically increasing function with the property:

= integer then

is a integer. We claim that

. Let's prove it. If

, then there's nothing to prove. Otherwise

, then we have

, since f is increasing. Hence

, since

is nondecreasing. If

, then there must be a number y such that

and

, since f is continuous. This y is an integer, because of

's special property. But there can not an integer strictly betweet

and

. This contradiction implies that we must have

, which proves the claim. Applying this claim to Exercise 1.5, we got what we want to prove (q.e.d).
Exercise 1.6. Let
with
. Show that
.
Exercise 1.7. Show that Theorem 1.5 also holds for the interval
. Does it hold in general for the intervals
or
?