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:

  1. 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.
  2. 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}}.
  3. 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. Como divulgador soy miembro de Scenio y he impartido conferencias en la UCM para el proyecto La Conciencia Social es la Vacuna y en la UCJC. He sido mentor durante dos años en el proyecto PiMat de integración en la universidad y un año community manager del proyecto.

Responder

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

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s