www.matematicas.net

LO DIJO...

George Cantor  
 
La esencia de las matemáticas reside en su libertad.
 
www.matematicas.net - Nuestros Temas ~ Ecuaciones diofánticas
.: Nuestros Temas :.
Ecuaciones diofánticas elementales

1  Introducción El conjunto de los números enteros

Z = { ..., -3, -2, -1, 0, 1, 2, 3, ... }
(1)

con la suma y el producto usuales tiene una estructura algebraica llamada dominio de integridad.

Definición 1 [Dominio de integridad] Un conjunto no vacío X , dotado de dos leyes de composición interna: +,·, es un dominio de integridad si cumple las condiciones siguientes:

  1. X es un grupo abeliano para la suma +, con neutro que simbolizamos mediante 0.
  2. El producto · es asociativo y conmutativo, existiendo además neutro para dicho producto, el cual se simboliza por 1.
  3. El producto es distributivo respecto a la suma por la derecha y por la izquierda.
  4. La expresión a ·b = 0, con a y b elementos de X, implica que a = 0, b = 0 o ambos son nulos.

    En los dominios de integridad no está  asegurada para todos los elementos la existencia de simétrico multiplicativo (inverso). Es decir, si u pertenece a un dominio de integridad X, la ecuación u ·x = 1 no tiene por qué tener solución. Esta particularidad de los dominios de integridad conduce al establecimiento del concepto de divisibilidad. En efecto, siguiendo un esquema paralelo a la ecuación x ·y = 1 obtenemos otras de la forma a ·x = c. La solución de esta última es posible sólo si a es factor de c, es decir, si a es divisor de c.

Ejemplo 1 Consideremos la siguiente ecuación en Z

2 x + 3 = 0

Añadiendo a ambos miembros el opuesto de 3, tenemos

2 x + 3+(-3) = 0+(-3)
2 x+0 = -3
2 x = -3

Como 2 no es factor de -3, concluimos que esta ecuación no tiene solución en Z.

2  Ecuaciones diofánticas

    Ecuación diofántica es toda aquella ecuación en la que tanto sus coeficientes como sus soluciones son enteras. Podemos clasificarlas según el número de incógnitas y el grado de éstas. Así las ecuaciones diofánticas en una incógnita y de primer grado son todas aquellas en las que se buscan soluciones enteras y pueden llevarse a la forma:

a x+b = 0,     a y b enteros.
(2)

    Generalizando, las ecuaciones diofánticas de grado n con una incógnita son las que se resuelven en Z y mediante transformaciones equivalentes quedan

an xn+an-1-1 xn-1-1 + ¼+ a1 x + a0 = 0,
(3)

donde cada ai para i = 0,1,¼, n es entero y an no nulo. Un valor entero u es solución de 3 si y sólo si

an un+an-1-1 un-1-1 + ¼+ a1 u + a0 = 0,
(4)

por lo que pasando el término independiente al otro miembro tenemos

an un+an-1-1 un-1-1 + ¼+ a1 u = -a0,
(5)

y sacando u factor común en el miembro de la izquierda

u (an un-1-1+an-1-1 un-2-2 + ¼+ a1) = -a0.
(6)

Sea b = an un-1-1+an-1-1 un-2-2 + ¼+ a1 entonces 6 queda como

u b = -a0.
(7)

    Esto prueba que una condición necesaria y suficiente para que un entero u sea solución de la ecuación diofántica 3 es que sea factor del término independiente.

Ejemplo 2 La ecuación diofántica

3 x2 + 5 x -1 = 0
(8)

no tiene solución ya que los únicos divisores del término independiente son -1 y 1 y ninguno de ellos verifica la igualdad.

    Nuestro interés se va a centrar en las ecuaciones diofánticas con con más de una incógnita. Por ejemplo, las ecuaciones del tipo

a x + b y = n,
(9)

con a,b y n enteros se llaman ecuaciones diofánticas lineales en dos incógnitas. Generalizando, tenemos que las ecuaciones diofánticas lineales con n incógnitas son aquellas de la forma

a1 x1 +a2 x2 +¼+ an xn = m
(10)

