Solution dff87469-4f69-4edb-82f5-becf75490825

Points: 2 pts

Lemma 1: $\operatorname{div}(b,a)=\operatorname{div}(a,r)$

Suppose $d_1\in\operatorname{div}(b,a)$. We then know
\[
  d_1\mid b,\qquad d_1\mid a.
\]
Suppose $d_2\in\operatorname{div}(a,r)$. We then know
\[
  d_2\mid a,\qquad d_2\mid r.
\]
But we can write
\[
\begin{aligned}
  d_2&\mid ka+r=b,\\
  d_1&\mid b-ka=r.
\end{aligned}
\]
We see that any divisor of $b$ and $a$ also divides $r$, and any divisor of $r$ and $a$ also divides $b$. Hence, the divisor sets are the same.

Lemma 2: $\gcd(b,a)=\gcd(a,r)$

Since $\operatorname{div}(b,a)$ and $\operatorname{div}(a,r)$ are the same set, they must have the same maximum.

Final answer:
\gcd(b,a)=\gcd(a,r)