Usuario:AlexFdez01/Taller

Única ecuación lineal diofantica

Definición

Definimos una ecuación lineal diofantica como ax + by = c donde $a,b,c\in \mathbb {Z}$ y $a,b\neq 0$, además los pares de soluciones (x,y) deberán cumplir $x,y\in \mathbb {Z}$.

Se pueden expresar con congruencias:

$ax\equiv c{\pmod {b}}$

$by\equiv c{\pmod {a}}$

También se cumple:

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

Esto quiere decir que en la ecuación es condición necesaria y suficiente que c sea divisible por el 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:

Utilizaremos la reducción al absurdo para demostrarlo. Supongamos que existe un único par que sea solución a la ecuación ax + by = c , este par será denominado $(x_{0},y_{0})$.

Formamos una combinación lineal $(x_{0}-bm,y_{0}+am)$ donde m es un entero arbitrario.

Sustituimos en la ecuación x e y por esa combinación lineal:

$a(x_{0}-bm)+b(y_{0}+am)=c$

$ax_{0}-abm+by_{0}+abm=c$

$ax_{0}+by_{0}=c$

Sabiendo esto podemos decir que sin importar el m entero que escojamos 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 de que $(x_{0},y_{0})$ era un par de soluciones únicas llevándonos 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 hemos utilizado será similar para obtener todas las soluciones de la ecuación solo teniendo una solución.

Resolución

Encontrar todas las soluciones a la ecuación lineal diofantica ax + by = c:

El primer paso será averiguar si existen soluciones y de paso intentar simplificar la ecuación, para ello averiguamos el $mcd(|a|,|b|)$ y haremos lo siguiente:

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

Si resulta que c dividido de $mcd(|a|,|b|)$ no es un número entero la ecuación no tendrá solución como se explica en la definición.

El siguiente paso será obtener $(x_{0},y_{0})$ que sean un par solución de la ecuación, en ocasiones se puede obtener este resultado de manera sencillo, pero en otras será necesario utilizar un método sistemático usando el Algoritmo de Euclides.

Y en último lugar usando el par solución obtenido anteriormente podemos generalizar el par solución a un infinito par de soluciones usando 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)$, $\forall m\in \mathbb {Z}$

Ejemplo

Encontrar todas las soluciones a la ecuación lineal diofantica 93x - 81y = 432:

Primer paso:

Aplicaremos el Algoritmo de Euclides para encontrar el mcd(93,81).

93(1) - 81(1) = 12

81(1) - 12(6) = 9

12(1) - 9(1) = 3

9(1) - 3(3) = 0

Obtenemos que el mcd(93,81) = 3

Por tanto, tiene soluciones y simplificamos a 31x + 27y = 144.

Volvemos 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 nuestro objetivo será encontrar una expresión tal que 31($\alpha$) + 27($\beta$) = 1, para ello tendremos que poner 4 y 3 en función de 31 y 27.

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

27(7) - 31(6) = 3

Ahora sustituimos en el final:

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

31(7) - 27(8) = 1

Habiendo obtenido la expresión que buscamos solo tenemos que multiplicar 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),\forall m\in \mathbb {Z}$

Sistema de ecuaciones lineales diofanticas

Definición

Un sistema de ecuaciones lineales diofanticas se definiría como Ax = b de manera similar a un sistema de ecuaciones lineales clásico donde $a_{ij},b_{i}\in \mathbb {Z}$ y las soluciones deben ser números enteros. En el caso de la ecuación diofántica buscaremos conseguir una única ecuación lineal diofantica usando sustitución y otros métodos comunes de la resolución de sistemas lineales, una vez que tengamos resuelta esta ecuación única aplicaremos las igualdades obtenidas para obtener el resultado de las demás incógnitas.

Ejemplo

Resolver el siguiente sistema de ecuaciones diofanticas:

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

Despejamos z en la primera ecuación:

$12-2x-y=z$

Y sustituimos en la segunda:

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

$-x-y=-15$

$x+y=15$

Encontramos una solución:

$(x_{0},y_{0})=(15,0)$

Y la general:

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

Obtenemos z usando la igualdad obtenida anteriormente:

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

$z=-18+m$

Y obtenemos la solución para todo el sistema de ecuaciones.

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