¿Cuál es la forma más directa de explicar por qué [math] \ text {gcd} (a, b) [/ math] es el número positivo más pequeño en [math] \ {ax + by \ mid x, y \ in \ mathbb { Z} \} [/ matemáticas]?

Answer 1

Cualquier número que divida tanto [math] a [/ math] como [math] b [/ math] debe dividir todo de la forma [math] ax + entre [/ math]. Por lo tanto, el MCD, como tal número, divide a todos los miembros positivos del conjunto [math] \ {ax + por | x, y \ in \ mathbb {Z} \} [/ math], y por lo tanto, ciertamente no puede Ser más grande que cualquiera de ellos. Ahora sabemos que el MCD es menor o igual que el menor entero positivo de ese conjunto.

¿Por qué no puede ser estrictamente menor que ese mínimo? Bueno, es suficiente para mostrar que el GCD es un miembro de ese conjunto. Si es así, no puede ser más pequeño que su miembro menos (positivo), ¿verdad? La forma más directa e intuitiva de ver que el GCD es una combinación lineal de los números originales es simplemente llevar a cabo el algoritmo natural para encontrar el GCD:

– Escriba [matemáticas] a [/ matemáticas] como algo multiplicado por [matemáticas] b [/ matemáticas] más algún resto. Observe que el resto es una combinación lineal de [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas].

– Escriba [math] b [/ math] como algo multiplicado por el resto más otro resto más pequeño. Observe que el nuevo residuo es una combinación lineal de [matemáticas] b [/ matemáticas] y el resto anterior, y por lo tanto también es una combinación lineal de [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas].

– Enjuague y repita. Eventualmente alcanzará un resto de 0, y el último resto antes de eso es el MCD. Al rastrear los pasos, puede presentar ese MCD como una combinación lineal de [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas].

---

Un ejemplo podría ayudar. Busquemos el MCD de [matemáticas] 13 [/ matemáticas] y [matemáticas] 45 [/ matemáticas].

A. [matemáticas] 45 = 3 \ por 13 + 6
[/matemáticas]

B. [matemáticas] 13 = 2 \ veces 6 + 1 [/ matemáticas]

C. [matemáticas] 6 = 6 \ veces 1 + 0 [/ matemáticas]

Entonces, el MCD es [matemática] 1 [/ matemática], el último resto distinto de cero, y podemos rastrear para encontrar la combinación lineal. Comenzamos con la ecuación B,

[matemáticas] 1 = 1 \ veces 13 – 2 \ veces 6 = [/ matemáticas]

y ahora use la ecuación A para reemplazar [matemáticas] 6 [/ matemáticas] con una combinación de [matemáticas] 45 [/ matemáticas] y [matemáticas] 13 [/ matemáticas]:

[matemáticas] = 1 \ veces 13 – 2 \ veces (45 – 3 \ veces 13) = [/ matemáticas]

[matemáticas] = -2 \ veces 45 + 7 \ veces 13 [/ matemáticas]

y aquí escribimos [matemáticas] 1 [/ matemáticas] como una combinación lineal de [matemáticas] 45 [/ matemáticas] y [matemáticas] 13 [/ matemáticas].

Answer 2

Con respecto a la respuesta de Alon Amit, esta pregunta podría querer una respuesta que no se base en teoremas o algoritmos preexistentes. Considere esto que podría ser más convincente de inmediato …

Para revisar, si g es el máximo común divisor de a y b, entonces, por definición, hay enteros m y n tales que a = gm y b = gn. Además, myn son números coprimos porque si hubiera un número q mayor que 1 que dividiera tanto myn, entonces gq dividiría tanto a como b, contradiciendo la premisa de que g es el máximo divisor. Cosas estándar

Ahora se ha dado un conjunto que está definido para contener los valores de (ax + by) para todos los enteros x, y. Llame a este conjunto S. Cada elemento de S se puede escribir como (gm) x + (gn) y = g (mx + ny), por lo que cada elemento de S es divisible por g. Podemos asignar el conjunto S a un nuevo conjunto T donde cada elemento de T será el elemento correspondiente de S dividido por g. Entonces g es el elemento menos positivo de S si y solo si 1 es el elemento menos positivo de T. Entonces queda por demostrar que para cualesquiera dos números coprimos myn hay enteros x e y tales que mx + ny = 1 .

Mostramos eso de la siguiente manera. Cree n productos multiplicando m por cada uno de los números 0, 1, …, (n-1). Entonces obtendremos m (0), m (1), …, m (n-1). Ahora cada uno de esos productos tiene algún resto cuando se divide por n. Si dos de esos productos, m (i) ym (j), tuvieran el mismo resto, entonces m (i) -m (j) sería divisible por n. Eso significa que n dividiría m (ij). Como n es coprimo para m, entonces n necesitaría dividir (ij). Pero dado que tanto i como j son menores que n, su diferencia no puede dividirse entre n. Contradicción. Esto significa que no hay dos de los restos iguales. Como los restos están todos en el rango de 0 a n-1, entonces cada número en ese rango es un resto para uno de los productos. Eso significa que hay un número x tal que mx tiene un resto de (n-1) cuando se divide por n. Y eso significa que hay un número z tal que mx + (n-1) = nz. Reescribe eso como mx + n (1-z) = 1. Establece y = 1-z. Entonces mx + ny = 1. QED