donde los ai para i = 1,2, ¼, n y m son enteros

3  Ecuaciones diofánticas lineales con dos incógnitas

    Vamos a establecer condiciones de existencia y cálculo para las soluciones de ecuaciones diofánticas lineales del tipo

a x + b y = n,
(11)

con a,b y n enteros y a y b no nulos ambos. Primero daremos condiciones de existencia para lo cual precisamos de un interesante y útil lema.

Lema 1 [Identidad de Bezout] Sean a y b dos enteros y sea d = gcd(a,b). Existen entonces enteros x¢ e y¢ tales que a x¢+ b y¢ = d.

    Sea M el conjunto de todas las combinaciones positivas del tipo a x + b y > 0 con x e y enteros. Este conjunto M no es vacío ya que si a > 0, tomando x = 1 e y = 0 conseguimos un elemento de M. Por otro lado, si es a < 0 basta tomar x = -1 e y = 0 para conseguir también un elemento de M. Los enteros de M forman un subconjunto de los naturales. El conjunto de los naturales está bien ordenado por lo que en M existe un primer elemento (mínimo). Probaremos por reducción al absurdo que tal mínimo es precisamente d. En efecto, sea h = minM, existen pues s y t enteros tales que

h = a s + b t.
(12)

    Supongamos que h no divide al entero a. Esto significa que existen q y r enteros que cumplen a = h q + r, donde 0 < r < h. Sustituyendo el valor de h en 12 tenemos

a = (a s + b t)q + r,
(13)

por lo que al despejar r, resulta

r = a-[(a s + b t)q] = a - (a s q + b t q) = a(1-s q) + b ((-t) q))
(14)

    Es decir r pertenece a M ya que es positivo (por definición) y se obtiene como una combinación de la forma a x + b y con x e y enteros. Ahora bien, por el algoritmo de la división es 0 < r < h lo que contradice el carácter de mínimo de h puesto que r es menor que él y pertenece a M. Para evitar esta contradicción concluimos que h es divisor de a. De forma análoga se prueba que h también es divisor de b y sólo resta comprobar que se trata del mayor divisor común. Sea d¢ otro divisor común de a y b. Por tanto,

a = d¢p     b = d¢q,
(15)

siendo p y q distintos. Llevando estas igualdades a la expresión de h tenemos

h = d¢p s + d¢q t = d¢(p s + q t).
(16)

    Es decir, d¢ divide a h y por tanto h es el mayor de los divisores comunes de a y b. Esto termina nuestra demostración.

Ejemplo 3 El máximo común divisor de 230 y 720 se puede obtener mediante el algoritmo de Euclides en la forma siguiente: 720 = 230 3+30
230 = 30 7+20
30 = 20 1+10
20 = 10 2+ 0. Esto significa que gcd(230,720) = 10 y aplicando la identidad de Bezout existen x¢ y y¢ enteros tales que

230 x¢+ 720 y¢ = 10
(17)

    En efecto, según la demostración del lema, el máximo común divisor es el mínimo valor positivo que resulta de la fórmula 230 x + 720y = 10 al variar x e y en el conjunto de los enteros. Un método para hallar estos valores pasa por utilizar los cálculos del Algoritmo de Euclides. Así, sustituyendo de abajo a arriba en las igualdades de 17 (empezando por la penúltima de ellas), resultan las igualdades: 10 = 30 - 20 1
10 = 30 - (230 - 30 7) 1 = 30 - 230 + 30 7 = 30 8 - 230
10 = (720 - 230 3) 8 - 230 = 720 8 - 230 24 - 230 = 720 8 - 230 25. Es decir x = 8 e y = -25

    Basándonos en la identidad de Bezout podemos demostrar un teorema de existencia para las ecuaciones diofánticas lineales con dos incógnitas

Teorema 1 La ecuación diofántica a x+b y = n tiene solución entera si y sólo si d = gcd(a,b) divide a n.

    Sea d = gcd(a,b). Esto quiere decir que a = d s      b = d t, con s y t distintos. Sustituyendo en la ecuación diofántica tenemos

