Sistema de ecuaciones diofánticas lineales

Un sistema de ecuaciones diofánticas lineales se define como $A\overrightarrow{x}=\overrightarrow{b}$ de manera similar a un sistema de ecuaciones lineales clásico donde $a_{ij},b_i,x_i\in \mathbb{Z}$. En el caso de la ecuación diofántica se busca conseguir una única ecuación diofántica lineal usando sustitución y otros métodos comunes de la resolución de sistemas de ecuaciones lineales. Una vez se haya encontrado la solución de esta ecuación única se aplican las igualdades obtenidas para obtener el resultado de las demás incógnitas. Para que la ecuación tenga soluciones debe cumplir las condiciones necesarias de cualquier sistema de ecuaciones lineales y además $mcd(a_{i1},...,a_{ij})\mid b_i$ (El máximo común divisor de cada fila debe poder dividir a $b_i$ de su correspondiente fila).

Una única ecuación diofántica lineal

Definición

Una ecuación diofántica lineal se define como $ax+by=c$ donde $a,b,c\in \mathbb{Z}$ y $a,b\ne 0$, y los pares de soluciones $(x,y)$ deben cumplir: $x,y\in \mathbb{Z}$.

Estas ecuaciones se pueden expresar con congruencias:

$ax\equiv c(\mathrm{mod}b)$

$by\equiv c(\mathrm{mod}a)$

También se cumple que:

$(\mathrm{\exists }x,y\{ax+by=c\wedge x,y\in \mathbb{Z}\})\iff (mcd(|a|,|b|)\mid c)$

Esto define que en la ecuación es condición necesaria y suficiente que c sea divisible por $mcd(|a|,|b|)$ para que la ecuación tenga soluciones y además el número de pares de soluciones es infinito.

Demostración que el número de soluciones es infinito si existe al menos una solución

Se puede demostrar esta afirmación mediante reducción al absurdo: suponemos que existe un único par que sea solución a la ecuación $ax+by=c$ , este par será denominado $(x_0,y_0)$.

Se forma una combinación lineal $(x_0-bm,y_0+am)$ donde m es un entero arbitrario.

Sabiendo que $(x_0,y_0)$ es un par solución, se tiene la siguiente igualdad: $a{x}_0+b{y}_0=c$. Se quiere averiguar si la siguiente igualdad es verdadera:

$a(x_0-bm)+b(y_0+am)=a{x}_0+b{y}_0$

$a{x}_0-abm+b{y}_0+abm=a{x}_0+b{y}_0$

$a{x}_0+b{y}_0=a{x}_0+b{y}_0$

Con esto se puede concluir que la igualdad es verdadera y por lo tanto:

$a(x_0-bm)+b(y_0+am)=c,\mathrm{\forall }m\in \mathbb{Z}$,

Sabiendo esto se puede afirmar que para cualquier m entero que se escoja en la combinación lineal, será solución de la ecuación haciendo que se produzca una contradicción con la hipótesis de partida, llevando por reducción al absurdo a que el número de soluciones es infinita si existe al menos una solución.

Además, la demostración que se ha empleado será similar para obtener todas las soluciones de la ecuación solo teniendo un par solución.

Resolución

Encontrar todas las soluciones a la ecuación diofántica lineal $ax+by=c$.

El primer paso es averiguar si existen soluciones y a la vez intentar simplificar la ecuación, para ello se averigua el $mcd(|a|,|b|)$ y se realiza lo siguiente:

$\frac{ax}{mcd(|a|,|b|)}+\frac{by}{mcd(|a|,|b|)}=\frac{c}{mcd(|a|,|b|)}$

Si resulta que $\frac{c}{mcd(|a|,|b|)}$ no es un número entero la ecuación no tendrá solución como se especifica en la definición. El siguiente paso se trata de obtener que $(x_0,y_0)$ sean un par solución de la ecuación. En ocasiones se puede obtener este resultado de manera sencilla, pero en otras será necesario utilizar un método sistemático utilizando el Algoritmo de Euclides.

Y en último lugar, usando el par solución obtenido anteriormente se puede generalizar el par solución a un infinito par de soluciones utilizando el mismo procedimiento que en la demostración en la definición.

