Demostrar que $(a+nb,b)=(a,b)$

Question

Demostrar que $(a+nb,b)=(a,b)$ para cualquier número entero $n$ .

Dejemos que $(a,b) = d$ .

Así que $d = ax_1 + by_1$ donde $x_1$ y $y_1 \in \mathbb{Z} $

Ahora considere, $(a+nb)x_1 + b(y_1 -nx_1)$ . Ahora claramente $(y_1 -nx_1)$ y $x_1$ son $\in \mathbb{Z}$

También

$(a+nb)x_1 + b(y_1 -nx_1) = ax_1 + by_1 = d $

¿Es esto correcto?

Answer 1

Si $d$ es un divisor común de $a$ y $b$ entonces también es un divisor de $a+nb$ .

Si $d$ es un divisor común de $a+nb$ y $b$ entonces también es un divisor de $a$ (porque $a = (a+nb) -nb$ ).

Por lo tanto, el conjunto de divisores comunes de $\{a,b\}$ es exactamente igual al conjunto de divisores comunes de $\{a+nb,b\}$ . Por tanto, el valor máximo de cada conjunto (es decir, los GCD) es el mismo.

Answer 2

Esto demuestra una dirección, pero no la otra. Recuerde que $d=(a,b)$ si y sólo si $d$ es el El más pequeño entero positivo expresable como $ax+by$ . Ha demostrado que si $d=(a,b)$ entonces existe $x$ y $y$ tal que $d=(a+nb)x+by$ pero no que sea el número entero más pequeño de esta forma.

Ya casi está, y hay varias formas de completar la prueba. Una sería asumir $e=(a+bn,b)=x_2(a+bn)+y_2b$ y demostrar que $e=xa+yb$ para algunos $x,y\in \mathbb Z$ .

(Lo que hizo demuestra que $(a+nb,b)\leq(a,b)$ y hacerlo de nuevo en la otra dirección muestra $(a+nb,b)\geq (a,b)$ por lo que combinando los dos hechos se obtiene la igualdad).