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, 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 (x₁, y₁) es una solución, todas las demás soluciones se obtienen mediante las expresiones:

§  x = x₁ + (b / d) * k

§  y = y₁ – (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. Es igual que también 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:

§  x₁ = s * e

§  y₁ = 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 x₁ e y₁:

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

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

§  x₁ = -11

§  y₁ = -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:

§  x₁ ⇒ x = 1 – 4k

§  y₁ ⇒ y = 3 – 23k

 Veamos que ambas soluciones representan la misma recta:

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

El 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:

§  x₁ = 33 ⇒ x = 33 – 4k

§  y₁ = 66 ⇒ y = 187 – 23k

Podemos ver que se trata de la misma recta:

Vamos a resolver 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

§  x₁ = 10 ⇒ x = 10 + 7k

§  y₁ = -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 Z₇ 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 x₁ = 3. Para encontrar y₁ reemplazamos:

4*(3) + 7y = 5 ⇒ y₁ = -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