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

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.

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

• brilliantly clear prove many thanks! Commented Feb 13, 2017 at 16:17
• @quasi what does the vertical bar stand for? $|$ Commented Feb 13, 2018 at 18:51
• @csandreas1: In this context, the vertical bar is the divisibility symbol. The notation $a|b$ is read as "$a$ divjdes $b$" and it means "$a$ is a divisor of $b$", or equivalently, expressed as an equation, it means $b=ax$, for some integer $x$. Commented Feb 13, 2018 at 20:21
• @quasi Hello i want to ask how do you know d|m-qn from d|n and d|m , by what theorem? Commented Jul 3, 2019 at 9:49
• @fiksx: If $d|a$ then $d|ac$ for all $c$, hence from $d|n$ we get $d|qn$. Also, if $d|a$ and $d|b$ then $d|(a+b)$ and $d|(a-b)$, hence from $d|m$ and $d|qn$, we get $d|(m-qn)$. Commented Jul 3, 2019 at 9:59

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

• It remains true if we replace $\,m\bmod n\,$ by any $\bar m$ such that $\,\bar m\equiv m\pmod{\! n},\,$ i.e. $\,n\mid \bar m - m.\ \$ Commented Feb 13, 2017 at 16:08