Si $a, b, q, r \in \mathbb{Z}$ tal que $a = bq + r$ . Prueba $\gcd(a,b) = \gcd(b, r).$

Question

Esto es lo que tengo hasta ahora, dejé $d_1$ dividir $a$ y $b$ para poder escribir $a$ y $b$ como $a = d_1k$ y $b = d_1j$ . Después de la manipulación, pude lograr que $d_1 \mid r$ tras sustituir los valores de $a$ y $b$ en $a - bq = r$ . En definitiva, quiero demostrar que $d_1 \mid d_2$ y viceversa para demostrar que mi $\gcd$ es único, pero ¿cómo hago para establecer que es el el más grande . Gracias por su tiempo.

Answer 1

Sugerencia $\ $ Si $\ d\mid \color{#c00}b\ $ entonces $\, d\mid \color{#c00}bq\!+\!r\iff d\mid r,\,$ por lo tanto $\, b,bq\!+\!r\,$ y $\,b,r\,$ tienen el mismo conjunto $\cal D$ de común divisores $\,d,\,$ por lo que tienen el mismo el más grande divisor común $(= \max\cal D).$

Answer 2

Dejemos que $d = \gcd(a,b)$ y $e = \gcd(b,r)$ . Desde $d | a $ y $d | b$ , $d | (a - bq)$ es decir, $d | r$ . Desde $d | b$ y $d | r$ , $d | e$ . Argumentar de forma similar para obtener $e | d$ . Entonces $e = d$ .