Let (a,b) be integers with greatest common divisor d. Let (r,s,t,u) be integers,

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.