elementary number theory - Proving that $text{gcd}(a,b)=text{gcd}(b,r)$

Let $0\neq a,b\in \mathbb{Z}$. there are integers $p,q$ such that $0\leq r

My attempt:

$$\text{gcd}(a,b)=\varphi$$

So

$$\exists \,m,n \in \mathbb{Z}\,\,\,\,\,\;\;\;\;\;\;\;\;\;\varphi=ma+nb$$

---

$$\text{gcd}(b,r)=\psi$$

So

$$\exists \,m,n \in \mathbb{Z}\,\,\,\,\,\;\;\;\;\;\;\;\;\;\psi=mb+nr$$

We know that $a=bq+r$ so $r=a-bq$

So gcd$(b,\underbrace{a-bq}_{=r})=\psi=mb+n(\underbrace{a-bq}_{=r})=$

I'm stuck here, and I don't know if my attempt is correct or not

Answer

You have to use the fact that the gcd is the smallest linear combination.

Suppose $(a,b)=ma+nb$. Then $(a,b)=m(bq+r)+nb = mr+(qm+n)b$.

Similarly, if $(b,r)=m'b+n'r$ then $(b,r) = m'b+n'(a-bq) = n'a + (m'-n'q)b$.

Therefore you know that $(a,b)$ divides $(b,r)$ and $(b,r)$ divides $(a,b)$