Divisor of $m$ and $n$ divides $m - qn$ (in proof of Euclidean algorithm)

For the last line in your post: Suppose $d$ divide both $m$ and $n$, this means that there are integers $a,b$ such that $m=ad$ and $n=bd$ and then $$r= m-qn= ad -qbd=(a-qb)d$$ that is $d$ divides $r$ too.

Hint $\rm\quad q\:,\ \dfrac{m}d,\ \dfrac{n}d\ \in\ \mathbb Z\ \ \Rightarrow\ \ \dfrac{m - q\ n}{d}\ =\ \dfrac{m}d\ -\ q\ \dfrac{n}d\ \in\ \mathbb Z$

Said more structurally, the set $\rm\,D = d\:\! \mathbb Z\, $ of all multiples of $\rm\,d\,$ is closed under addition, and closed under scalings (multiplication by an integer), so it is closed under compositions of such operations, i.e. all integer-linear combinations of elements of $\rm\,D,\,$ so $\rm\ m,n\in \mathbb Z,\ a,b\in D\ \Rightarrow\ ma+nb\in D.\,$ If you study ring theory you will learn that this is a prototype of a fundamental ubiquitous algebraic structure known as an ideal or $\rm\:R$-module (a ring-theoretic analog of a vector space)