## How can I show that gcd(a,b) =gcd(b,r) ? Euclidean algorithm? given a=bq+r?

**Answer**

Let gcd(a,b) = t. … (1)

So in a = bq + r, let a = ct and b=dt, with gcd(c,d) = 1. so

ct = dtq + r.

Thus t divides r. Let r = te. We get,

c = dq + e. …(2)

Now let gcd ( d,e) = h. ( h divides d & e) in (2) ,would imply that ( h divides c )! But since ( h divides c ) & ( h divides d ) means that ( h divides c & d ). But gcd ( c,d) = 1. Hence h divides 1, i.e. h = 1. If h is not equal to ‘1’, we have the contradiction a positive integer dividing ‘1’ and not equal to one. No such integer exists.

In other words, gcd ( d,e ) = 1. Thus,

gcd ( b , r ) = gcd ( dt, te ) = t * gcd ( d,e) = t*1 = t

That is gcd ( b,r ) = t …(3)

“Compare” (1) and (3) to see plainly that

gcd ( a,b) = gcd ( b,r) because both equals the value ‘t’ !

QED.

STAY CONNECTED