gcd(m,n) = gcd(n, m mod n)

Question

The Following exercise is driving me nuts as I'm the only one who does not seem to get it:

Prove the equality $\gcd(m, n) = \gcd(n,m\bmod n)$ for every pair of positive integers m and n.

Most proofs just show that $m\bmod n$ is divisible by $\gcd(m, n)$ but I do not get why that would mean the equality holds.

thanks in advance.

Answer 1

Write $m = qn + r$, where $q,r$ are integers and $0 \le r < n$.

Let $d = \text{gcd}(m,n)$ and let $e = \text{gcd}(n,r)$. The goal is to show $d=e$.

First we show $d|e$ . . .

\begin{align*} &d = \text{gcd}(m,n)\\[6pt] \implies\;&d|m \text{ and }d|n\\[6pt] \implies\;&d|(m - qn)\\[6pt] \implies\;&d|r \end{align*}

Since $d|n$ and $d|r$, it follows that $d|\text{gcd}(n,r)$, hence $d|e$.

Next we show $e|d$ . . . \begin{align*} &e = \text{gcd}(n,r)\\[6pt] \implies\;&e|n \text{ and }e|r\\[6pt] \implies\;&e|(qn+r)\\[6pt] \implies\;&e|m \end{align*}

Since $e|m$ and $e|n$, it follows that $e|\text{gcd}(m,n)$, hence $e|d$.

Sincd $d|e$ and $e|d$, it follows that $d = e$.

Answer 2

Hint $ $ If $\,d\mid n\,$ then $\,d\mid m\!\iff\! d\mid \overbrace{m\bmod n}^{ \large m \ -\ q\,n} =:\bar m.\,$ Thus $\,n,m\,$ and $\,n,\, \bar m\,$ have the same set $S$ of common divisors $d,\,$ so they have the same greatest common divisor $(= \max S).$