d s x+d t y = n.
(18)

    Podemos sacar a d factor común en el miembro de la izquierda de 20 para obtener

d (s x+t y) = n.
(19)

    Si la ecuación diofántica lineal tiene solución x0,y0, habrá de ser

d(s x0 +t y0 ) = n
(20)

por lo que d es factor (divisor) de n. Recíprocamente si d es factor de n, escribimos n = d p y la ecuación diofántica resulta ser

a x+b y = d p.
(21)

    Usando la identidad de Bezout, existen enteros x¢,y¢ tales que

a x¢+ b y¢ = d
(22)

por lo que multiplicando ambos miembros de 24 por p obtenemos

a x¢p + b y¢p = d p = n
(23)

y los valores x¢p e y¢p son soluciones de la ecuación diofántica. Aquí acaba nuestra demostración.

    Los resultados teóricos expuestos hasta el momento son suficientes para desarrollar un par de algoritmos de solución para las ecuaciones diofánticas lineales con dos incógnitas.

Teorema 2 [Primer algoritmo de resolución] Sigue los pasos:

  • Paso 1: Determinamos si d = gcd(a,b) es divisor de n. En el caso de ser así vamos al paso 2, en caso contrario no hay solución.
  • Paso 2: Si es n = 0 la ecuación adopta la forma
    a x + b y = 0
    (24)

    que tiene la solución trivial x = y = 0. Para obtener más soluciones expresamos y en función de x:

    y = - a x

    b

    (25)

        Como y se quiere entero es necesario que b sea factor de x, es decir, que x sea múltiplo de b. Escribimos pues

    x = b t
    (26)

    con t = 0, ±1, ±2, ... y tenemos todas las soluciones posibles para x. Para hallar las de y sustituimos en la ecuación 27:

    y = -a (bt/b) = -a t.
    (27)

    Si n no es nulo vamos al paso 3.

  • Paso 3: Sea a*x+b*y = n con n diferente de 0. Calculamos el máximo común divisor de a y b utilizando el Algoritmo de Euclides, teniendo el cuidado de especificar en distintas líneas las divisiones que llevamos a cabo. Una vez hemos terminado este algoritmo, reescribimos la primera división mediante un esquema recursivo que comienza en la penúltima división y va siguiendo los cálculos en sentido inverso. Esto se hace con el fin de obtener los coeficientes de una identidad de Bezout (ver ejemplo 3). Al final del procedimiento recursivo se ha de obtener una igualdad del tipo:

    d = a x0 + b y0,
    (28)

    donde d = gcd(a,b) y x0, y0 son los coeficientes de la identidad de Bezout. Como d es un factor de n, hallaremos w tal que n = d w, de forma que multiplicando por w ambos miembros de 30 llegamos a

    n = d w = a (x0 w) + b (y0 w)
    (29)

        Esto indica que x0 w e y0 w son una solución particular de la ecuación a x + b y = n. La solución general se obtiene mediante la particular y las expresiones: x = (x_0 w) + a d t,     t = 0,1 ,2, ...
    y = (y_0 w) - b d t ,     t = 0,1 ,2, ...

        El lector debe observar que 32 y 33 son una especie de progresiones aritméticas con diferencias a/d y - b/d, respectivamente y argumentos, t, enteros.

    A continuación daremos ejemplos de aplicación del algoritmo

Ejemplo 4 Sea la ecuación diofántica 2 x - 5 y = 0. Aplicamos el primer algoritmo:

  • Paso 1: El máximo común divisor de 2 y -5 es 1, el cual es trivialmente un divisor de n = 0. Esto significa que la ecuación tiene solución.
  • Paso 2: Como n = 0 la ecuación tiene la solución trivial x = y = 0. El resto de las soluciones las sacamos mediante la expresión de y en función de x:
    y = 2

    5

    x = 2 x

    5

    .
    (30)

        El carácter entero de y lleva a concluir que x = 5 t con t entero. Ahora sustituimos en 34 este valor de x y obtenemos

    y = 2 5 t

    5

    = 2 t
    (31)

    Aquí tenemos otro ejemplo.

