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

Question

El ejercicio siguiente me está volviendo loco, ya que soy el único que no parece entenderlo:

Demostrar la igualdad $\gcd(m, n) = \gcd(n,m\bmod n)$ para cada par de enteros m y n.

La mayoría de las pruebas sólo demuestran que $m\bmod n$ es divisible por $\gcd(m, n)$ pero no entiendo por qué eso significaría que la igualdad se mantiene.

gracias de antemano.

Answer 1

Escriba a $m = qn + r$ donde $q,r$ son números enteros y $0 \le r < n$ .

Sea $d = \text{gcd}(m,n)$ y que $e = \text{gcd}(n,r)$ . El objetivo es mostrar $d=e$ .

Primero mostramos $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*}

Desde $d|n$ y $d|r$ se deduce que $d|\text{gcd}(n,r)$ Por lo tanto $d|e$ .

A continuación mostramos $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*}

Desde $e|m$ y $e|n$ se deduce que $e|\text{gcd}(m,n)$ Por lo tanto $e|d$ .

Sincd $d|e$ y $e|d$ se deduce que $d = e$ .

Answer 2

Sugerencia $ $ Si $\,d\mid n\,$ entonces $\,d\mid m\!\iff\! d\mid \overbrace{m\bmod n}^{ \large m \ -\ q\,n} =:\bar m.\,$ Así $\,n,m\,$ y $\,n,\, \bar m\,$ tienen el mismo conjunto $S$ de común divisores $d,\,$ para que tengan el mismo mayor divisor común $(= \max S).$