Resolución de ecuaciones diofánticas

Las ecuaciones diofánticas contienen 2 incógnitas en una sola ecuación y están generalmente expresadas en la forma ax + by = c

Cuando hay dos incógnitas, tal vez nos resulte más familiar un sistema de dos ecuaciones como nos enseñaron en primaria, por ejemplo:

  • 2x + 2 = 6y
  • 4y + 2 = x + 6

Ahora bien, una ecuación diofántica también nos resulta familiar expresada en la forma ax + by – c = 0 , pues se trata de la ecuación de una recta. Al tratarse de una recta sus soluciones serán infinitas, si tiene solución.

Aunque el conjunto de puntos de una recta está en R, al igual que hemos hecho con las congruencias contemplaremos sólo las soluciones en Z. En este conjunto, hay un teorema debido al matemático indio Brahmagupta, que nos dice que la condición necesaria y suficiente para que la ecuación diofántica ax + by = c tenga solución es que d = mcd(a, b) | c En este caso, si (x1, y1) es una solución, todas las demás soluciones se obtienen mediante las expresiones:

  • x = x1 + (b / d) * k
  • y = y1 – (a / d) * k

Este teorema nos resulta familiar con las ecuaciones de congruencia; vimos que ax ≡ b (mod m) tendrá solución si d | b En los dos artículos anteriores, 1 y 2, vimos también que solucionar ecuaciones de congruencia lineal se reduce a resolver congruencias donde el coeficiente de la x, a, y el módulo m son primos entre si. El procedimiento es el mismo para las ecuaciones diofánticas. Por el teorema de Bezout sabemos que existen coeficientes s y t tales que:

a*s + b * t = d

Si e = c / d y multiplicamos ambos lados por e tendremos:

  • x1 = s * e
  • y1 = t * e

Vamos a resolver 23x – 4y = 11 Mediante el algoritmo de Euclides tenemos:

  • 23 = -4 * (-5) + 3 ⇒ 2 = 23 – 4 * 5
  • -4 = 3 * (-2) + 2 ⇒ 2 = -4 + 3 * 2
  • 3 = 2 * 1 + 1 ⇒ 1 = 3 -2 * 1

Obtenemos mcd(23, -4) = 1 Usemos el algoritmo extendido de Euclides para hallar un s y t:

1 = 3 – 2 * 1 = 3 – (-4 + 3*2) * 1 = 3 + 4 – 3 * 2 = 4 – 3 * 1 = 4 – (23 – 4 * 5) * 1 = 4 -23 * 1 + 4 * 5 = 23 * (-1) + 4 * 6

Sabiendo s y t tenemos tendremos x1 e y1:

23 * (-1) – 4 * (-6) = 1

23 * (-11) – 4 * (-66) = 11

  • x1 = -11
  • y1 = -66

Reemplacemos para encontrar las expresiones que dan todas las soluciones:

  • x = -11 + (-4 / 1) * k = -11 – 4k
  • y = -66 – (-23 / 1) * k = -66 – 23k

Siguiendo con las familiaridades, podemos ver que estas expresiones para x e y coinciden con la forma paramétrica de la ecuación de la recta.

Si usamos fracciones continuas para resolver la ecuación diofántica llegaremos a este resultado:

  • x1 ⇒ x = 1 – 4k
  • y1 ⇒ y = 3 – 23k

Cómo resolver ecuaciones diofánticas mediante fracciones continuas puede encontrarse en Google, lo que quiero destacar es que aparentemente hemos llegado a un resultado diferente pero no es así. Veamos que ambas soluciones representan la misma recta:

23x - 4y - 11 = 0La segunda solución nos conduce a la misma ecuación 23x – 4y – 11 = 0

23x -4y - 11 = 0El algoritmo extendido de Euclides nos da un par s y t y cualquier otro par nos dará soluciones que son la misma recta. El resto de pares nos los da la expresión:

1 = 23*( -1 – (-4) * h) + (-4)*(-6 + 23 * h) ∀ h ∈ Z

Para h = 1 y multiplicando luego por 11:

  • x1 = 33 ⇒ x = 33 – 4k
  • y1 = 66 ⇒ y = 187 – 23k

Podemos ver que se trata de la misma recta:

23x - 4y - 11 = 0En el artículo anterior resolvimos la congruencia 12x ≡ 15 (mod 21) y podemos ver que resolver esta ecuación equivale a encontrar todos los enteros x que satisfagan la ecuación diofántica 12x + 21y = 15. Vamos a resolverla:

12x + 21y = 15 equivale a 4x + 7y = 5

Bezout: 4s + 7t = 1

Podemos ver que s = 2 y t = -1 satisfacen la ecuación. Por lo tanto:

4(2 * 5) + 7(-1 * 5) = 5

  • x1 = 10 ⇒ x = 10 + 7k
  • y1 = -5 ⇒ y = -5 – 4k

La solución para x son todos los múltiplos de 7 + 10 En “términos” de congruencias diríamos que estamos en Z7 y que 10 pertenece a la clase de equivalencia [3] Sabemos que el mcd es 3, por lo tanto los 3 primeros residuos serán las soluciones: 3, 10 y 17

También vemos que el conjunto de soluciones k = {-1, 0, 1} dan las soluciones de la ecuación de congruencia 12x ≡ 15 (mod 21) x = {3, 10, 17}  Gracias a lo que sabemos de congruencias podemos suponer que otra forma paramétrica correcta para x es:

x = 3 + 7k Por lo tanto x1 = 3. Para encontrar y1 reemplazamos:

4*(3) + 7y = 5 ⇒ y1 = -1 ⇒ y = -1 – 4k Así que otra forma paramétrica equivalente es:

  • x = 3 + 7k
  • y = -1 – 4k

Si desarrollamos como hemos visto anteriormente veremos que ambas formas paramétricas conducen a la misma ecuación de la recta: -4x -7y + 5 = 0

2 pensamientos en “Resolución de ecuaciones diofánticas

  1. Pingback: Programa para resolver ecuaciones diofánticas | Víctor Iglesias

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.