Prueba de $\gcd$ siendo la combinación lineal más pequeña de $a,b \in \mathbb {Z}$ .

Question

Por favor, examine mi enfoque:

Primero hay que demostrar que para la combinación de menor valor positivo (let, $l$ ), dividirá $a, b \in \mathbb{Z}$ .

Utilizará el enfoque indirecto o de contradicción para demostrar que $l \mid a$ . Similar se extenderá a $l \mid b$ .

Así, para $l \nmid a, \exists q, r \in \mathbb {Z}$ s.t. $a = al +r, 0 \lt r \lt l$ . Por lo tanto, $r = a - q.l = a - q(ax_0 + by_0) = a(1 - qx_0) - qby_0$ . Así que.., $r$ es una combinación lineal de $a, b$ con multiplicadores enteros, sea $x,y,$ donde $x = 1 - qx_0, y = -qy_0$

La forma asumida para $l = ax_0 + by_0$ . Dado, por contradicción que $0 \lt r \lt l$ tenemos las siguientes desigualdades, ya que los multiplicadores enteros de $r$ debe ser menor que el de $l$ y también positiva:

\=> $1- qx_0 \lt x_0$ - (i) & $-q \lt 1$ - (ii)

\=> $1 \lt x_0(1+q)$ - (i) & $q \gt -1$ - (ii)

Sustituyendo por $q$ de (ii) en (i), obtenemos:

$ 1 \lt x_0($ valor negativo $)$ -- obviamente falsa, por lo tanto demostrado que $l \mid a$ por contradicción.

---

Anexo A la vista de las respuestas recibidas, se ha modificado como sigue. En primer lugar, asumir que $a,b \gt 0$ . En segundo lugar, formar cuatro casos de posibles valores del multiplicador entero, y tratará de demostrar por contradicción en cada uno.

Caso (i) : $x_0 \gt 0, y_0 \gt 0$ : Ya se ha demostrado este caso anteriormente.

Caso (ii) : $x_0 \gt 0, y_0 \lt 0$ : Implica $-qy_0 \lt y_0$ pero como $y_0 \lt 0$ por lo que se cancela $y_0$ de ambas partes conduce a: $-q \gt 1 => q \lt -1$ .

Las dos desigualdades son : $1 \lt x_0(1+q)$ - (i), $q \lt -1$ - (ii)

Sustituyendo por $q$ de (ii) en (i), obtenemos: $1 \lt x_0$ (valor negativo), de nuevo obviamente falso.

Caso (iii) : $x_0 \lt 0, y_0 \gt 0$ : Implica que las dos desigualdades son: $1- qx_0 \lt x_0$ - (i), $q \gt -1$ - (ii)

$1 \lt x_0(1+q)$ pero como $x_0 \lt 0$ por lo que cambia a $-1 \gt x_0(1+q)$ para positivo $x_0$ . Ahora bien, esto tampoco es posible ya que $(1+q)\gt 0$ .

Caso (iv) : $x_0 \lt 0, y_0 \lt 0$ : Como asumir $a, b \gt 0$ por lo que este caso no es posible.

Por lo tanto, se ha demostrado que para todos los valores posibles de $x_0, y_0$ .

Answer 1

Esto es lo que he entendido de tu pregunta: quieres demostrar que si $l = \min\{ ax+by > 0 : x,y \in \mathbb{Z} \}$ entonces $l \mid a$ y $l \mid b$ . Suponiendo que $ l \nmid a$ escribe $a = ql + r$ donde $ 0 < r < l$ y así llegar a $r = a(1-qx_0) + b(-qy_0)$ donde $l = ax_0 + by_0$ .

Ahora, usted argumenta que desde $0 < r < l$ los números enteros que aparecen en la combinación lineal para $r$ deben ser ambos positivos, y deben ser menores que los enteros respectivos que aparecen en la combinación lineal para $l$ . Esto es incorrecto. Parece que usted está asumiendo que $x_0$ y $y_0$ son ambas positivas, pero esto no es cierto. Prueba a calcular las combinaciones lineales para números enteros positivos $a$ y $b$ y verá que $x_0$ y $y_0$ suelen tener signo contrario. También parece que usted está asumiendo que si una combinación lineal es menor que otra combinación lineal, entonces lo mismo puede decirse de los coeficientes respectivos. De nuevo, esto no es cierto en general, incluso si los coeficientes son todos positivos. Por ejemplo $a=1$ y $b=2$ . Entonces $5a+b < 4a+2b$ . Puedes encontrar muchos más ejemplos jugando con los números.

En su lugar, esto es lo que tienes que hacer para completar la prueba. Puesto que $0 < r < l$ y $r$ se expresa como una combinación lineal integral de $a$ y $b$ implica que $l$ no es el número entero positivo más pequeño que puede expresarse como una combinación lineal de $a$ y $b$ . Esto es una contradicción. Por lo tanto, nuestra hipótesis original de que $l \nmid a$ es falso.

---

En cuanto a su prueba modificada, tenga en cuenta que usted todavía está haciendo la suposición de que si $ax+by < ax’ + by’$ entonces $x < x’$ y $y < y’$ . Como he mencionado en el segundo párrafo anterior, esto no es cierto en general, independientemente de los signos de $x$ , $y$ , $x’$ y $y’$ . Así pues, ninguno de los cuatro casos demuestra realmente el resultado deseado. De hecho, como no se puede decir nada en general sobre los tamaños relativos de $x$ y $x’$ y $y$ y $y’$ , del hecho de que $ax + by < ax’ + by’$ Por lo tanto, a mi entender, su planteamiento no puede conducir a una solución.

La forma más sencilla de concluir la contradicción es la que mencioné en mi tercer párrafo, más arriba.