Demostrando que $\gcd(a,b) = as + bt$, es decir, $\gcd$ es una combinación lineal.

Question

Para cualquier % distinto de cero enteros $a$y $b$, allí existen enteros $s$ y $t$ tal que $\gcd(a,b) = as + bt$. Por otra parte, $\gcd(a,b)$ es el entero positivo más pequeño de la forma $as + bt$.

Sé de una prueba de esta pregunta, en el que consideramos $$S = \ {am + bn ~ | ~ \text{$ m,n \in \mathbb{Z} $ y $ am + bn > 0 $} },$$ pero no lograron obtener la prueba. ¿Alguien puede por favor explicar este teorema?

Answer 1

Tome el conjunto $$S=\{ax+by>0:x,y\in \Bbb Z\}$$

Sin pérdida de generalidad, supongamos que $a<b$. A continuación,$b-a>0$$S$, lo $S$ es un conjunto no vacío positiva de los números naturales. Por el principio de orden, existe al menos un elemento de a $d\in S$, que sabemos que es de la forma $ax'+by'$. Por el algoritmo de la división, existe $q,r$ $0\leq r <ax'+by'$ tal que $$a=qd+r$$

Pero, a continuación, $a-qd=r$ es un número no negativo de la forma$ax+by$, pero menor que $d$, por lo que debe forzosamente ser cero. Esto significa que el resto al $d$ divide $a$$0$; lo que significa que $d\mid a$. Por una completamente análogo argumento, se deduce que el $d\mid b$. Por lo $d$ es un divisor común de a$a$$b$. Pero si $c$ es ningún divisor común de a$a$$b$, se debe dividir $ax'+by'=d$. Por la definición de la $\gcd$, se demostró que $\gcd(a,b)=d$. $\blacktriangle$

Answer 2

Esto se conoce como identidad de Bezout y puedes estudiar la sección 4 de este http://math.bard.edu/belk/math332s09/NumberTheory.pdf

Answer 3

No soy demasiado rápido, por lo que generalmente es útil mirar ejemplos concretos (digamos, $\gcd (83, 56) =1$) antes de considerar el uno general.

Si usted puede mostrar por qué este proceso termina (en general), creo que debería hacerse.

$83 = 1 \times 56 + (83-56)$

$56 = 2 \times (83-56) + (56 - 2 \times (83-56))$

$83-56 = 13 \times (56 - 2 \times (83-56)) + (83-56-(13 \times (56 - 2 \times (83-56))))$

y que el último resto, $1=\gcd(83,56)$.

$1=(83-56-(13 \times (56 - 2 \times (83-56))))$

$1=83-56-(13 \times (-2 \times 83 + 3 \times 56)$

$1 = 83-56 + 26 \times 83 - 39 \times 56$

$1 = 27 \times 83 - 40 \times 56$

Y sus coeficientes.

Answer 4

¿Sabes cómo calcular el gcd de $a$ y $b$ con el Algoritmo euclidiano?

Si es así, una forma primaria de producir $s$ y $t$ es para subir el Algoritmo euclidiano.

Esto se explica aquí bajo la identidad de Bezout.