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?

• Strategy: Show that the set of common divisors of $m$ and $n$ is the same as the set of common divisors of $n$ and $r$. – André Nicolas Aug 19 '15 at 21:20

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.

• Whew, that was a lot of work. But you're new here, so I shouldn't mind. – Robert Soupe Aug 20 '15 at 3:47

$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)$

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}$.

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.