Es el máximo común divisor de dos números realmente los más pequeños combinación lineal?

Question

En una conferencia nota del MIT en la teoría de los números dice:

Teorema 5. El máximo común divisor de a y b es igual al menor positiva combinación lineal de a y b.

Por ejemplo, el máximo común divisor de 52 y 44 es de 4. Y, efectivamente, el 4 es un combinación lineal de 52 y 44:
6 · 52 + (-7) 44 = 4

Lo que sobre las 12 y las 6 de su mcd es 6 y el 0, que es menos de 6 puede ser

Answer 1

Se escribió a sí mismo: el mcd es el más pequeño positivo de la combinación lineal. Positivo menor que combinación lineal es una forma abreviada de menor positiva número, que es una combinación lineal. Es cierto que $0$ es una combinación lineal de $12$ $6$ con coeficientes enteros, sino $0$ no es positiva.

La prueba no es difícil, pero es un poco larga. Damos todo detalle a continuación.

Deje $e$ ser el más pequeño positivo combinación lineal $as+bt$ $a$ $b$ donde $s$ $t$ son enteros. Supongamos que, en particular, que $e=ax+by$.

Deje $d=\gcd(a,b)$. A continuación, $d$ divide $a$$b$, por lo que se divide $ax+by$. Por lo tanto $d$ divide $e$, y por lo tanto, en particular,$d\le e$.

Nos muestran que en el hecho de $e$ es un divisor común de a$a$$b$. Esto significa que $e$ es un divisor común de a$a$$b$, lo que implica que $e\le d$. Que, junto con nuestro anterior $d\le e$, implicará que el $d=e$.

Por lo que sigue siendo para mostrar que $e$ divide $a$ $e$ divide $b$. Nos muestran que $e$ divide $a$. La prueba de que $e$ divide $b$ es esencialmente el mismo.

Supongamos que al contrario que $e$ no divida $a$. A continuación, cuando se trate de dividir a $a$$e$, se obtiene un positivo resto. Más precisamente, $$a=qe+r,$$ donde $0\lt r\lt e$. Entonces $$r=a-qe=a-q(ax+by)=a(1-qx)+b(-qy).$$ Esto significa que $r$ es una combinación lineal de $a$$b$, y es positivo y menor que $e$. Esto contradice el hecho de que $e$ es el más pequeño positivo de la combinación lineal de $a$$b$.