Ejemplo 5 Resolvamos la ecuación diofántica

23 x - 12 y = 7
(32)
  • Paso 1: Como gcd(23, -12) = gcd(23, 12) = 1 y 1 divide a 7, la ecuación tiene solución.
  • Paso 2: Como n = 7 es no nulo vamos al paso 3.
  • Paso 3: Efectuamos las divisiones euclídeas con los valores absolutos de los coeficientes (puesto que basta con tales valores absolutos para obtener los resultados del algoritmo de Euclides): 23 = 121 + 11
    12 = 111 + 1
    11 = 111 + 0 Partimos de la penúltima división y sustituimos hacia arriba: 12 - 11 1 = 1
    23-12 1 = 11
    12 - (23-12 1) 1 = 1

        Simplificamos y agrupamos 40 para obtener la identidad de Bezout:

    12 - (23-12 ·1) ·1 = 1 Þ12 ·2 - 23 ·1 = 1
    (33)

        Sólo resta multiplicar por 7 para llegar a una forma similar a la ecuación inicial 36:

    12·2·7 - 23 ·7 = 1 ·7 Þ 12·14 - 23 ·7 = 7.
    (34)

        Reordenando y asignando signos adecuados tenemos:

    23·(-7) - (-14)·12 = 7.
    (35)

        Es decir, una solución particular es x0 = -7, y0 = -14. La solución general se consigue a partir de ésta y resulta ser: x = (-7) + -12 1 t, t= 0, 1, 2, ...
    y = (-14) - 23 1 t, t= 0, 1, 2, ...

        Podemos simplificarla para llegar a x = (-7) -12 t, t= 0, 1, 2, ...
    y = (-14) - 23 t, t= 0, 1, 2, ...

        Así, para t = 1 obtenemos: x = (-7) -12 1 = -19
    y = (-14) - 23 1 = -37

Observación 1 En la solución general los coeficientes que multiplican a los parámetros t están cambiados. Es decir, para x el coeficiente empleado es el de y dividido por el máximo común divisor y para y el coeficiente es el de x dividido por el máximo común divisor. También es de notar que para el cálculo del máximo común divisor utilizamos los valores absolutos de los coeficientes de la ecuación y los disponemos de forma que el mayor se divide por el menor.

    Vamos a exponer un algoritmo alternativo para resolver las ecuaciones diofánticas lineales en dos incógnitas: a x + b y = n. Este nuevo algoritmo se basa en el ya expuesto y sólo difiere en el último paso. El siguiente ejemplo muestra la aplicación práctica de este segundo algoritmo.

Ejemplo 6 Resolver la ecuación diofántica

120 x - 150 y = 30
(36)
  • Paso 1: Hallamos el máximo común divisor de 120 y -150. Para ello trabajaremos con los valores absolutos de los coeficientes: 120 y 150. 150 = 120 1 + 30
    120 = 30 4 + 0.

        Como gcd(150,120) = 30 la ecuación tiene solución pues el máximo común divisor divide al término independiente.

  • Paso 2: Al ser n ¹0 vamos al siguiente paso, el cual difiere del correspondiente paso del primer algoritmo de resolución
  • Paso 3: Dividimos ambos miembros de la ecuación por el máximo común divisor y queda:
    4 x - 5 y = 1.
    (37)

        Evidentemente, 53 es equivalente a 50 pero los coeficientes son ahora primos relativos (no tienen factores comunes). Volvemos a utilizar el algoritmo de Euclides con los nuevos coeficientes: 5 = 4 1 + 1
    4 = 4 1 + 0.

        Usando estos coeficientes vamos a expresar la fracción 5/4 en forma de fracción continua:

    5

    4

    = 4 ·1 + 1

    4

    = 1 + 1

    4

    = 1 + 1

    4 ·1+0

    = 1 + 1

    4

    .
    (38)

        En este punto suprimimos la última fracción de la expresión continua y resulta 1 valor que se resta a la fracción original 5/4:

    5

    4

    - 1 = 1

    4

    .
    (39)

        Ahora suprimimos denominadores y queda:

    5 - 4 = 1.
    (40)

        Reordenando, tenemos

    -4+5 = 1.
    (41)

        Transformamos para adecuar esta expresión a la ecuación 53

    4 ·(-1) - 5 ·(-1) = 1
    (42)

        Esto significa que x0 = -1, y0 = -1 es una solución particular de la ecuación y, a partir de ella, la solución general es: x = -1 + (-5) t, t = 0, 1, 2,... y = -1 - 4 t, t = 0, 1, 2,...

    Para pulir un poco más este nuevo algoritmo daremos un nuevo ejemplo. Resolveremos la ecuación del ejemplo 5.

