Question

Exercise 8.1 Prove Theorem 8.1 by proving the following: a.) Consider the set of all positive integral linear combinations of a and 6. Prove that this set has a smallest element, m. b.) Prove that (a,b) < m. c.) Prove that ms (a, b).

Answer 1

(a)

Let S be the set of all positive integral linear combinations of a and b.

Therefore, S = {s > 0: s= ax + by for some x,y EZ).

Now, a +61 ES. Since a = a.1 if a is positive and a = a.(-1) if a is negative. Similarly for 16.1

Thus, S is non-empty and all the elements are greater than 0. Hence, S has a smallest element.

Let this smallest element be m.

Hence proved.

(b)

meS. :: 3 xo, Yo E Z such that m = axo + byo. Let d= (a,b). da and d|b daxo + byo) dm 3d<m (a, b) <m Hence proved.

(c)

By the division algorithm, 3q, r e Z such that a = mq + r. 0 <r <m. - -- - - - - - - (1) Now, r < m r & S. Since m is the smallest element of S.

Now, r = a – mq = a - (axo + byoq = a (1 – 709) + b(-409) where (1 – 209),(-409) EZ But r&S= rX0 =r< 0. Also, r > 0. From (1)

Thus r = 0 and r 20 Br=0.

..a= mq Bma. Similarly, m|6.

Hence, ma and mb amd = m(a,b) a m < (a,b) Hence proved.