Identidad de Bezout

Versión para impresión


El  máximo común divisor de dos enteros $a, b$ (no ambos nulos) se puede expresar como una combinación lineal entera de los números $a$ y $b$: $$MCD(a,b)=ax_0+by_0,$$ para algunos enteros $x_0, y_0$.

Más aun, $MCD(a,b)$ es el elemento mínimo positivo del conjunto de combinaciones lineales enteras $\{ax+by\}$.

Demostración(es)
Demostración: 

La demostración clásica inicia considerando el conjunto de las combinaciones lineales enteras $ax+by$ de los enteros $a, b$ dados, y elige el mínimo elemento positivo, digamos $d$, de ese conjunto. Procede entonces a demostrar que ese elemento mínimo es el $MCD(a,b)$. La demostración de esto se basa en el algoritmo de la división: primero se demuestra que $d$ divide a ambos números y, como $d$ es del conjunto $S$, se llega a que cualquier otro divisor común de $a$ y $b$ tiene que dividir a $d$; de aquí que $d$ sea el $MCD(a,b)$.

Sea $d$ el mínimo positivo de $S=\{ax+by|x,y \in{Z}\}$. Consideremos ahora la división $a/d$. Por el algoritmo de la división deben existir $q$ y $ r $ enteros, con $0\leq{r}$ y menor que $d$, tales que $a=qd+r$. Es decir, $r=a-qd$. Pero, como $a$ y $d$ son de $S$, $ r $ es también de $S$. Y se tiene que concluir que $r=0$, pues $d$ es el mínimo positivo. Esto demuestra que $d$ divide a $a$. De manera similar, $d$ divide a $b$.

Finalmente, sea $d'$ cualquier otro divisor común de $a$ y $b$. Debería ser claro que $d'$ divide a cada uno de los elementos de $S$. En particular divide a $d$. Por tanto, $d'\leq{d}$. Es decir, $d$ es el $MCD(a,b)=ax_0+by_0$, para algunos enteros $x_0, y_0$.




Imagen de jmd

La demostración de la

La demostración de la identidad de Bezout está llena de sutilezas.

En primer lugar ¿por qué se escoge el mínimo positivo del conjunto de combinaciones lineales enteras como candidato para MCD? Ahora bien, que $d$ sea el mínimo de $S$ es la clave para demostrar que $d$ es común divisor de $a$ y$ b$. Pero la prueba misma de este hecho es ya una sutileza: el residuo $ r $ no puede ser positivo y menor que el mínimo de los positivos (por tanto tiene que ser nulo).

Finalmente está el hecho de que si $d'$ divide a $d$ entonces es menor o igual que $d$: trivial, pero no al alcance del novicio...

La elección del mínimo positivo del conjunto $S$ de combinaciones lineales enteras de $a$ y $b$ merece un comentario más detallado. En primer lugar ¿cómo sabemos que existe? Esta sutileza se denomina principio de la buena ordenación: todo conjunto no vacío de enteros positivos tiene un elemento mínimo.

Aparte de que la identidad de Bezout se pueda considerar como un decantamiento histórico de ciertos problemas de divisibilidad, puede que sea pertinente añadir también que la conjetura de la combinación lineal (de que el máximo común divisor de dos números es una combinación lineal entera de éstos) surge de manera natural del algoritmo de Euclides. (La demostración más directa --aunque no la más simple, ni la más elegante-- de la identidad de Bezout es mediante un análisis de las consecuencias de divisibilidad del Algoritmo de Euclides --en particular del hecho de que la divisibilidad se trasfiere de los sumandos a la suma.)

Por otro lado, una vez que se conjetura que el $MCD(a,b)$ es una combinación lineal entera de $a$ y $b$, la siguiente sutileza es la consideración del conjunto $S$ de combinaciones lineales enteras de $a$ y $b$.

La primera consecuencia de un análisis de $S$ con miras a encontrar cuál podría se el $MCD(a,b)$, es el hecho de que cualquier divisor común de $a$ y $b$ divide a cada uno de los elementos de $S$. (Una consecuencia directa de la transferencia de la divisibilidad de los sumandos a la suma.)

La segunda consecuencia --que es clave para la demostración de Bezout-- es: si existiera en $S$ un divisor común de $a$ y $b$, entonces tendría que ser el mínimo (en valor absoluto), pues de otra manera habría algunos elementos de $S$ no divisibles entre ese divisor común, lo cual entraría en contradicción con la primera consecuencia.

Esta segunda consecuencia es lo que hace plausible la conjetura de que el $MCD(a,b)$ es el elemento mínimo positivo de $S$.

Los saluda

jmd

Imagen de Matías Ezequiel Hernández

Los detalles que mencionas

Los detalles que mencionas simplemente son tan evidente que por ese motivo el autor no hace hincapié. Al menos que el lector sea un neófito, se entiende perfectamente. Al final tu comentario es más extenso que la publicación original.

Imagen de jesus

Bueno, a mi me parece que

Bueno, a mi me parece que perdiste el punto del comentario. Desde el inicio él se da cuenta de lo que mencionas y de hecho lo dice; aclara que la demostración es trivial, pero no al alcance de los novicios (o los neófitos).

El punto del comentario no era hacer una demostración más clara o más corta (evidentemente), era más bien develar las dificultades que ponen a esta prueba fuera del alcance de los novicios.

¡Y creo que lo hace de maravilla!

Saludos