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

$d\mid a-b$ significa $\dfrac{a-b}d=\dfrac ad-\dfrac bd$ es un número entero. Está claro que si una de estas fracciones es un número entero, entonces también lo es la otra, es decir, $d\mid a\iff d\mid b$ .

$d\mid\gcd(b,a-b)\implies d\mid b$ Por lo tanto $d\mid a$ .

Por lo tanto, un divisor de ambos $a-b$ y $b$ también es un divisor de $a$ .

A la inversa, $k\mid a$ significa $\dfrac ak=\dfrac{a-b}k+\dfrac bk$ es un número entero, por lo que $k\mid a-b\iff k\mid b$ .

$k\mid\gcd(a,b)\implies k\mid b$ Por lo tanto $k\mid a-b$ .

Por lo tanto, un divisor de ambos $a$ y $b$ también es un divisor de $a-b$ . QED

Answer 2

Escribe $u=b$ y $v=a-b$ . Entonces $a=u+v$ y $b=u$ .

Estos dos conjuntos de ecuaciones implican que $d$ divide $u,v$ si $d$ divide $a,b$ . Por lo tanto, $\gcd(u,v)=\gcd(a,b)$ .

En términos de álgebra, las ecuaciones implican que $\{a,b\}$ y $\{u,v\}$ generan el mismo subgrupo de $\mathbb Z$ . Es bien sabido que $\langle x,y \rangle = \gcd(x,y)\mathbb Z$ De ahí el resultado.

Answer 3

Olvidémonos de "lo más grande": veamos simplemente el conjunto de divisores comunes .

El conjunto $\mathrm{CD}(a,b)$ de los divisores comunes de $a$ y $b$ es por definición $$\mathrm{CD}(a,b) = \{ d \in \mathbb{Z} \colon d \text{ divides } a \text{ and } d \text{ divides } b \}.$$

Y del mismo modo, el conjunto $\mathrm{CD}(b,a-b)$ de los divisores comunes de $a$ y $a-b$ es por definición $$\mathrm{CD}(b,a-b) = \{ d \in \mathbb{Z} \colon d \text{ divides } b \text{ and } d \text{ divides } a-b \}.$$

De hecho, tenemos $$\mathrm{CD}(a,b)=\mathrm{CD}(b,a-b)$$ por lo que obviamente tienen el mismo elemento "mayor" (es decir $\max\mathrm{CD}(a,b)=\max\mathrm{CD}(b,a-b)$ ).

Para demostrarlo, comprobamos...

• Si $x \in \mathrm{CD}(a,b)$ entonces $x$ divide ambos $b$ y $a-b$ Así que $x \in \mathrm{CD}(b,a-b)$ .

  Prueba : Por definición $x$ divide $b$ . Además, sabemos que $x$ divide ambos $a$ y $b$ Así que $a=kx$ y $b=k'x$ para algunos enteros $k$ y $k'$ . Así, $x$ divide $(k-k')x=a-b$ .

• Si $y \in \mathrm{CD}(b,a-b)$ entonces $y$ divide ambos $a$ y $b$ Así que $y \in \mathrm{CD}(a,b)$ .

  Prueba : Por definición $y$ divide $b$ . Además, sabemos que $y$ divide ambos $b$ y $a-b$ Así que $b=cy$ y $a-b=c'y$ para algunos enteros $c$ y $c'$ . Así, $y$ divide $(c-c')y=b+(a-b)=a$ .

Answer 4

En primer lugar,

• definición: $b|a \iff \exists k \in \mathbb{Z}: a = k \cdot b$
• Lema 1: $a|b \wedge a|b \Rightarrow a = \pm b$
• Lema 2: $d|a \wedge d|b \Rightarrow d|(ax + by)$ para cualquier $x,y \in \mathbb{Z}$
• Teorema 1: Si a y b son números enteros cualesquiera, no siendo ambos cero, entonces $gcd(a,b)$ es el menor elemento positivo del conjunto $\{ax + by: x,y \in \mathbb{Z}\}$ de combinaciones lineales de a y b.

Por lo tanto, tenemos que demostrar $gcd(,)|gcd(,)$ y $gcd(,)|gcd(,)$ y como $gcd$ es siempre positivo, deben ser iguales por Lema 1 .

1. $gcd(,)|gcd(,)$

Dejemos que $d = gcd(,)$ Por lo tanto $d|a \wedge d|b$ y, además, $d|(a-b)$ ya que es una combinación lineal de $a$ y $b$ ( Lema 2 ).

$d|b$ , $d|(a-b)$ y $gcd(,)$ es una combinación lineal de $b$ y $a-b$ ( Teorema 1 ). Por lo tanto, $d|gcd(,)$ por Lema 2 .

2. $gcd(,)|gcd(,)$

Dejemos que $d = gcd(,)$ Por lo tanto $d|b \wedge d|(a-b)$ .

$a = b + (a - b)$ Por lo tanto $a$ es una combinación lineal de $b$ y $a - b$ .

Por lo tanto, $d|a$ por Lema 2 .

Otra vez, $gcd(a,b)$ es una combinación lineal de $a$ y $b$ por Teorema 1 Por lo tanto $d|gcd(a,b)$ .

Por último, utilizando Lema 1 :

$gcd(,)|gcd(,) \wedge gcd(,)|gcd(,) \Rightarrow gcd(,) = gcd(,)$

Tenga en cuenta que si $a = b = 0$ entonces $gcd(a,b) = gcd(b, a - b) = gcd(0,0) = 0$ por definición.

Prueba de lema 1

Por definición , $b|a \Rightarrow |b| \leq |a|$ . Por lo tanto, $a|b \wedge b|a \Rightarrow |a| = |b| \Rightarrow a = \pm b$ .

Prueba de lema 2

Como $d|a \wedge d|b$ hay algunos enteros $k_1$ y $k_2$ que cumple con $\frac{a}{d} = k_1$ y $\frac{b}{d} = k_2$ .

Ahora, tenemos que demostrar $(ax + by) = k \cdot d$ para algunos $k \in \mathbb{Z}$ .

$(ax + by) = k \cdot d \iff k = \frac{a}{d}x + \frac{b}{d}y = k_1x + k_2y$

Como la multiplicación de dos enteros es un número entero, y esto también se sigue para la suma de dos enteros, así $k_1x + k_2y \in \mathbb{Z}$ .

Prueba de Teorema 1

Esto se demuestra en: Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to algorithms, MIT Press, 3a. ed., 2009.

página 930, Teorema 31.2.