Ejemplo 7 La ecuación es 23 x - 12 y = 7. Los pasos 1 y 2 ya los hemos llevado a cabo en el ejemplo 5, el máximo común divisor es 1 y los cálculos del algoritmo de Euclides son: 23 = 121 + 11
12 = 111 + 1
11 = 111 + 0. Ahora dividimos ambos miembros de la ecuación original por el máximo común divisor. En este caso, al ser la unidad no hay modificación. Expresamos la división [23/ 12] como fracción continua mediante los resultados del algoritmo de Euclides: 23 12 = 12 1 + 11 12 = 1 + 11 12
= 1 + 1 12 11 =1 + 1 11 1 +1 11
=1 + 1 1 +1 11.

    Entonces:

23

12

= 1 + 1
1 + 1

11

.
(43)

    Suprimimos la última fracción [1/ 11] y resulta

1 + 1

1

= 1 +1 = 2,
(44)

valor que se resta a [23/ 12]:

23

12

- 2 = 23

12

- 2 ·12

12

= -1

12

(45)

    De esta última igualdad [23/ 12] -[2 ·12/ 12] = [(-1)/ 12] suprimimos denominadores para obtener:

23 - 2 ·12 = -1.
(46)

    Multiplicamos por (-7) para llegar a una expresión similar a la ecuación original:

23 ·(-7) - 12 ·(-14) = 7.
(47)

    Esto significa que x0 = -7, y0 = -14 es una solución particular (la misma que obtuvimos al aplicar el primer algoritmo de resolución). A partir de ella se consigue la solución general de la misma manera que en el ejemplo 5.

4  Ecuaciones diofánticas del tipo x2-y2 = n

    Las ecuaciones diofánticas de segundo grado son todo un mundo de sorpresas y posibilidades. Entre ellas hemos elegido el tipo más sencillo, aquellas que tienen dos incógnitas y están relacionadas en la forma x2-y2 = n. Existe un teorema que nos proporciona una condición necesaria y suficiente para que tales ecuaciones tengan solución. Además nos da el método para obtenerla.

Teorema 3 La ecuación x2-y2 = n, donde n es un entero, tiene soluciones enteras si y sólo si n puede descomponerse en producto de números de la misma paridad (ambos pares o ambos impares). En el caso de que a y b sean dos de tales números (esto es n = a b con a y b de la misma paridad), la pareja de valores

x = a+b

2

, y = a-b

2

(48)

