Let ab be integers with greatest common divisor d Let rstu b

Let (a,b) be integers with greatest common divisor d. Let (r,s,t,u) be integers, and define integers (a\',b\') by a\'=ar+bs, b\'=at+bu.

(a) Show that d divides the greatest common divisor, d\', of (a\',b\').

(b) Now assume further that there exist integers (r\',s\',t\',u\') such that a equals a\'r\'+b\'s\' and b equals a\'t\'+b\'u\'. In this case, show that also d equals d\'. Conclude that d equals d\'.

(c) As a special case, prove that the greatest common divisor of (a,b) equals the greatest common divisor of (a\',b\')=(a+bs,b) for every integer s.

Solution

Soln) (a,b) has GCD(greatest common divisor) d

GCD(a,b)=d

So i can write a= kd, b= k\'d where (k and k\' are also divisor of a and b respectively)

A) (a\',b\') has GCD d\'.

GCD(a\',b\')=d\'

GCD(ar+bs, at + bu)= d\' (replace a\' and b\' by its value)

GCD(kdr+k\'ds,kdt+k\'du)=d\' (replace a and b in terms of d)

GCD(d(kr+k\'s), d(kt+k\'u))=d\'

GCD as term defines greatest common factor and d is common factor in both terms. so took it common.

Also property of GCD : GCD(ak,bk)=kGCD(a,b)

SO, d(GCD((kr+k\'s), (kt+k\'u)))=d\'

  GCD((kr+k\'s), (kt+k\'u))=d\'/d

GCD((kr+k\'s), (kt+k\'u)) cannt be fractional . So d\' is multiple of d.

B) follow same appoach as in part A)

(a\',b\') has GCD(greatest common divisor) d\'

GCD(a\',b\')=d\'

So i can write a\'= pd\', b\'= p\'d\' where (p and p\' are also divisor of a\' and b\' respectively)

(a,b) has GCD d.

GCD(a,b)=d

GCD(a\'r\'+b\'s\', a\'t\' + b\'u\')= d (replace a and b by its value)

GCD(pd\'r\'+p\'d\'s\',pd\'t\'+p\'d\'u\')=d (replace a\' and b\' in terms of d\')

GCD(d\'(pr\'+p\'s\'), d\'(pt\'+p\'u\'))=d

GCD as term defines greatest common factor and d\' is common factor in both terms. so took it common.

Also property of GCD : GCD(ak,bk)=kGCD(a,b)

SO, d\'(GCD((pr\'+p\'s\'), (pt\'+p\'u\')))=d

GCD((pr\'+p\'s\'), (pt\'+p\'u\'))=d/d\'

GCD((kr+k\'s), (kt+k\'u)) cannt be fractional . So d\' is multiple of d.

in part A) d\'/d is interger, in PART B) d/d\' is integer

this is possible only when d=d\'

hence proved.

C) To prove : GCD(a,b)= GCD(a+bs,b)

Soln )Assume GCD(a,b)=d

So i can write a= kd, b= k\'d where (k and k\' are also divisor of a and b respectively)

GCD(a+bs,b) = GCD(kd+k\'ds,k\'d)

GCD(a+bs,b) = GCD(d(k+k\'s),dk\')

GCD as term defines greatest common factor and d is common factor in both terms. so took it common.

Also property of GCD : GCD(ak,bk)=kGCD(a,b)

GCD(a+bs,b) = dGCD(k+k\'s,k\');

here one point to note that GCD(k,k\')=1 because i already extracted out common part that multiplied in d factor.

suppose k+k\'s and k\' has GCD=x

So k\'= xq (q is divisor of k\')

k+k\'s=xq\' (q\' is divisor of k+k\'s)

k=xq\' -k\'s =xq\' - xqs

k=x(q\'-qs)

q-q\'s is integer

So k also multiple of x

So k\' and k both has a common factor x which is possible in one case if x=1

So for x=1

GCD(k+k\'s,k\')=1

GCD(a+bs,b) = dGCD(k+k\'s,k\')=d= GCD(a,b)

GCD(a+bs,b) = GCD(a,b)

hence proved.