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?

  • $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ Whew, that was a lot of work. But you're new here, so I shouldn't mind. $\endgroup$ – 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)$



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.