Ecuaciones diofánticas¶
Según cuentan, la tumba de Diofanto de Alejandría mostraba el siguiente acertijo:
El epitafio de Diofanto
Transeúnte, esta es la tumba de Diofanto: los números pueden mostrar, ¡oh maravilla! la duración de su vida. Su niñez ocupó la sexta parte de su vida; después, durante la doceava parte, de vello se cubrieron sus mejillas. Pasó aún una séptima parte de su vida antes de tomar esposa y, cinco años después, tuvo un precioso niño que, una vez alcanzada la mitad de la edad de la vida de su padre, pereció de una muerte desgraciada. Su padre tuvo que sobrevivirle, llorándole, durante cuatro años. De todo esto se deduce su edad.
¿Cuántos años vivió Diofanto?
Si llamamos \(x\) a los años que vivió Diofanto, el acertijo nos lleva a plantear la ecuación
Operando, obtenemos la solución \(\boxed{x=84}\).
Diofanto de Alejandría fue un matemático griego que vivió alrededor del siglo III. Es conocido principalmente por su obra Arithmetica, un tratado de 13 libros, de los que solo se conservan los seis primeros. En esta obra, Diofanto presenta una colección de problemas que plantean ecuaciones determinadas (con una única solución) o indeterminadas (con varias soluciones). La mayoría de las ecuaciones del libro se convierten en ecuaciones de segundo grado. Aunque en Arithmetica solo se plantean problemas concretos y no se desarrolla una teoría general de las ecuaciones, hoy en día se conocen como ecuaciones diofánticas aquellas con coeficientes enteros y de las que solo interesan sus soluciones enteras.
Problema
Un elevador está estropeado y solo puede subir o bajar en pasos de 130 cm o de 80 cm. ¿Existe alguna secuencia de pasos que permita subir 10 cm?
Solución
Buscamos soluciones enteras de la ecuación \(130x + 80y = 10\). Una posibilidad es buscar soluciones por tanteo. Podemos hacer una lista de múltiplos de \(130\) y de \(80\) y buscar múltiplos cuya diferencia sea \(10\). No es difícil ver que \(130 \cdot 3 = 390\) y que \(80 \cdot 5 = 400\), por lo que una solución de esta ecuación es \((x,y)=(-3,5)\).
El famoso comentario de Fermat
El matemático Pierre de Fermat tenía un ejemplar de Arithmetica y alrededor de 1637 escribió en el margen de una de sus páginas un comentario que ya forma parte de la historia de las matemáticas:
No existen tres números enteros \(x,y,z\), todos distintos de cero, tales que \(x^n+y^n=z^n\) para \(n>2\). Tengo una demostración maravillosa de este hecho, pero este margen es demasiado estrecho para contenerla.
Para \(n=2\) existen infinitas soluciones, las conocidas como ternas pitagóricas: \({3^2+4^2=5^2}\), \({5^2+12^2=13^2}\), etc. Pero Fermat aseguraba en su anotación que no había igualdades semejantes para potencias superiores. Mientras que otras observaciones que Fermat dejó sin demostración consiguieron ser demostradas, esta conjetura se resistió durante más 350 años. Finalmente, en 1995, Andrew Wiles publicó su demostración de lo que actualmente se conoce como el último teorema de Fermat o teorema de Fermat-Wiles. Se cree que la demostración que Fermat dijo tener era incorrecta, ya que las técnicas que fueron desarrolladas por Wiles y otros estaban fuera de su alcance.
El lema de Bézout¶
Las ecuaciones diofánticas aparecen en muchos problemas prácticos, pero a primera vista no es fácil saber si tienen solución o no.
Dos problemas parecidos
Soy el encargado de comprar los refrescos para una fiesta. Entre unos cuantos amigos hemos juntado un bote de 50 €, y queremos gastarlo completamente. En la tienda A venden packs de latas a 4 € y packs de botellas a 9 €. En la tienda B los packs de latas están también a 4 €, pero los de botellas a 8 €. ¿Podré gastar todo el dinero en alguna de las dos tiendas?
Solución
Para gastar todo el dinero en la tienda A, debemos hallar soluciones en los naturales a la ecuación \(4x+9y=50\), donde \(x,y\) son el número de packs de latas y de botellas, respectivamente. Esta ecuación tiene infinitas soluciones enteras, pero solo una en la que ambos valores sean positivos \((x,y)=(8,2)\).
Para la tienda B, la ecuación es parecida, \(4x+8y=50\). Pero ahora el lado izquierdo es múltiplo de 4 y el derecho no. ¡No hay soluciones enteras! Si queremos gastar los 50 €, tendremos que comprar en A, ¡aunque sea más cara! 
El problema anterior nos da la clave. La ecuación \(ax+by=c\) no puede tener soluciones enteras si el lado izquierdo tiene un factor común que el lado derecho no tiene. Es decir, si el máximo común divisor de \(a\) y \(b\) no divide a \(c\), entonces la ecuación no tiene soluciones enteras. Pero, ¿y al revés? ¿Tendrá solución siempre que \(c\) sea múltiplo del \(\text{mcd}(a,b)\)? ¡Sí! Este hecho se conoce como el lema de Bézout.
Lema de Bézout
La ecuación diofántica \(ax+by=c\) tiene soluciones enteras si y solo si \(\text{mcd}(a,b) \,\vert\, c\).
Parece claro que el máximo común divisor tiene mucho que ver con la solubilidad de las ecuaciones diofánticas, así que necesitamos un buen método para hallarlo.
El algoritmo de Euclides¶
Uno de los algoritmos matemáticos más antiguos que siguen usándose es el algoritmo de Euclides, que permite calcular el máximo común divisor de dos números. Aparece en los libros VII y X de su obra fundamental, Elementos. Concretamente, la proposición 1 del libro VII dice:
Dados dos números desiguales y restando sucesivamente el menor del mayor, si el que queda no mide nunca al anterior hasta que quede una unidad, los números iniciales serán primos entre sí.
Cuando Euclides escribe “el que queda no mide nunca al anterior”, quiere decir “el que queda nunca divide al anterior”. Es decir, “medir” significa “dividir de forma exacta, ser divisor”. Euclides nos está dando un método para averiguar si dos números son primos entre sí (es decir, si su \(\text{mcd}\) es \(1\)).
En realidad, es mejor todavía: este algoritmo nos permite averiguar el \(\text{mcd}\) de dos números. La idea clave es que si un número divide a otros dos, entonces también divide a su diferencia. Por ejemplo, 3 es divisor de 12 y también de 21, por lo tanto también divide a su diferencia \(21-12=9\). De forma más matemática,
Dados \(a,b,c \in \N\), si \(c | a\) y \(c |b\), entonces \(c | a-b\)
Si \(c\) divide a \(a\), podemos escribir \(a=c \cdot m\) para algún \(m \in \N\). Si \(c\) divide a \(b\), podemos escribir \(b=c \cdot n\) para algún \(n \in \N\). Entonces,
por lo que \(c\) divide a \(a-b\).
Con el algoritmo de Euclides obtenemos números cada vez más pequeños, por lo que en algún momento vamos a terminar con un número que divide a todos los anteriores: el máximo común divisor.
Cálculo del \(\text{mcd}\) de dos números
Apliquemos las instrucciones de Euclides para calcular \(\text{mcd}(23,34)\):
- ¿\(23\) mide a \(34\)? No, así que restamos el menor del mayor: \(34-23=11\)
- ¿\(11\) mide a \(23\)? No, así que restamos el menor del mayor: \(23-11=12\)
- ¿\(11\) mide a \(12\)? No, así que restamos el menor del mayor: \(12-11=1\)
Hemos llegado a la unidad sin que el menor divida nunca al mayor, y por lo tanto concluimos que \(23\) y \(34\) son primos entre sí. Es decir, \(\text{mcd}(23,34)=1\).
Calculemos ahora \(\text{mcd}(24,34)\):
- ¿\(24\) mide a \(34\)? No, así que restamos el menor del mayor: \(34-24=10\)
- ¿\(10\) mide a \(24\)? No, así que restamos el menor del mayor: \(24-10=14\)
- ¿\(10\) mide a \(14\)? No, así que restamos el menor del mayor: \(14-10=4\)
- ¿\(4\) mide a \(10\)? No, así que restamos el menor del mayor: \(10-4=6\)
- ¿\(4\) mide a \(6\)? No, así que restamos el menor del mayor: \(6-4=2\)
- ¿\(2\) mide a \(4\)? ¡Sí! Hemos terminado.
Hemos hallado un número que divide al anterior antes de llegar a la unidad, así que \(\text{mcd}(24,34)=2\).
Para hacerlo más rápido, en vez de restar sucesivamente el menor del mayor, haremos la división entera y nos quedaremos con el resto. Restando, deberíamos hacer
pero en vez de restar \(10\) tres veces seguidas, podemos hacer directamente la división entera \({34=3 \cdot 10 + 4}\) para llegar a la siguiente pareja \(10,4\).