Wednesday, July 8, 2009

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

10 comments:

Anonymous said...

Nhìn mấy bài toán này nhớ hồi cấp 2 thế. Hồi đó mình rất thích cuốn "Bài giảng số học" của Đặng Hùng Thắng, khá hay, đủ cho học sinh (cấp <= 3) yêu số học/lý thuyết số.

ps: chẳng nhẽ blogspot cho phép viết công thức bằng latex?

thaidn said...

@Anonymous: ừ toàn toán cấp 2 thôi. nhưng mà cách tiếp cận rất khác.

về latex thì sao bạn không thử view image xem mấy cái công thức latex được làm bằng cách nào :-p

Anonymous said...

Thì ra mấy công thức dùng equation editor của codecogs.com. Nhưng đằng nào cũng mất công viết công thức bằng latex, sao bạn không viết luôn cái solution manual này bằng latex, xuất ra pdf nhìn đẹp hơn và đúng với tinh thần manual hơn là để trên blogspot, vốn ko phải để trình bày công thức thế này.

thaidn said...

@Anonymous: ờ mình cũng muốn làm toàn bộ bằng latex rồi xuất ra PDF lắm nhưng mà có 2 lý do khiến mình chưa làm:

1. latex-fu của mình chưa có cao :-D

2. quan trọng hơn, mình muốn gửi lên đây để mọi người đánh giá trước, khi nào okie hết rồi thì mới xuất bản một lần luôn.

Anonymous said...

ủa bài tập lấy từ sách nào vậy bạn?

Anonymous said...

à Latex thì mình biết chứ latex-fu là gì thì mình không biết. bạn giải thích hộ được không?
Thân.

thaidn said...

@Anon1: Bài tập từ cuốn này: http://vnhacker.blogspot.com/2009/07/solutions-manual-for-computational.html

@Anon2: hahah latex-fu nghĩa là kung-fu latex mình còn kém quá, nên chưa có dám thi triển võ công đó mà :-P

Anonymous said...

Oh thanks for your link and your explanation about fatex-fu. Anyway, Anonymous 1 and Anonymous 2 are the same and is this Anonymous.
p/s: I'm trying to use my newbie English-fu to leave a comment on your blog :))

Anonymous said...

Oh thanks for your link and your explanation about latex-fu. Anyway, Anonymous 1 and Anonymous 2 are the same and is this Anonymous.
p/s: I'm trying to use my newbie English-fu to leave a comment on your blog :))

Az said...

Chào anh Thái,

Thật tốt khi anh viết solution của cuốn này trên mạng dù mới có 1.1 --> 1.3. Em cũng đang học cuốn này.

À em có ý kiến nhỏ về bài 1.8. Nhìn chung thì em nghĩ là đúng rồi.
Nhưng trường hợp z = 0 thì là phải xét riêng để a + (-a) = 0 chứ không thể gộp chung với z > 0 được. Em nghĩ vậy.