Proving that if $a=bq+r$ then $(a,b)=(b,r)$ 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$.
 A: 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$.
A: 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$.
A: 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!
