Sean \( a,b \) enteros con mcd=d.
Vamos a demostrar que existen enteros \( x,y \) tales que \( ax+by=d \) siendo “d” el máximo común divisor de (a,b) como se ha dicho.
Por comodidad, podemos elegir, por ejemplo, que a,b sean enteros positivos (pues eligiendo los signos convenientes para x,y siempre podremos igualar a un “d” entero positivo).
Tenemos que \( ax+by \) (sea “d” u otro) no puede ser cero, porque cero no es divisor de nadie (no puede ser cero salvo ax=-by, que es una tontería sin interés).
Entonces vamos a considerar el conjunto de los divisores (en el sentido de que son números distintos de cero) según esta forma \( ax+by \).
Queda claro que este conjunto tiene que tener un mínimo “m”, porque está acotado, ningún elemento podrá ser nunca menor que 1 (el mínimo podría ser 1,5, 7..., cualquier natural mayor que cero).
Luego podemos definir el mínimo como
\( m=ax_{0}+by_{0} \).
Se trata de demostrar que ese mínimo “m” es siempre el máximo común divisor; m=d.
Entonces hay que probar, primeramente, que “m” divide a \( d=mcd(a,b) \), con lo cual empezamos por probar que “m” divide a “a”:
Por el algortimo de la división tenemos que existe \( a=qm+r \), donde \( r<m \) (esto es bastante obvio).
Sustituyendo “m” por \( m=ax_{0}+by_{0} \), nos queda
\( a=q(ax_{0}+by_{0})+r\Rightarrow \)
\( a=qax_{0}+qby_{0}+r\Rightarrow \)
\( (1-qx_{0})a-qby_{0}=r\Rightarrow \)
Luego “r” tiene esta forma \( ax+by \); lo cual se ve simplemente haciendo \( x=(1-qx_{0}) \) y análogamente para el otro coeficiente de “b”.
Eso significa que “r” pertenece a este conjunto \( ax+by \) y, a la vez, como \( r<m \), es menor que el mínimo de ese conjunto; ¡pero esto es imposible!
Lo único que puede pasar es que sea r=0 (que en este caso sí puede ser porque es el resto cero, existe).
Luego si el resto es cero, esto implica que \( m \), el mínimo, divide a \( a \).
Análogamente se hace exactamente igual para “b”, se demuestra del mismo modo que “m” divide a “b”; y ambas cosas implican que “m” divide a “d”.
Al probar eso, hemos demostrado que aquí, \( m=ax_{0}+by_{0} \), “m” sólo puede ser igual a “d”, el máximo común divisor de (a,b), pues es el mínimo término independiente positivo de la combinación lineal; no puede ser mas pequeño. O sea, dado esto último, como “m” divide a “d”, m=d, no puede ser menor.
...
Resumiendo, llega a que el menor del conjunto de los números de esta forma \( ax+by \) es más pequeño que el mínimo de los números de esta forma \( ax+by \); luego tiene esa forma, pero no pertenece al conjunto, no es un divisor. ¿Qué es? El resto cero. Luego “m” divide a “d”.
Preciosa demostración.
Este teorema sirve principalmente para resolver ecuaciones diofánticas, sistemas de congruencias con el teorema chino del resto... Pero para estas demostraciones, para mí, es meter más letras de las necesarias, complicarlo. Pero, bueno, si lo hace así en los libros, pues así.
...
Yo tengo una demostración mía aquí, bastante larga y pesada, carente de esa genialidad:
https://foro.rinconmatematico.com/index.php?topic=92222.msg373207#msg373207[/sopiler]
Saludos.
