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 
?
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 ?
Comments