Proving that if $a=bq+r$ then $(a,b)=(b,r)$

Question

Theorem. If $a=bq+r$ then $(a,b)=(b,r)$.

This is what I have tried. Is this correct? is there a better way to prove it?

Proof. Let $d=(a,b)$. Since $d$ is a common divisor of $a$ and $b$, we have $d|a$ and $d|b$ or equivalently $d|bq+r$ and $d|b$.

So there must exits integers $k_1$ and $k_2$ such that

$$ \begin{align} bq+r&=dk_1\tag{1}\\ b&=dk_2\tag{2} \end{align}$$ If we add equation (1) to $-q$ times equation (2), we get

$$ r=d(k_1-qk_2) $$ So $d|r$. Since $d|b$ and $d|r$ then $d$ is a common divisor of $b$ and $r$. What remains to be shown is that $d$ is the greatest common divisor of $b$ and $r$.

Suppose that $m$ is a common divisor of $b$ and $r$. That is, $m|b$ and $m|r$ so there must exist integers $k_3$ and $k_4$ such that

$$ \begin{align} b&=mk_3\tag{3}\\ r&=mk_4\tag{4} \end{align} $$ Since $a=bq+r$, then using equation (4) we have

$$ a=bq+mk_4 $$ and if we use equation (3), then

$$ a=mk_3q+mk_4=m(k_3q+k_4) $$

So $m|a$. Since $m|a$ and $m|b$, then it is a common divisor of $a$ and $b$ but $d=(a,b)$ so by the definition of gcd, we must have $m|d$.

Answer 1

Your proof is not correct. You wrote “What remains to be shown is that $d$ is the greatest common divisor of $b$ and $r$”, but after that you actually don't prove that. You prove instead a trivial assertion: if $m\mid a$ and $m\mid b$, then $m\mid d$.

Answer 2

I think it can be done a bit simpler if you forget "greatest" for a moment, and concentrate on showing that any common divisor of $a, b$ is a common divisor of $b, r$, and vice versa. Once we've proven this, the fact that the greatest common divisor is the same for both pairs is trivial.

If $k$ is a common divisor of $a, b$, then because $r = a-qb$, we must have that $k$ is a divisor of $r$ as well, so it's a common divisor of $b, r$. Similarily, because $a = bq + r$, if $k$ is a common divisor of $b, r$, then it must also be a divisor of $a$ and thus a common divisor of $a, b$.

Answer 3

Let $d=(a,b)$, and $k=(b,r)$. If you can show that $d\mid k$ and $k\mid d$, then you have shown that $d=k$.

The first part of the proof looks OK, here you're showing that $k\mid d$. For the second part you know that $k\mid b$ and also $k\mid r$, therefore $k\mid bq+r$, so $k\mid a$. Since this shows that $k\mid a$ and $k\mid b$ we must have $d\mid k$. Therefore $(a,b)=(b,r)$ and you're done!