Show that $\gcd(m, n) = \gcd(n, r)$ 
Question:
Let $m, n, q, r \in \mathbb Z$. If $m = qn + r$, show that $\gcd(m, n) = \gcd(n, r)$. Hence justify the Euclidean Algorithm.

I found this question in a past test paper, but cannot seem to find a reference in my textbook that indicates how I can go about "proving" the above statement. Can anyone please point me in the right direction?
 A: $m-qn=r$ so if $c$ divides $m$ and $n$ it also divides r. Since this is true for all divisors of $m$ and $n$ it is true for $gcd(m,n)$ and so $gcd(m,n)\le gcd(n,r)$. If $d$ divides $n$ and $r$ then $d$ divides $qn+r$ which equals $m$ so $d$ is a common divisor of $m$ and $n$. Therefore $gcd(n,r)\le gcd(m,n)$ and $gcd(m,n) = gcd(n,r)$
A: To Prove $\gcd(m, n) = \gcd (n, r)$ if $m = qn + r$
Let $\gcd(m, n) = d$.
So $d \mid m$ and $d \mid n$ implies $d \mid r$ (read $d$ divides...)
Similarly if $n = q_1r + r_1$ and $d \mid n$ and $d \mid r$ implies $d \mid r_1$.
Note $r_i$ are reducing by each successive terms, hence this algorithm is guaranteed to terminate.
Now suppose the last expression (say algorithm takes $n$ steps) reads like this:
$$r_{n - 3} = q_{n - 3}r_{n - 2} + r_{n - 1}$$
$$r_{n - 2} = q_{n - 2}r_{n - 1} + r_n$$
For uniqueness by the above logic $d \mid r_n$, let $d_1 \mid r_n$ and $d_1 \mid r_{n - 2}$) [$d_1$ is some divisor of $n, r$], therefore $d_1 \mid (q_{n - 2}r_{n - 1})$.
Now $d_1 \mid r_{n - 3}$ because $d_1 \mid r_{n - 2}$ and $d_1 \mid r_{n - 1}$ and so on $d_1 \mid m$ and $d_1 \mid n$.
Therefore $m = nd$ and $m = nd_1$ but by definition $d$ is the greatest divisor, hence $d > d_1$ and we know that since the choice of $d_1$ was arbitrary, we are sure that $d \mid n$ and $d \mid r$ is the greatest possible $d$, hence the proof.
A: Hint: 
Suppose $d$ divides both $m$ and $n$ (it needn't be the $\gcd$). Then $d$ divides $m+kn$ for any $k \in \mathbb{Z}$.
A: The following is a demonstration using notions of ring theory.
Let $m,n,q,r\in\mathbb{Z}$ such that $m=qn+r$.
Now consider the ideals $J=m\cdot \mathbb{Z}+n\cdot \mathbb{Z}$ and $J'=n\cdot\mathbb{Z}+r\cdot\mathbb{Z}$. The ring of integer is a principal ideal domain, therefore, since $J$ and $J'$ are ideals, there're $d,d'\in\mathbb{Z}$ such that $J=d\cdot\mathbb{Z}$ and $J'=d'\cdot \mathbb{Z}$. Recalling the definition of $\gcd$(greatest common divisor) it's easy to see that $d=\gcd(m,n)$ and $d'=\gcd(n,r)$ knowing that $d$ and $d'$ are the least positive integers, respectively, of $J$ and $J'$. Therefore to show that $\gcd(m,n)=\gcd(n,r)$ is sufficient to show that $J=J'$.
$j'\in J'\rightarrow \exists x',y'\in\mathbb{Z}: j'=nx'+ry'$
We know that $m=nq+r\Leftrightarrow r=m-nq$, so $j'=nx'+ry'=nx'+(m-nq)y'=my'+n(x'-qy')\in J\Rightarrow J'\subset J$.
$j\in J\rightarrow \exists x,y\in\mathbb{Z}: j=mx+ny$
We know that $m=qn+r$, so $j=mx+ny=(nq+r)x+ny=n(qx+y)+rx\in J'\Rightarrow J\subset J'$.
Since $J'\subset J$ and $J\subset J'$, then we have $J=J'$, which allows us to demonstrate what we want.
A: Let $m=qn+r$. We have $gcd(m,n)=gcd(qn+r,n)=gcd(r,n)$, where the last equality follows that if $d=gcd(qn+r,n)$ then since $d|n$ we know $d|qn$ so we can sort of ignore that term.
