Demostrar que $\gcd(a, b) = \gcd(b, a-b)$

Question

Puedo entender el concepto de que $\gcd(a, b) = \gcd(b, r)$ , donde $a = bq + r$ que se basa en el hecho de que $\gcd(a, b) = \gcd(b, a-b)$ pero no tengo ninguna intuición para esto último.

Answer 1

Dejemos que $d = \text{gcd}(a,b)$ entonces $d|a$ y $d|b$ Así que $d|(a-b)$ y $d|\mbox {gcd}(b,a-b)= d'$ . También $d'|b$ y $d'|(a-b)$ Así que $d'|(b+(a-b)) = a$ y $d'|\mbox {gcd}(a,b) = d$ . Así que $d = d'$ .

Answer 2

Lema: $gcd(x,y)=d$ si $d$ es el menor número natural que puede expresarse como una combinación lineal de $x$ y $y$ (en $\mathbb{Z}$ )

Tenemos $gcd(a,b)=d$

$d=ap+bq$ para algunos $p,q\in \mathbb{Z}$

$d=ap-bp+bp+bq=(a-b)p+b(p+q)=(a-b)p+bq'$

donde $q'=p+q\in \mathbb{Z}$

Así,

$gcd(a-b,b)=d$

Answer 3

Supongamos que $\gcd(a, b) = q$ significa al menos que $q | a, q|b$ entonces $q|(a - b)$ . Esto es cierto para todo divisor, de modo que para $\gcd$ también.

Un usuario preguntó a la inversa, pero también es obvio. Denote $s = a - b$ entonces $\gcd(b, s) = \gcd(b, s + b) = \gcd(b, a)$ .

Answer 4

Por definición $$gcd(a,b)=g\iff g|a,b\land (\forall h:h|a,b\implies h\le g).$$

Entonces

$$\begin{align}gcd(a,b)=g&\implies g|a,b\land (\forall h:h|a,b\implies h\le g)\\&\implies g|b,(a-b)\land (\forall h:h|b,(a-b)\implies h|a,b\implies h\le g)\\&\implies gcd(b,a-b)=g.\end{align}$$

Answer 5

Todo divisor común de $a$ y $b$ también es un divisor común de $b$ y $a-b$ .

Todo divisor común de $b$ y $a-b$ también es un divisor común de $a$ y $b$ , como $a=(a-b)+b$ .