Doubt in proof of Euclidean Algorithm

Question

I got this text from https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf

Is it necessary for the proof to suppose:

"Now suppose $d$ is a common divisor of $b$ and $r$..."

By showing that if $d|a$ and $d|b$ then $d|(a-bq)$ aren't we already showing that the set of common dividers for $a$ and $b$ are the same $r$ and $b$?

Answer 1

Yes. Let $\,{\rm CD}(x,y)\,$ be the set of Common Divisors of $x,y$. The proof works as follows.

Note $\ \ {\rm CD}(a,b) \,\subseteq\, {\rm CD}(b,r)\ $ by paragraph $2$ in the proof,

and $\ \ \ \ {\rm CD}(a,b)\, \supseteq\, {\rm CD}(b,r)\ $ by paragraph $3$ in the proof.

Thus $\,\ {\rm CD}(a,b)\, =\, {\rm CD}(b,r)\ $ so they have the same greatest element (= common divisor)

i.e. $\ \ {\rm GCD}(a,b)\! =\! {\rm GCD}(b,r)$

Note that the proof requires both containment directions (paragraph $2$ and $3$) to deduce the equality of the common divisor sets (hence equality of their greatest elements).

Answer 2

No. By showing that if $d\mid a$ and $d\mid b$ then $d\mid r$, we are showing that$$\{\text{common dividers of $a$ and $b$}\}\subset\{\text{common dividers of $b$ and $r$}\}.$$Now, we must prove that the reverse inclusion also holds.

Answer 3

Indeed, the proof shows that any common divisor of $a,b$ is a common divisor of $b,r$ and vice versa.

Thus $a,b$ and $b,r$ have the same greatest common divisor, where greatest is taken according to the divisibility relation.