Featured Post

Có một Biển Đông trên không gian mạng

Có một Biển Đông trên không gian mạng Thái Dương Mùa hè 2014, giữa lúc người Việt trong nước và hải ngoại đang sôi sục vì Trung Quốc đư...

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: