Unable to understand why gcd(bt+r,b)=gcd(b,r)

Question

I am trying to understand greatest common divisor so If a=bt+r for integers t & r then why gcd(a,b)=gcd(b,r).I am unable to understand it.

Answer 1

The $\gcd$ of two numbers is defined to be the maximum in the set of all common divisors. If two pairs of numbers have the same sets of common factors, then the two pairs have the same $\gcd$.

So to show $\gcd(a,b)=\gcd(a-b,b)$ for example, you would need to show

$$d\mid a~\mathrm{and}~d\mid b ~~\iff~~ d\mid (a-b)~\mathrm{and}~d\mid b. $$

(That is: you need to prove the first implies the second and vice-versa. The first is saying $d$ is a common factor of $a$ and $b$, while the second is saying $d$ is a common factor of $a-b$ and $b$.)

You can either induct from this or just use the same kind of reasoning in order to prove the desired conclusion $\gcd(bq+r,b)=\gcd(r,b)$.