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.