Solutions manual for NTB - 1.2 Ideals and greatest common divisors

Exercise 1.8. Let be a non-empty set of integers that is closed under addition (i.e., for all ). Show that is an ideal if and only if for all . Proof We prove is an ideal implies for all and vice versa. First, we show is an ideal implies for all . Since is an ideal so we have for all . Choose , we get what we want to prove. Now, we show for all implies is an ideal. For all , we have ( times ) which belongs to since is closed under addition. Similarly, for all , we have ( times ) which belongs to since is closed under addtion and . So we have for all and for all . This proves is an ideal.

(q.e.d.)

---

Exercise 1.9. Show that for all integers , we have: (a) ; (b) ; (c) and ; (d) . Proof a, b, c are trivial and can be easily derived from the definition of greatest command divisor. We prove only d here. We first show that . According to Theorem 1.8, there exist such that . Then we have . Then once again, according to thereom 1.8, we have . Now we show that . Since and , we have and . Hence is a common divisor of and . That means .

Thus .

(q.e.d.)

---

Exercise 1.10. Show that for all integers with , we have . Proof We use proof by contradiction. Suppose . Then we have and . Hence and . That means is a common divisor of and . But . This is a contradiction. Therefore, . (q.e.d.)

---

Exercise 1.11. Let be an integer. Show that if are relatively prime integers, each of which divides , then divides . Proof Before proving it, let's pause for a second and think about this problem. Is it just me or this problem is right by intuition? After two months studying number theory, I can tell you that not only this problem but most problems in this field are intuitively right. May this be the reason why number theory is so beautiful. Everybody can intuitively get it, but only somebody can intellectually prove it. So how do we solve this exercise? Well, we have so let for some . We claim that , hence . To prove , observes that and , then applying Theorem 1.9, we got what we want to prove. (q.e.d.)

---

Exercise 1.12. Show that two integers are relatively prime if and only if there is no one prime that divides both of them. Proof (This proof left blank because it is way too trivial) (q.e.d.)

---

Exercise 1.13. Let be integers. Show that if and only if for . Proof We show implies for and vice versa. First we show implies for . We prove this by contradiction. Suppose such that . We have and . Hence is a common divisor of and . That means . This is a contradiction. Therefore, for . Now we show for implies . Applying exercise 2.12, we see that there's no prime divides both and for . That means there's no prime divides both and . Hence they are relatively prime. (q.e.d.)

---

Exercise 1.14. Let be a prime and an integer, with . Show that the binomial cofficient

,

which is an integer, is divisible by . Proof We have: for some . Since , then we have . Hence . That means for some . Therefore, . (q.e.d.)

---

Exercise 1.15. An integer is called square-free if it is not divisible by the square of any integer greater than 1. Show that: (a) is square-free if and only if , where the ’s are distinct primes; (b) every positive integer can be expressed uniquely as , where and are positive integers, and is square-free. Proof (q.e.d.)