Show that $\gcd(m, n) = \gcd(n, r)$

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.