$(x,y)=(x_0-bm,y_0+am)$ o  $(x_0+bm,y_0-am)$, $\mathrm{\forall }m\in \mathbb{Z}$

Corolarios

Corolario 1

Si $c|ab$ y $(c,a)=1$ , entonces $c|b$

Demostración

Definimos que $c|ab$ y $(c,a)=1$. Como $(c,a)=1$ existen enteros $x$ e $y$ tal que: $cx+ay=1$.

Multiplicando ambos lados de la ecuación por $b$ se obtiene: $bcx+bay=b$.

Como $c|bx$ y $c|bay$ (como $c|ab$), entonces se debe obtener que $c|b$ tal como se quería demostrar.

Corolario 2

Si $(a,b)=d$, $c|a$ y $c|b$ entonces $c|d$

Demostración

Como $(a,b)=d$ existen enteros $x$ e $y$ tal que: $ax+by=d$. Si $c|a$ y $c|b$ entonces: $c|(ax+by)$.

Como $ax+by=d$ se debe tener que $c|d$

Corolario 3

Si $(a,b)=1$, $a|m$, y $b|m$ entonces $ab|m$

Demostración

Como $a|m$ y $b|m$, existen enteros $q_1$ y $q_2$ tal que: $a{q}_1=m$ y $b{q}_2=m$. Por consecuencia: $a{q}_1=b{q}_2$.

Tenga en cuenta que $a|b{q}_2$ y $(a,b)=1$. Por el corolario 1, se puede observar que $a|q_2$. Por lo tanto existe algún entero $r$ tal que: $ar=q_2$.

Por sustitución de $q_2$ se obtiene:

$ar=\frac{m}{b}$

$abr=m$

Como $ab|abr$, se deduce que $ab|m$

Ejemplos

Ecuación lineal diofántica

Encontrar todas las soluciones a la ecuación diofántica lineal $93x-81y=432$:

Primer paso:

Se aplica el Algoritmo de Euclides para encontrar $mcd(93,81)$.

$93(1)-81(1)=12$

$81(1)-12(6)=9$

$12(1)-9(1)=3$

$9(1)-3(3)=0$

Se obtiene que $mcd(93,81)=3$

Por tanto, la ecuación tiene soluciones y podemos simplificar dividiendo la ecuación original entre 3, con lo que se obtiene : $31x+27y=144$

Se vuelve a aplicar el Algoritmo de Euclides junto a la Identidad de Bézout para encontrar un par solución.

$31(1)-27(1)=4$

$27(1)-4(6)=3$

$4(1)-3(1)=1$

Ahora el objetivo será encontrar una expresión tal que $31(\alpha )+27(\beta )=1$. Para ello se expresa 4 y 3 en función de 31 y 27.

$27(1)-(6)(31(1)-27(1))=3$

$27(7)-31(6)=3$

Ahora se sustituye en el final:

$31(1)-27(1)-(27(7)-31(6))=1$

$31(7)+27(-8)=1$

$\alpha =7,\beta =-8$

Una vez se obtiene la expresión que se estaba buscando se multiplican los dos lados de la igualdad por 144

$144(31(7)-27(8))=144$

$31(1008)-27(1152)=144$

$(x_0,y_0)=(1008,1152)$

Y la solución general sería:

$(x,y)=(1008+27m,1152+31m),\mathrm{\forall }m\in \mathbb{Z}$

Sistema de ecuaciones lineales diofánticas

Resolver el siguiente sistema de ecuaciones diofánticas:

$\{\begin{array}{c}2x+y+z=12\\ 3x+y+2z=9\end{array}$

Se despeja $z$ en la primera ecuación:

$12-2x-y=z$

Y se sustituye en la segunda:

$3x+y+2(12-2x-y)=9$

$-x-y=-15$

$x+y=15$

Una solución particular:

$(x_0,y_0)=(15,0)$

Y la general:

$(x,y)=(15-m,m),\mathrm{\forall }m\in \mathbb{Z}$

Se obtiene $z$ usando la igualdad obtenida anteriormente:

$z=12-2(15-m)-m$

$z=-18+m$

Y finalmente se obtiene la solución para todo el sistema de ecuaciones diofánticas lineal:

$(x.y,z)=(15-m,m,m-18),\mathrm{\forall }m\in \mathbb{Z}$