¿Cómo se puede probar este hecho sobre los MCD y el algoritmo euclidiano?

Answer 1

Se basa principalmente en la propiedad que [math] gcd (a, b) = gcd (b, a – b) [/ math].

Prueba:
Deje [math] mcd (a, b) = r_1, mcd (b, a – b) = r_2 [/ math]
[matemática] r_1 [/ matemática] divide [matemática] a, b [/ matemática] ya que es su máximo divisor común, por lo tanto [matemática] r_1 [/ matemática] divide [matemática] a – b [/ matemática], luego [ matemáticas] r_1 \ leq r_2 [/ matemáticas].
también
[matemática] r_2 [/ matemática] divide [matemática] b, a – b [/ matemática] ya que es su máximo divisor común, por lo tanto [matemática] r_2 [/ matemática] divide [matemática] b + (a – b) = a [/ math], luego [math] r_2 \ leq r_1 [/ math].
entonces obtienes [math] r_1 = r_2 [/ math].

Después de esto, puede deducir que [matemática] mcd (x, y) = mcd (x – y, y) [/ matemática], [matemática] mcd (x – y, y) = mcd (x – 2y, y) [/ math], [math] \ dots [/ math] [math] gcd (x – (n – 1) y, y) = gcd (x – ny, y) [/ math], que demuestra la propiedad que eres preguntar por.

Answer 2

Primera nota que

un número divide tanto a como b si y solo si divide a – b y b.

Entonces, si restas b varias veces t de a , puedes decir

un número divide tanto a como b si y solo si divide a – tb y b.

Por lo tanto, los divisores de a y b son los mismos que los divisores de r y b.

Por lo tanto, ayb tienen el mismo MCD que r y b.

Answer 3

No hagas ninguna división. Simplemente siga el algoritmo euclidiano para los pares [matemática] (a, b) [/ matemática] y [matemática] (r, b) [/ matemática].

Answer 4

Demuestre dos hechos: (1) cualquier número entero que divide a b y r divide a, y (2) cualquier número entero que divide a a y b divide a r. Ambos son bastante fáciles si traduces “x divide y” en “y = xk para algún entero k”.