es una solución de la ecuación. Todas las soluciones son de esta forma.

    Sabemos que la diferencia de cuadrados x2-y2 puede factorizarse en todo anillo conmutativo como (x-y)(x+y). El conjunto de los enteros es un anillo unitario y conmutativo por lo que tal factorización es posible. Por otro lado, los valores (x-y) y (x+y han de tener la misma paridad ya que al restar uno de otro resulta un número par: (x-y)-(x+y) = -2y. Esto indica que están situados en la ordenación de los enteros a una distancia par y son ambos pares o impares (por ejemplo, -3 y 5 están a una distancia de 8 unidades, 4 y 14 a una distancia de 10 unidades, etc.). En definitiva, la ecuación original se expresa como

(x-y)(x+y) = n.
(49)

    Supongamos que n = a b con a y b enteros de la misma paridad. Entonces se tiene de 72 que

(x+y) (x-y) = a b
(50)

lo cual nos lleva de forma natural a suponer que x+y = a y x-y = b, puesto que son descomposición de un mismo número n en factores de la misma paridad. A partir de estas igualdades se sigue que

x = a+b

2

, y = a-b

2

,
(51)

valores que resultan enteros puesto que a y b tienen la misma paridad y su suma y diferencia son entonces números pares. Sustituyendo tales valores en la ecuación original se llega a una identidad. Esto termina nuestra demostración.

    Veamos ahora un ejemplo de resolución.

Ejemplo 8 Sea la ecuación diofántica x2-y2 = 200. En primer lugar, descomponemos factorialmente el término independiente 200 con el fin de buscar valores a y b de la misma paridad cuyo producto sea igual a 200.

200 = 22 ·5 2
(52)

    El número de productos r s que dan 200 (sin exigir nada más que la igualdad) se halla mediante el artificio que empleamos a continuación. El número de divisores de un entero cuya descomposición factorial es

n = p1a p2b ¼
(53)

es igual a (a+ 1) (b+1) ¼. En nuestro caso, el número de divisores de 200 es igual a (3+1)·(2+1) = 4·3 = 12. Cada división de 200 por uno de estos doce divisores dará lugar a una descomposición de 200 en producto de dos factores. Así, como 8 es divisor de 200 se sigue que 200 = 8·25 es una descomposición de 200 en producto de dos factores. Los divisores de 200 son, en orden creciente: 1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 200. Cada producto de divisores equidistantes de los extremos proporciona una descomposición de 200 como producto de dos factores, es decir: 1 200
2 100
4 50
5 40
8 25
10 20,

y estos son todos los productos posibles, de los cuales sólo los que siguen tienen la misma paridad:

2 ·100, 4 ·50, 10 ·20.
(54)

    En definitiva, las soluciones de la ecuación son: x_0 = (2+100)/2 = 51, y_0 =(2-100)/2 = -49
x_1 = (100+2)/2 = 51 , y_1 =(100-2)/2 = 49
x_2 = (4+50)/2 = 27 , y_2 =(4-50)/2 = -23
x_3 = (50+4)/2 = 27 , y_3 =(50-4)/2 = 23
x_4 = (10+20)/2 = 15 , y_4 =(10-20)/2 = -5
x_5 = (20+10)/2 = 15 , y_5 =(20-10)/2 = 5

    El lector debe observar que hay 6 soluciones debido a que los tres productos de la misma paridad se pueden poner cada uno de ellos de dos formas distintas.

Area On-Line
  Todo tipo de material, para disfrutar de él completamente On-Line, sin necesidad de descargar archivos ni tener que andar descomprimiendo estos. No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva. Son de lo más interesante.

¿ Nuestros Temas?

En esta sección de la página, se publican distintos artículos matemáticos, ya sean teóricos o prácticos, y todos aquellos escritos que puedan ser de interés para nuestros visitantes.

Se intentan crear versiones on-line de todo el material, pero esto no siempre es posible. Unas veces debido al formato fuente del documento original, y otras al elevado tamaño del archivo final HTM/PHP que haría realmente lenta y tediosa la carga de la página on-line.

Para visualizar correctamente alguno de los artículos disponibles en PHP/HTM, es necesario disponer de los tipos de letra True Type llamados Symbol.ttf y MTExtra.ttf. Descárgalos si no los tienes. Si aun así tienes problemas para visualizar el texto, pásate por nuestra sección de ayuda.

Sábado, 25 / 10 / 2014
   BUSCADOR
 

   TU CORREO
Usuario
Contraseña

   MATRACAS
Lista de correo gratuita
.: Chismes de Adán y Eva :.
Adios a Elisenda Fo...
WolframAlpha: El mo...
WIRIS para Mac...
Third CEU Summersch...
¡Más y más actualiz...
Cerca de 500 MB de ...
Ha llegado el momen...
WIRIS, matemáticas ...
El Universo Matemát...
Segundas Jornadas d...
Los Elementos de Eu...
VI Semana de la Cie...
Tras varios meses d...
¡Chiflados por los ...
Otro verano más, to...

 

Todos los derechos reservados. El Paraíso de las Matemáticas 2010Información Legal Política de PrivacidadAyudaEmail