Ecuaciones diofánticas y fracciones continuas. Parte II

Bienvenidos al Escritorio de Enrique. Antes de nada, si queréis descargaros en pdf el contenido de esta entrada podéis pinchar en este enlace post10, y también podéis descargaros un documento que he preparado con el artículo anterior y con este como un solo archivo en este enlace Ecuaciones diofánticas y fraciones continuas. En este artículo vamos a terminar el estudio que iniciamos en el anterior artículo Ecuaciones diofánticas y fracciones continuas. Parte I.

Dada una fracción continua $[a_{1},\; \ldots, a_{n}]$ , nos planteamos aproximarla por lo que se llaman cocientes parciales $c_{1},\; \ldots, c_{n}$ . El primer cociente parcial, $c_{1}$ , se define como $c_{1} = \dfrac{a_{1}}{1}$ . El segundo cociente parcial se define como $c_{2} = a_{1} + \dfrac{1}{a_{2}}$ . El tercer cociente parcial se define como $c_{3} = a_{1} + \dfrac{1}{a_{2} + \dfrac{1}{a_{3}}}.$ Ya te puedes imaginar cómo se definen el resto de cocientes parciales; si expresas $\dfrac{a}{b}$ en forma de fracción continua, cada $c_{i}$ es la fracción continua que resulta de truncar la original en el término i-ésimo. Vamos a mirar más en detalle cómo calcular los cocientes parciales.

Llamamos $c_{1} = \dfrac{a_{1}}{1} = \dfrac{p_{1}}{q_{1}}.$

Llamamos también $c_{2} = a_{1} + \dfrac{1}{a_{2}} = \dfrac{a_{1}a_{2} + 1}{a_{2}} = \dfrac{p_{2}}{q_{2}}.$

Entonces vamos a ver que podemos calcular el siguiente cociente parcial a partir de los dos anteriores. $c_{3} = a_{1} + \dfrac{1}{a_{2} + \dfrac{1}{a_{3}}} = \dfrac{a_{1}a_{2}a_{3} + a_{1} + a_{3}}{a_{2}a_{3} + 1} = \dfrac{a_{3}(a_{1}a_{2} + 1) + a_{1}}{a_{3}a_{2} + 1} = \dfrac{a_{3}p_{2} + p_{1}}{a_{3}q_{2} + q_{1}} = \dfrac{p_{3}}{q_{3}}.$

De hecho, aunque no lo vamos a demostrar (como ejercicio para el lector se deja la demostración por inducción de este hecho, solo falta el paso inductivo), se tiene que si $i \geq 3$ , entonces $c_{i} = \dfrac{p_{i}}{q_{i}} = \dfrac{a_{i}p_{i-1} + p_{i-2}}{a_{i}q_{i-1} + q_{i-2}}.$ Para poder incluir en esta fórmula a $c_{1}$ y a $c_{2}$ se suelen considerar unos nuevos valores $p_{-1} = 0,\; p_{0} = 1,\; q_{-1} = 1,\; q_{0} = 0.$ Ahora puedes comprobar que la fórmula $c_{i} = \dfrac{p_{i}}{q_{i}} = \dfrac{a_{i}p_{i-1} + p_{i-2}}{a_{i}q_{i-1} + q_{i-2}}$ es válida para todo valor $i \geq 0$ . Veamos un ejemplo. Calculemos los cocientes parciales de $\dfrac{121}{21}.$

Para calcular $c_{1}$ necesitamos $a_{1}.$ Como $\dfrac{121}{21} = 5 + \dfrac{16}{21}$ , se tiene que $a_{1} = 5.$ Así, $c_{1} = \dfrac{5}{1} = \dfrac{p_{1}}{q_{1}}.$

Para calcular $c_{2}$ necesitamos $a_{2}$ , que es el cociente de $\dfrac{21}{16}$ , esto es, $\dfrac{21}{16} = 1 + \dfrac{5}{16},$ y $a_{2} = 1$ . Por tanto, $c_{2} = \dfrac{1 \cdot 5 + 1}{1 \cdot 1 + 0} = \dfrac{6}{1} = \dfrac{p_{2}}{q_{2}}.$

Ya menos detalladamente vamos a proseguir con los siguientes cálculos. $\dfrac{16}{5} = 3 + \dfrac{1}{5}$ , luego $a_{3} = 3$ . $c_{3} = \dfrac{3 \cdot 6 + 5}{3 \cdot 1 + 1} = \dfrac{23}{4} = \dfrac{p_{3}}{q_{3}}.$

$a_{4} = 5$ , porque ya hemos llegado al final de la fracción continua. $c_{4} = \dfrac{5 \cdot 23 + 6}{5 \cdot 4 + 1} = \dfrac{121}{15} = \dfrac{p_{4}}{q_{4}}.$ Evidentemente el último cociente parcial es el número racional inicial.

