Proving that $\text{gcd}(a,b)=\text{gcd}(b,r)$

Question

Let $0\neq a,b\in \mathbb{Z}$. there are integers $p,q$ such that $0\leq r<b$ and $a=bq+r$. Prove that $(a,b)=(b,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 1

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)$

Answer 2

Perhaps it's easier to prove more:

Denote $\;\mathcal D(x,y)$ the set of divisors common to $x$ and $y$.

Claim: $\mathcal D(a,b)=\mathcal D(b,r)$.

Indeed, if $x$ divides $a$ and $b$, it divides any linear combination of $a$ and $b$ with integer coefficients, in particular it divides $b$ and $a-qb$, whence $\subseteq$.

Concersely, if $x$ divides $b$ and $r$, it also divides $qb+r=a$, whence $\;\supseteq$.