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.)