Una observación muy interesante que podemos hacer es que para todo $i \geq 0,\; p_{i}q_{i-1} - p_{i-1}q_{i} = (-1)^{i}$ (es decir, si $i$ es par, entonces el producto es igual a 1, y si es impar, el producto es igual a -1). Esto sí que lo vamos a demostrar, cómo no, por inducción.

Vamos a ver como casos base $i = 0,\; i= 1,\; i = 2$ para familiarizarnos con el modo de proceder en la demostración.

Si $i = 0,\; p_{0}q_{-1} - p_{-1}q_{0} = 1 \cdot 1 - 0 \cdot 0 = 1 = (-1)^{0}$ .

Si $i = 1,\; p_{1}q_{0} - p_{0}q_{1} = a_{1} \cdot 0 - 1 \cdot 1 = -1 = (-1)^{1}$ .

Si $i = 2,\; p_{2}q_{1} - p_{1}q_{2} = (a_{1}a_{2} + 1) \cdot 1 - a_{1}a_{2} = 1 = (-1)^{2}$ .

Ahora vamos a ir con el paso inductivo. Suponemos que el resultado es cierto para los $i$ primeros pasos (es decir, $p_{k}q_{k-1} - p_{k-1}q_{k} = (-1)^{k},\; 0 \leq k \leq i$ es nuestra hipótesis de inducción) y vamos a demostrar que se cumple para el paso $i+1$ .

$p_{i+1}q_{i} - p_{i}q_{i+1} = (-1)^{i+1} = (a_{i+1}p_{i} + p_{i-1})q_{i} - p_{i}(a_{i+1}q_{i} + q_{i-1}) = a_{i+1}p_{i}q_{i} + p_{i-1}q_{i} - a_{i+1}p_{i}q_{i} - p_{i}q_{i-1} = p_{i-1}q_{i} - p_{i}q_{i-1} = (-1)(p_{i}q_{i-1} - p_{i-1}q_{i}).$ Por hipótesis de inducción, el factor $p_{i}q_{i-1} - p_{i-1}q_{i} = (-1)^{i}$ , por lo que $(-1)(p_{i}q_{i-1} - p_{i-1}q_{i}) = (-1)(-1)^{i} = (-1)^{i+1},$ como queríamos probar.

De este resultado se deduce que todo cociente parcial $c_{i} = \dfrac{p_{i}}{q_{i}}$ cumple que $mcd(p_{i},\; q_{i}) = 1$ , porque si $p_{i}q_{i-1} - p_{i-1}q_{i} = (-1)^{i}$ y $d = mcd(p_{i},\; q_{i})$ , se tiene que $d$ divide a $p_{i}q_{i-1} - p_{i-1}q_{i}$ , luego tiene que dividir a $(-1)^{i}$ , pero a este número solo lo dividen 1 y -1. Como $d \geq 1$ , no queda otra que $d = 1$ .

Y después de todo este estudio de fracciones continuas, volvemos a las ecuaciones diofánticas que queremos resolver. Recordemos que una ecuación diofántica es una ecuación de la forma $Ax + By = C$ , donde $A,\; B,\; C$ son números enteros y las soluciones $(x,y)$ son también números enteros. De momento nos vamos a contentar con resolver ecuaciones diofánticas de la forma $ax - by = 1$ . Una primera observación que tenemos que hacer es que solo podrá resolverse si $mcd(a, b) = 1$ por la misma razón del párrafo anterior. Así que ya vamos a asumir esta condición.

