La prueba de $\gcd(a,b)=ax+by$

Question

Aquí está mi prueba de $\gcd(a,b)=ax+by$$a, b, x, y \in \mathbb{Z}$. Estoy haciendo algo mal? Existen más fácil pruebas?

$a,b \in \mathbb{Z}, g=\gcd(a,b)$ y supongamos $g \neq ax + by$. Deje $c$ ser un divisor común de a$a$$b$. Entonces

$$\forall x', y' \in \mathbb{Z}: c | ax' + by'\Longrightarrow\exists q_1, q_2 \in \mathbb{Z}\,\,\, s.t.\,\,\, c q_1 = ax' + by'\,\,,\,\,cq_2 = g$$

Así

$$gcd(a, b)=g=c q_2 = c q_1 \frac{q_2}{q_1} = \left(\frac{q_2}{q_1}x'\right)a + \left(\frac{q_2}{q_1}y'\right)b$$ So if we have $q_1|q_2$ then we found $\gcd(a,b)=ax'+'$ for all $x', y' \in \mathbb{Z}$.

Ahora

$$\frac{q_1}{q_2}=\frac{c q_1}{c q_2} = \frac{ax'+by'}{g}$$ but $g|a$ and $g|b$ so $\existe q_3 \in \mathbb{Z}: \frac{q_1}{q_2}=q_3 \Rightarrow q_1=q_2 q_3 \Rightarrow q_1 | q_2\,$ . QED.

Answer 1

La mejor prueba de que yo sé es como sigue:

Consideremos el conjunto a $S = \{ax+by>0 : a,b \in \mathbb{Z}\}$. Deje $d = \min S$. Ahora nos muestran la siguiente:

• $d$ es un divisor común de a$a$$b$.
• Ningún divisor común de a $a$ $b$ debe dividir $d$.

Si podemos demostrar que esas dos cosas, entonces es trivial que se $d$ es el máximo común divisor de a$a$$b$, y, por tanto, que el máximo común divisor de a $a$ $b$ es de la forma $ax+by$.

Para mostrar que $d$ divide $a$$b$: supongamos por contradicción que $d$ no divide $a$. A continuación, $a=qd+r$ donde$q\ge 0$$0<r<d$. Desde $a=qd+r$, $qd=a-r$, y ya que tenemos que $d=ax+by$, $q(ax+by)=a-r$, por lo $r=a(1-qx)-bqy$. Por lo $r$ es una combinación lineal de $a$$b$, y desde $r>0$, lo que significa que $r\in S$. Desde $r<d$ y tuvimos supone $d$$\min S$, tenemos una contradicción. Por lo $d$ debe dividir $a$.

Idéntico argumento demuestra que $d$ debe dividir $b$.

Ahora queremos demostrar que ningún divisor común de a $a$ $b$ debe dividir $d$. Esto es fácil de demostrar: si $a=uc$$b=vc$,$d=ax+by=c(ux+vy)$, lo $c$ divide $d$.

Por lo tanto, $d$ es el máximo común divisor de a$a$$b$, y es de la forma $ax+by$.

Answer 2

La pregunta de cuál es el más fácil la prueba de la representación lineal de la gcd (la Identidad de Bezout). En mi opinión es la prueba de abajo, que también tiene mucho que ofrecer conceptualmente, ya que alude a la implícita ideal de la estructura. Esta estructura fundamental se pondrán de manifiesto en estudios posteriores.

El conjunto $\rm\:S\:$ de los enteros de la forma $\rm\:x\:a + y\:b,\ x,y\in \mathbb Z\:$ es cerrado bajo la resta entonces, por el Lema de abajo, todos los $\rm\:n\in S\:$ es divisible por el menos positivo $\rm\:d\in S.\:$, con Lo que $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b,\:$ es decir, $\rm\:d\:$ es un común divisor de a $\rm\:a,b,\:$ necesariamente mayor, por $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d =\hat x\:a+\hat y\:b\:$ $\Rightarrow$ $\rm\:c\le d.$

Lema $\ \ $ Si un conjunto no vacío de enteros positivos $\rm\: S\:$ satisface $\rm\ n > m\ \in\ S \ \Rightarrow\ \: n-m\ \in\ S$
a continuación, cada elemento de a $\rm\:S\:$ es un múltiplo de al menos el elemento $\rm\:m_{\:1} \in S.$

Prueba de $\ \: $ Si no hay un mínimo de nonmultiple $\rm\:n\in S,\,$ contra $\rm\:n-m_{\:1} \in S\:$ es un nonmultiple de $\rm\:m_{\:1}.$

Comentario $\ $ Este fundamentales lema, interpretado en el procedimiento, los rendimientos de Euclides clásico algoritmo para calcular el mcd utilizando sólo resta repetida.

Esto lineal de la representación de la mcd es conocida como la identidad de Bezout para el mcd. No es necesario que se repite en todos los dominios donde gcds existen, por ejemplo, en el dominio $\rm\:D = \mathbb Q[x,y]\:$ de los polinomios en la $\rm\:x,y\:$ con coeficientes racionales tenemos $\rm\:gcd(x,y) = 1\:$, pero no hay $\rm\:f(x,y),\: g(x,y)\in D\:$ tal que $\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$ de hecho, si es así, entonces la evaluación en $\rm\:x = 0 = y\:$ rendimientos $\:0 = 1.$