Greatest common divisor: Euclidian Algorithm, missing proof step

Question

I'm working through the Euclidian Algorithm to find the greatest common divisor of two integers $n,m$. However I'm stuck at a very trivial step before the algorithm is even presented:

$n,m\in \mathbb{N}, m\leq n\Longrightarrow n = \lfloor\frac{n}{m}\rfloor m + n \text{ mod } m$

we define $q:= \lfloor\frac{n}{m}\rfloor$ and $r:=n\text{ mod } m \Longrightarrow n = qm + r$ with $1\leq q \leq n$, $0\leq r<m$

I define the divisor set $D(n):= \left\{ d\in \mathbb{N}\text{ }| \text{ } \exists k\in\mathbb{N}: \frac{n}{d} = k \right\}$

Now I can easily prove that:

(1) $d\in D(m) \cap D(r) \Longrightarrow d\in D(n)$

(2) $d \in D(n) \cap D(m) \Longrightarrow d\in D(r)$

Here is the missing step: Why do (1) and (2) imply the following identity of the greatest common denominator $\mathrm{gcd}(m,n)$?

$\mathrm{gcd}(n,m) = \mathrm{gcd}(m,r)$

There's some thought or idea that I'm missing here that I cannot quite grasp.

Thank you!

Answer 1

Rewrite these two implications by keeping the fact that $d \in D(m)$ around:

1. $d\in D(m) \cap D(r) \implies d\in D(n) \cap D(m)$
2. $d \in D(n) \cap D(m) \implies d\in D(m) \cap D(r)$.

We conclude that there's a two way implication $d\in D(m) \cap D(r) \iff d\in D(n) \cap D(m)$. As a result, $D(m) \cap D(r) = D(n) \cap D(m)$: the set of common divisors of $m$ and $r$ is the same as the set of common divisors of $n$ and $m$. In particular, the greatest common divisor is the same in both cases.