Consideremos la fracción continua $[a_{1},\; \ldots , a_{n} ]$ que resulta de $\dfrac{a}{b}$ , y consideremos los cocientes parciales de esta fracción continua $c_{1},\; \ldots, c_{n}$ . Como ya hemos comentado antes, $c_{n} = \dfrac{p_{n}}{q_{n}} = \dfrac{a}{b}.$ Por tanto, utilizando el resultado anterior, $p_{n}q_{n-1} - p_{n-1}q_{n} = aq_{n-1} - bp_{n-1} = (-1)^{n}.$ En el artículo anterior vimos que podíamos elegir que el número de coeficientes de la fracción continua fuera par o impar a voluntad (es decir, podemos elegir que $n$ sea par o impar) haciendo algún pequeño cambio en los últimos coeficientes, así que podemos suponer que $n$ es par. Esto quiere decir que $aq_{n-1} - bp_{n-1} = (-1)^{n} = 1.$ ¡De esta manera hemos conseguido encontrar dos enteros, $q_{n-1},\; p_{n-1}$ , que resuelven nuestra ecuación! Sin embargo, como vamos a ver ahora mismo, hay muchas más soluciones (de hecho, infinitas), y no nos contentamos con una sola solución. Proponemos otra solución $(x, y)$ de nuestra ecuación (es una solución genérica, solo dos valores que satisfarían la igualdad, el propósito es descubrir la forma que tienen). Por tanto tenemos $ax -by = 1$ y $aq_{n-1} - bp_{n-1} = (-1)^{n} = 1.$ Si a la segunda ecuación le restamos la primera obtenemos $a(x - q_{n-1}) - b(y - p_{n-1}) = 0,$ de donde se deduce que $a(x - q_{n-1}) = b(y - p_{n-1}).$ Esto implica que $b$ divide a lo que está a la izquierda de la igualdad. Pero $b$ no puede dividir a $a$ , porque si no, $mcd(a, b)$ sería $b$ . Por tanto, $b$ divide a $x - q_{n-1}.$ De aquí concluimos que, como $b$ es un múltiplo de $x - q_{n-1},$ $x - q_{n-1} = bt,\; t \in \mathbb{Z}$ . Sustituyendo esto en $a(x - q_{n-1}) = b(y - p_{n-1}),$ obtenemos $abt = b(y - p_{n-1}).$ Por tanto, dividiendo por $b$ en ambos lados de la igualdad, $y - p_{n-1} = at.$ Reescribiendo lo obtenido, concluimos que la solución general de la ecuación viene dada por $x = q_{n-1} + tb,\; y = p_{n-1} + ta,$ para cualquier valor $t \in \mathbb{Z}$ (aquí están las infinitas soluciones, dependen del valor $t$ ).

Ahora también sabemos resolver las ecuaciones del tipo $ax - by = -1$ , pues, como al multiplicar por $-1$ en ambos lados de la igualdad esta se mantiene, $-ax + by = a(-x) - b(-y) = a \tilde{x} - b \tilde{y} = 1,$ y esta ecuación ya sabemos resolverla, así que las soluciones de $ax - by = -1$ vendrán dadas por $x = - \tilde{x} = -q_{n-1} - tb = -q_{n-1} + kb,\; y = - \tilde{y} = -p_{n-1} - ta = -p_{n-1} + ka, \; k \in \mathbb{Z}$ (nótese que como $t$ toma cualquier valor entero, al cambiarlo de signo sigue siendo un entero, por lo que podemos cambiarle el signo por «+»; incluso podríamos haber dejado la variable $t$ , pues es solo un símbolo que representa cualquier valor entero).

Ahora vamos a resolver unas ecuaciones más generales, de la forma $ax - by = c$ , donde $mcd(a, b) = 1.$ De nuevo, si $d = mcd(a, b)$ divide a $c$ podríamos reducir la ecuación a la equivalente $\dfrac{a}{d}x - \dfrac{b}{d}y = \dfrac{c}{d}$ , y en este caso los coeficientes de las variables sí tendrían máximo común divisor igual a 1, por lo que ya podemos suponer que el máximo común divisor es 1. Por otra parte, si $mcd(a, b) = d$ y este no divide a $c$ , por lo que hemos comentado anteriormente, no existiría solución para la ecuación. Así que, queriendo resolver nuestra ecuación, vamos a volver a considerar $ax - by = 1$ , que cumplía que $aq_{n-1} - bp_{n-1} = 1.$ Como hemos hecho antes, si multiplicamos por $c$ a ambos lados de la igualdad nos queda $c(aq_{n-1} - bp_{n-1}) = a(cq_{n-1}) - b(cp_{n-1}) = c.$ Así que, procediendo como en el párrafo anterior, tenemos que la solución general de $ax - by = c$ es $x = cq_{n-1} + tb,\; y = cp_{n-1} + ta, \; t \in \mathbb{Z}.$

Para terminar, vamos a ver cómo resolver una ecuación $Ax + By = C$ . Lo primero es comprobar que $d = mcd(A, B)$ divide a $C$ (pues si no no existe solución). Dividimos toda la ecuación por $d$ y nos queda $ax + by = c$ , con $mcd(a, b) = 1$ . Como $1 = aq_{n-1} - bp_{n-1}$ y $ax + by = c = c \cdot 1$ , vamos a sustituir el 1 por $aq_{n-1} - bp_{n-1}.$ Así, $ax + by = c(aq_{n-1} - bp_{n-1}).$ Agrupando las a’s por un lado y las b’s por otro obtenemos $a(x - cq_{n-1}) = b(-y - cp_{n-1}).$ Como hemos visto antes, $b$ tiene que dividir a $x - cq_{n-1},$ luego $bt = x - cq_{n-1},\; t \in \mathbb{Z}.$ Sustituyendo este valor en $a(x - cq_{n-1}) = b(-y - cp_{n-1})$ , tenemos que $a(bt) = b(-y - cp_{n-1}).$ De esta forma conseguimos $at = (-y - cp_{n-1}).$ Por tanto, la solución general de la ecuación es $x = cq_{n-1} + tb,\; y = -cp_{n-1} - ta,\; t \in \mathbb{Z}.$

