Ecuaciones diofánticas


Se llama ecuación diofántica a cualquier ecuación algebraica con coeficientes enteros, de la que nos interesa exclusivamente las soluciones que tenga dentro del conjunto de los números enteros.

 

El origen del término diofántico hay que buscarlo en el matemático Diofanto de Alejandría, que vivió en el siglo III, y que se ocupó de este tipo de ecuaciones.

 

Como base previa al tema es importante recordar algunos conceptos de teoría de números, iniciaremos con el tema del Máximo Común Divisor.

 

Todos conocemos el método que se nos enseña en el colegio para ello: Descomponemos en factores primos los dos números y tomamos los factores comunes a ambos con el menor exponente con el que aparezcan.

 

Aunque es un método bastante útil y sencillo para conseguirlo que queremos tiene un evidente problema: si los números son muy grandes, o si sus factores primos lo son, la situación se puede complicar ya que el cálculo de la descomposición se torna bastante tedioso.

Por ello es interesante tener a mano otro método para casos en los que el procedimiento inicial se complique. Para ello utilizaremos el algoritmo de Euclides.

 

Algoritmo de Euclides

Para calcular el máximo común divisor de dos números enteros positivos a y b, dividimos el mayor, que puede ser a, entre el menor, supongamos b. Esta división nos proporcionará un cociente y un resto. Si aplicamos repetidamente el algoritmo del cociente, se obtiene:

Entonces, el máximo común divisor entre a y b es el último resto distinto de cero que obtengamos en el procedimiento anterior.

 

Ejemplo:

Determinar el mcd(721, 448)

Aplicando el algoritmo de Euclides, tenemos:

Ejemplo:

Determinar el mcd(12378, 3054)

Identidad de Bézout

La identidad de Bézout, es un teorema elemental de Teoría de números, siendo a y b dos enteros distintos de cero, y siendo d su máximo común denominador, existen dos enteros x, y tales que:

Simbólicamente tenemos que:

Propiedades

  • Si a, b son enteros, no nulos, tal que mcd(a, b) = d, y sea c un entero cualquiera, entonces:
  •  Si d = mcd(a, b) entonces d es el menor entero de la forma ax + by con x, y enteros.
  • Si d = mcd(a, b) entonces mcd(ma, mb) = md para todo m > 0
  • Si d = mcd(a, b) entonces mcd(a/d, b/d) = 1
  • Si mcd(a, b) = 1 y a|c y b|c entonces ab|c
  • Si mcd(a, b) = 1 y a|bc entonces a|c
  • Dos enteros a y b son primos entre sí (coprimos) sí y sólo sí

Ejemplo:

1.      Dados (150, 39). Hallar x, y.

Aplicando el algoritmo de Euclides

Luego aplicamos el Lema de Bézout

Ecuaciones diofánticas lineales

El problema anterior, se escribe algebraicamente de la siguiente manera:

 

En  la  película  La  Jungla  de  Cristal  3,  para  desactivar  una  bomba,  se propone el siguiente  problema  que  consiste  en  colocar sobre una báscula controlada por computadora exactamente  4  galones  de  agua disponiendo únicamente de una garrafa de 5 galones y otra de 3 galones. ¿Cómo lo  pueden conseguir? 

 

Este problema lo que plantea es cuántas veces se debe llenar o vaciar la garrafa de 5 galones y/o llenar o vaciar la garrafa de 3 galones, para poder tener exactamente 4 galones.

 

Este problema nos genera lo que llamamos una ecuación diofántica

 

Son ecuaciones de la forma ax + by = c con coeficientes enteros, y de las que solamente nos interesan sus soluciones enteras.

 

El problema anterior, se escribe algebraicamente de la siguiente manera:

Una ecuación diofántica lineal es una ecuación de la forma:

Teorema:

Una ecuación lineal diofántica de la forma ax +by = n tiene solución entera x0, y0 si y solo si el máximo común divisor de a y b es divisor de n.

 

Además si llamamos d al mcd(a, b) se tiene que una solución particular de dicha ecuación puede obtenerse de la siguiente forma:

Los valores obtenidos en el teorema anterior son una solución particular de la ecuación.

Para obtener la solución general de una ecuación diofántica lineal enunciamos el siguiente teorema.

 

Teorema:

Si x0, y0  son números enteros y constituyen una solución particular de la ecuación

Entonces todas la soluciones enteras xy de la misma, son de la forma:

La solución de una ecuación diofántica es una consecuencia del algoritmo de Euclides y de la identidad de Bézout.

 

Ejemplo:

Encontrar la solución de la siguiente ecuación diofántica:

Algoritmo de Euclides

Aplicando la identidad de Bézout

Las soluciones particulares son

Si la ecuación tiene solución, entonces tiene infinitas soluciones y son de la forma:

Ejemplo:

Encontrar la solución de la siguiente ecuación diofántica:

Algoritmo de Euclides

Aplicando la identidad de Bézout

Las soluciones particulares son

La solución general está dada por:

Ejemplo:

La patrulla de la policía municipal de una ciudad ha impuesto sanciones de  tráfico por  valor  de  3.700 U.M. (Unidades Monetarias).  Si  la  sanción  por  exceso  de  velocidad  es  de  600 U.M.  y  la  sanción  por  aparcamiento indebido es de 250 U.M, ¿cuántas  sanciones ha impuesto de cada uno de los  dos tipos?

 

Solución:

Solución Particular

Solución General

Para valores mayores que 0

 

Verificamos para x

Luego tenemos que para k=30 los valores obtenidos en la solución general son: x = 2 y=10.  Por lo tanto se sancionaron 2 excesos de velocidad y 10 faltas de aparcamiento.