Combinación lineal de enteros.

Un teorema importante que relaciona las combinaciones lineales con el máxicomo común divisor es el teorema de Bezout. Visiten la liga anterior si no lo conocen.

En este post, voy a ver algunas consecuencias de este teorema que pueden ser de interés para todos.

Me gustaría que el lector de este post, se tomara unos minutos en intentar los problemas que vayamos planteando y luego continúe con la lectura.

Problema1. Encuentra, si existen, enteros $x$ e $y$ tales que se satisface la siguiente identidad: $$15x + 6y = 2009$$

 Este problema puede llegar a ser latoso, puede hacer que pasemos mucho tiempo sin encontrar $x$ e $y$, si no tienen cuidado, podrían incluso olvidar que $x$ e $y$ pueden ser negativos o incluso cero.

Bueno, pues si ya intentaron un buen rato, se darán cuenta que no es nada fácil. Pero intentemos resolver unos casos posiblemente más fáciles.

Problema 2. Para cada uno de los siguientes casos, encuentra, si existen, enteros $x$ e $y$ tales que se da la igualdad.

• a) $15x + 6y = 0$
• b) $15x + 6y = 3$
• c) $15x + 6y = 2$
• d) $15x + 6y = 4$
• e) $15x + 6y = 6$
• f) $15x + 6y = 9$
• g) $15x + 6y = 5$

Notemos que el inciso a) es muy fácil. Bueno, si olvidaron que cero es entero se les pudo complicar un poco. Pero con $x=-6$ y $y=15$ funciona. Sin embargo, trivialmente $x=y=0$ funciona.

Por otro lado, el inciso b) se puede con $x=1$ e $y=-2$.

El inciso (c) parece que no se puede...¿verdad?

Luego, el inciso (d) también se ve difícil de encontrar.

El inciso (e), es muy obvio, bueno, si no hemos olvidado que $x$ puede ser cero.

El (f), con $x=1$ e $y=-1$

Y el (g)... otra vez nos mete en problemas.

Hagamos un recuento. En el problema se planteó encontrar $x$ e $y$ tales que $15x+6y=C$ para algunos valores de $ C$. Además, hemos visto que pudimos resolver el problema cuando $ C$ es igual a 0, 3, 6 y 9. Esto último es interesante pues son todos múltiplos de 3. Luego, también vimos que los casos en que $ C$ no es múltiplo de 3 parecen ser el difíciles. Pues..., tal vez esto se deba a que, en realidad, no existen los números. Es decir, el siguiente problema.

Problema 3. Sea  $ C$ un número que no es múltiplo de 3. Demuestra que no es posible encontrar $x$ e $y$ tales que $15x+6y=C$.

Este ejercicio nos hace ver claramente que no hay solución para el problema 1.

Bueno, Ok. Si $ C$ no es múltiplo de 3 no se puede. Pero, ¿y si es múltiplo de 3?¿siempre se puede?. Ya vimos que con $ C$ igual a 0,3, 6, y 9 se puede, ¿cómo probamos que para todos los múltiplos de 3 sí se puede?

Pues es muy fácil, sea $ 3n$ un múltiplo de 3. Luego, consideremos la expresión $15\cdot (1) + 6 \cdot (-2) = 3$. Basta con multiplicar esta expresión por $ n$ para obtener lo deseado:

$$15\cdot (n) + 6 \cdot (-2n) = 3n$$

Es decir, para cualquier múltiplo de 3 ($ 3n$) sí se pudo encontrar $ x$ ( = $ n$) e $y$ ( = $ -2n$) tales que $15x+6y=3n$.

Generalización

Tratemos ahora de entender, qué está pasando en general. Es decir, si yo tengo dos números enteros $ a$ y $ b$ ¿para qué números $ C$ existirán $x$ e $y$ enteros tales que $ax+by=C$.

Bueno, la primera pista la obtenemos con la identidad de Bezout, que nos dice que para $C = (a,b)$ (el máximo común divisor de $ a$ y $ b$) sí existe solución.

Como vimos en el ejemplo, al multiplicar por $ n$, también se pueden encontrar $ x$ e $ y$ para cualquier múltiplo de $(a,b)$.

Entonces, podemos conjeturar que los múltiplos de $(a,b)$ son los únicos se pueden.

¡Eso es un buen ejercicio!, demuestren lo siguiente:

Teorema. Consideremos $ a$ y $ b$ enteros, no ambos cero. Definamos el conjunto $ T =\{ax+by | x,y \textrm{ son enteros}\}$ . Entonces,  $ T$ es el conjunto de múltiplos de $(a,b)$.

Esto es un resultado muy interesante pues, ahora ya podemos decir con facilidad cuándo se pueden encontrar $ x$ e $ y$. Aunque, tal vez, no sepamos cómo encontrarlas. Pero el cómo encontrarlas será para otro post.

Los dejo con la siguiente pregunta sobre el teorema antes mencionado.

¿Cuándo sucede que $\mathbb{Z} = T$ ?

o bien,

¿Qué tienen que satisfacer $ a$ y $ b$ para que $\mathbb{Z} = T$?

P.D Resolver esta última pregunta les podría ayudar a resolver el siguiente problema: Quita y pon canicas.