¡Voilà! ¡Ya sabemos cómo resolver ecuaciones diofánticas! No hay más que seguir los siguientes pasos:

Comprobar que $d = mcd(A, B)$ divide a $C$ y reducir la ecuación dividiéndola por $d$ a la ecuación $ax + by = c.$
Calcular los cocientes parciales $c_{i}$ de la fracción continua de $\dfrac{a}{b}$ (teniendo cuidado de que haya un número par de cocientes $a_{i}$ ). Realmente solo nos interesa $c_{n-1} = \dfrac{p_{n-1}}{q_{n-1}}.$
Las soluciones de la ecuación $ax + by = c$ (o de la ecuación inicial $Ax + By = C$ ) vienen dadas por $x = cq_{n-1} + tb,\; y = -cp_{n-1} - ta,\; t \in \mathbb{Z}.$

Veamos un ejemplo. Queremos resolver la ecuación diofántica $130x + 112y = 14$ .

Lo primero que hacemos es calcular $mcd(130, 112)$ . Por el algoritmo de Euclides, se comprueba que $mcd(130, 112) = 2$ (como ejercicio comprueba que ese es el máximo común divisor). Además, 2 divide a 14, por lo que reducimos la ecuación a $65x + 56y = 7.$

Ahora calculamos la fracción continua de $\dfrac{65}{56}$ (como ejercicio calcúlala como vimos en el artículo anterior) y la expresamos con una cantidad par de coeficientes de la forma $[1, 6, 4, 2]$ ( $n = 4$ ). Calculamos los cocientes parciales (haz las cuentas si lo necesitas) y nos quedan $c_{1} = \dfrac{1}{1},\; c_{2} = \dfrac{7}{6},\; c_{3} = \dfrac{29}{25} = \dfrac{p_{3}}{q_{3}} = \dfrac{p_{n-1}}{q_{n-1}},\; c_{4} = \dfrac{65}{56}.$

Las soluciones de nuestra ecuación son $x = 7 \cdot 25 + 56t = 175 + 56t,\; y = -7 \cdot 29 - 65t = - 203 - 65t,\; t \in \mathbb{Z}$ . Esto significa que si damos valores a $t$ vamos a obtener distintas soluciones particulares de la ecuación. Por ejemplo, con $t = 0$ , la solución es $x = 175,\; y = -203.$ Podemos comprobar que no nos hemos equivocado directamente sustituyendo en la ecuación estos resultados: $65 \cdot 175 + 56 \cdot (-203) = 11375 - 11368 = 7.$ Se puede jugar con los distintos valores que se obtienen al variar los valores de $t$ .

Hay una cosa más. En el artículo anterior comenzamos introduciendo las ecuaciones diofánticas con un ejemplo en el que teníamos que resolver la ecuación $8x + 5y = 81$ pero teníamos la restricción de que $x,\; y \geq 0.$ Obviamente, cuando añadimos restricciones a las ecuaciones, perdemos soluciones (incluso puede que nos quedemos sin soluciones). Para resolver esta ecuación tenemos que conseguir la solución general como si no tuviéramos restricciones y luego jugar con los valores de $t$ hasta encontrar un valor que haga que $x,\; y \geq 0.$ ¿Te atreves a intentarlo?

Espero que os haya resultado interesante. Si es así, dejádmelo en los comentarios y compartidlo con familiares, amigos y vecinos del barrio. ¡Hasta la próxima!

Autor: Enrique Ferres

Soy matemático por la Universidad Complutense de Madrid especializado en Ciencias de la Computación, PDI en U-tad y estudiante PhD en Didáctica de las Matemáticas en la UCM. Miembro de Scenio. También divulgo en Twitter: @enrique_ferres Lee todas las entradas de Enrique Ferres

Deja una respuesta Cancelar la respuesta

Introduce aquí tu comentario...

Introduce tus datos o haz clic en un icono para iniciar sesión:

Correo electrónico (obligatorio) (La dirección no se hará pública)

Nombre (obligatorio)

Web

Estás comentando usando tu cuenta de WordPress.com. ( Salir / Cambiar )

Estás comentando usando tu cuenta de Facebook. ( Salir / Cambiar )

Cancelar

Conectando a %s

Compártelo:

Me gusta esto:

Relacionado

Autor: Enrique Ferres

Deja una respuesta Cancelar la respuesta