Exercise 1.1. Let with . Show that if and only if .
Exercise 1.2. Let be a composite integer. Show that there exists a prime dividing with .
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 .
* 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 .
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 .
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 ?