Tuesday, July 7, 2009

Solutions manual for NTB - 1.1 Divisibility and primality

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 ?

No comments: