Ecuaciones diofánticas

Una ecuación diofántica es un tipo de ecuación de varias variables cuyas soluciones son números enteros. Las más sencillas son del tipo $ax+by=c$, y el caso general se expresa$$a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=n$$

El nombre le viene de Diofanto de Alejandría, un notabilísimo matemático griego que nació entre el 200 y el 214 d.C., aunque los expertos no se ponen de acuerdo. Lo que sí se sabe es que murió a los 84 años gracias a un famoso epitafio grabado en su tumba:

Transeúnte, ésta es la tumba de Diofanto: es él quien con esta sorprendente distribución te dice el número de años que vivió. Su niñez ocupó la sexta parte de su vida; después, durante la doceava parte su mejilla se cubrió con el primer bozo. Pasó aún una sépima parte de su vida antes de tomar esposa y, cinco años después, tuvo un precioso niño que, una vez alcanzada al mitad de la edad de su padre, pereció de una muerte desgraciada. Su padre tuvo que sobervivirle, llorándole, durante cuatro años. De todo esto se deduce su edad.

Su edad, pues, sería de 84 años gracias a la ecuación$$\frac{x}{6}+\frac{x}{12}+\frac{x}{7}+5+\frac{x}{2}+4=x.$$Diofanto es considerado el padre de los algebristas modernos, pues en su obra más famosa, Arithmetica, recoge un compendio de problemas al que da solución a ecuaciones y sistemas de ecuaciones determinadas e indeterminadas con solución real. Entre ellas se hallan las ecuaciones diofánticas. Si queréis más detalles, clicad aquí.

Una ecuación diofántica se resuleve mediante dos principios matemáticos sencillos: el máximo común divisor y la identidad de Bézout. Utilizaremos como ejemplo la ecuación diofántica $200x+37y=432$.

Máximo común divisor

El máximo común divisor de dos números a y b, en adelante mcd(a,b), es el mayor divisor de ambos números cuyo resto es 0, es decir, $$\begin{matrix}
mcd\left( a,b \right )=d & y & d \mid a, & d\mid b
\end{matrix}$$ donde "$\mid$" se lee "divide a". Una de sus propiedades dice:

Siendo $a,b,q,r \in \mathbb{Z}$, si $a=bq+r$, entonces $mcd\left(a,b \right) = mcd\left(b,r \right)$

Esta propiedad utilizada recursivamente conforma el famoso algoritmo de Euclides. Con el ejemplo de ecuación, tenemos $mcd\left(200, 37 \right)$ que expresaremos en forma de división:$$200=37\cdot 5 + 15$$Ahora cogemos el divisor y resto, expresamos en forma de división sucesivamente: $$\begin{align*}
37 &= 15 \cdot 2 + 7\\
15 &= 7 \cdot 2 + 1\\
7 &= 1 \cdot 7 + 0\\
\end{align*}$$ El último resto no nulo es 1, por tanto, $mcd \left( 200, 37 \right) = 1$.

Otras maneras de calcular el máximo común divisor es mediante factorización de números enteros o por el mínimo común múltiplo $$mcd \left( a,b \right) = \frac{a \cdot b}{MCM \left( a,b \right)}$$

Identidad de Bézout

Étienne Bézout (1730, Nemours, Francia - 1783, Basses-Loges, Francia) fue un matemático francés, miembro de la Academia de las Ciencias Francesa, que publicó una Teoría general de ecuaciones algebraicas donde aparece la identidad matemática que lleva su nombre. Ésta es:

Si a y b son números enteros con máximo común divisor d, entonces existen enteros x e y tales que $ax+by=d$

Para hallar x e y, utiliza el algoritmo de Euclides y luego lo deconstruye utilizando los restos de cada división. Con el ejemplo anterior teníamos $$\begin{align*}
200 &= 37\cdot 5 +15 & \left[1 \right]\\
37 &= 15\cdot 2 + 7 & \left[2 \right]\\
15 &= 7\cdot 2 + 1 & \left[3 \right]\\
7 &= 1\cdot 7 + 0\\
\end{align*}$$ El último resto no nulo es 1, por tanto procedemos de la siguiente manera: $$\begin{align*}
1 &= 15 - 7\cdot 2 & \textrm{aislamos el resto en } \left [3 \right ]\\
 &= 15 - \left( 37-15 \cdot 2 \right) \cdot 2 & \textrm{aislamos el resto en } \left [2 \right ] \textrm{y substituimos}\\
 &= 15 \cdot 5 - 37\cdot 2 & \textrm{simplificamos}\\
 &= \left( 200 - 37 \cdot 5 \right) \cdot 5 - 37\cdot 2 & \textrm{aislamos el resto en } \left [1 \right ] \textrm{y substituimos}\\
 &= 200 \cdot 5 - 37\cdot 27 & \textrm{simplificamos}\\
\end{align*}$$Con este procedimiento, los enteros x, y que cumplen $200x+37y=1$ son $x=5$ e $y=-27$

Ecuaciones diofánticas

Resolver estas ecuaciones precisa de un par de teoremas que cabe definir y demostrar. Son teoremas que usan las operaciones anteriores. Vamos con el primero:

Teorema 1

Una ecuación diofántica tiene solución entera $x_{0}$, $y_{0}$ si y sólo si el máximo común divisor de a y b es divisor también de n. Además, sea d el $mcd\left( a,b \right)$, obtenemos soluciones particulares de la forma: $$\begin{align*}
x_{0} &= \frac{n}{d} \cdot \alpha\\
y_{0} &= \frac{n}{d} \cdot \beta
\end{align*}$$ siendo $d=\alpha a + \beta b$

Empezaremos por la implicación de izquierda a derecha:
Si una ecuación diofántica $ax+by=n$ tiene solución entera $x_{0}$, $y_{0}$, entonces $$ax_{0}+by_{0} = n.$$ Tenemos que d es divisor de a y b, por tanto decimos que $a=a_{1}d$ y $b=b_{1}d, \; \forall a_{1},b_{1} \in \mathbb{Z}$.
Substituimos: $$ax_{0}+by_{0} = a_{1}dx_{0}+b_{1}dy_{0} =\left( a_{1}x_{0}+b_{1}y_{0} \right)d = kd = n.$$Concluimos pues que d divide a n.

Vamos con la implicación de derecha a izquierda:
Dado que $d \mid n$, existe un $k \in \mathbb{Z}$ tal que $n = dk$. Por otra parte, la identidad de Bézout nos dice que $\exists \alpha , \beta \in \mathbb{Z} : d = a\alpha + b\beta$. Entonces$$dk = \left( a\alpha + b\beta \right)k = \left( k\alpha \right)a + \left( k\beta \right)b = n$$De donde concluimos que $k\alpha$ y $k\beta$ son soluciones de la ecuación. Con esto,$$x_{0} = k\alpha = \frac{n}{d}\alpha \\ y_{0} = k\beta = \frac{n}{d}\beta$$Este teorema demuestra que existen soluciones y que conseguiremos una solución particular de la ecuación, pero puede haber más de una y queremos saber cómo son:

Teorema 2

Si una ecuación diofántica tiene solución entera particular $x_{0}$, $y_{0}$, entonces toda solución entera x, y es de la forma: $$\begin{align*}
x = x_{0} + \frac{b}{d}t\\
y = y_{0} - \frac{a}{d}t
\end{align*}$$ siendo  $d=\alpha a + \beta b$ y  $t \in \mathbb{Z}$

Partimos de que $x_{0}, y_{0}$ son solución particular de la ecuación, supondremos que x, y también lo son. Con esto, tenemos:$$\begin{matrix}
ax + by = n\\
ax_{0} + by_{0} = n
\end{matrix}$$Restamos ambas ecuaciones y obtenemos$$a \left( x-x_{0} \right) + b \left( y-y_{0} \right) = 0$$Pasamos el segundo sumando a la otra parte:$$a \left( x-x_{0} \right) = b \left( y_{0}-y \right)$$Y dividimos por d: $$\frac{a}{d} \left( x-x_{0} \right) = \frac{b}{d} \left( y_{0}-y \right).$$Como $\frac{a}{d}$, $\frac{b}{d}$ son coprimos y $\left. \frac{a}{d} \right| \frac{b}{d} \left( y_{0}-y \right)$, $\frac{a}{d}$ divide a $\left( y_{0}-y \right)$. Para ello, existe $t \in \mathbb{Z}$ tal que:$$\frac{a}{d}t = y_{0}-y,$$y de aquí $$y = y_{0}- \frac{a}{d}t.$$ Substituimos en la fórmula: $$\begin{align*}
\frac{a}{d} \left( x-x_{0} \right) &= \frac{b}{d} \left( y_{0}-y \right) = \\
 &= \frac{b}{d} \left( y_{0}-y_{0}+ \frac{a}{d}t \right) = \\
 &= \frac{b}{d} \cdot \frac{a}{d}t \\
x-x_{0} &= \frac{b}{d}t \\
x &= x_{0} + \frac{b}{d}t
\end{align*}$$

Resolver la ecuación

Ahora empezamos a resolver nuestra ecuación $200x + 37y = 432$:

1. El máximo común divisor de 200 y 37 debe dividir a 432.

Como podemos comprobar por Euclides, $mcd \left( 200,37 \right) = 1$ y $1 \mid 432$


2. Hallar soluciones $x_{1}$, $y_{1}$ que cumplan  $200x_{1} + 37y_{1} = 1$


Mediante la identidad de Bézout, habíamos obtenido $x_{1} = 5$, $y_{1} = -27$.


3. Hallar soluciones $x_{0}$, $y_{0}$ que cumplan  $200x_{0} + 37y_{0} = 432$


Recordemos que una solución de la ecuación corresponde a la forma $x_{0} = \frac{n}{d}x_{1}$, $y_{0} = \frac{n}{d}y_{1}$. Por tanto, $$x_{0} = \frac{432}{1} \cdot 5 = 2160 \\ y_{0} = \frac{432}{1} \cdot \left( -27 \right) = -11664$$


4. Hallar la solución general a la ecuación diofántica


$$x = 2160  + \frac {37}{1}t = 2160  +  37t \\ y = -11664 - \frac {200}{1} \cdot t = -11664 - 200t$$ Comprobamos que todo está correcto en esta tabla de valores:

$$\begin{matrix}
\boldsymbol{t} & \boldsymbol{x} & \boldsymbol{y} & \boldsymbol{200x+37y}\\
-2 & 2086 & -11264 & 200\cdot 2086 + 37 \cdot \left ( -11264 \right ) = 432\\
-1 & 2123 & -11464 & 200\cdot 2123 + 37 \cdot \left ( -11464 \right ) = 432\\
0 & 2160 & -11664 & 200\cdot 2160 + 37 \cdot \left ( -11664 \right ) = 432\\
1 & 2197 & -11864 & 200\cdot 2197 + 37 \cdot \left ( -11864 \right ) = 432\\
2 & 2234 & -12064 & 200\cdot 2234 + 37 \cdot \left ( -12064 \right ) = 432
\end{matrix}$$Y así, todos los valores que queráis.

Utilidades

Una ecuación de dos o más variables es una forma de relación entre las variables y su resultado. En la práctica, se me ocurre que estas ecuaciones sirven para fines económicos o de stock. Un ejemplo: una empresa destina una partida de dinero a material pero no le importa la cantidad de cada artículo siempre que no se exceda del presupuesto. Con la ayuda de un software informático, se pueden calcular esas variables.

Otra utilidad "escondida" aparece cuando extraemos dinero de los cajeros automáticos. El dinero que solicitamos viene siempre en billetes de 20 y 50 euros. La ecuación diofántica que procesan los cajeros es $20x+50y=cantidad$. Cualquier cantidad superior a 40 euros es procesada dentro de esa ecuación con la condición de que las incógnitas sean siempre positivas (no tiene sentido que te den -4 billetes de 50 euros). Lo mismo pasa con las máquinas que devuelven el cambio, aunque sus ecuaciones contiene más variables.

El problema de los cocos y el mono

Diofanto dio a conocer la metodología que usaba para resolver ecuaciones diofánticas en su libro Arithmetica, mediante un ejemplo de problema, llamado problema de los cocos y el mono.

Éste es el enunciado del problema, de manera más escueta:

Un navío con 5 hombres naufraga en una isla. Para sobrevivir se dedican a recolectar cocos de las palmeras mientras un mono se dedica a observarles. Por la noche, uno de ellos se despierta por hambre, y decide separar su parte desconfiando del mono. Divide los cocos en cinco montones y como sobró uno, se lo dio al mono, quedándose él su quinta parte. Más tarde, un segundo náufrago se despertó por el mismo motivo, y de los cocos que había (sin saber él que se habían sustraído algunos previamente) divide los cocos en cinco grupos, da el coco sobrante al mono y se queda su parte. Y así sucesivamente con los otros tres marineros. Por la mañana del día siguiente, se repartieron los cocos que quedaron y no sobró ninguno. ¿Cuántos cocos habían recolectado, como mínimo?

Sea $C$ la cantidad total de cocos,  $n_{1},n_{2},n_{3},n_{4},n_{5}$ cada náufrago y $n_{6}$ la repartición final de cocos. Cada uno separa una quinta parte de los cocos que observa cuando se despierta. Así, el primer náufrago cuenta $$C = 5n_{1}+1 \textrm{ cocos.}$$ El segundo náufrago no sabe que ya no existe una quinta parte más un coco del total, así que se quedará con una quinta parte de lo que hay y dará otro coco al mono. Entonces $$C-n_{1}-1 = 5n_{2}+1$$ Y así sucesivamente, hasta que por la mañana siguiente, se reparten los cocos que quedan, con lo que tenemos: $$\begin{align*}
C &= 5n_{1}+1 & &\Rightarrow & n_{1} &= \frac{C-1}{5}\\
C-n_{1}-1 &= 5n_{2}+1 & &\Rightarrow & n_{2} &= \frac{4C-9}{25}\\
C-n_{1}-n_{2}-2 &= 5n_{3}+1 & &\Rightarrow & n_{3} &= \frac{16C-61}{125}\\
C-n_{1}-n_{2}-n_{3}-3  &= 5n_{4}+1 & &\Rightarrow & n_{4} &= \frac{64C-369}{625}\\
C-n_{1}-n_{2}-n_{3}-n_{4}-4 &= 5n_{5}+1 & &\Rightarrow & n_{5} &= \frac{256C-2101}{3125}\\
C-n_{1}-n_{2}-n_{3}-n_{4}-n_{5}-5 &= 5n_{6} & &\Rightarrow & n_{6} &= \frac{1024C-8404}{15625}\\
\end{align*}$$Cogemos la última igualdad y la escribimos en forma de ecuación diofántica: $$1024C-15625n_{6} = 8404 \Leftrightarrow 1024C+ \left( -15625n_{6} \right) = 8404$$ Calculamos el $mcd \left( 1024,-15625 \right)$ con el algoritmo de Euclides y obtenemos $$mcd \left( 1024,-15625 \right) = -1\;\; \textrm{y} \;\; -1 \mid 8404$$ Ahora sabemos que existe solución entera $x_{0}, y_{0}$ de la ecuación, y por la identidad de Bézout, sabemos también que existen $x_{1}, y_{1}$ enteros tales que $1024x_{1}-15625y_{1} = -1$. Deconstruyendo el algoritmo de Euclides obtenemos las soluciones particulares $$\begin{align*}
x_{1} &= 4776\\
y_{1} & =313
\end{align*}$$ Estas soluciones particulares se convierten en soluciones particulares de la ecuación principal mediante $$\begin{align*}
x_{0} &= \frac{8404}{-1} \cdot 4776 = -40137504\\
y_{0} &= \frac{8404}{-1} \cdot 313= -2630452
\end{align*}$$ Ya tenemos una solución particular de la ecuación, y para hallar todas las posibles soluciones, operamos de la forma: $$\begin{align*}
C &= -40137504+ \frac{-15625}{-1}t = -40137504+ 15625t\\
f &= -2630452- \frac{1024}{-1}t = -2630452+ 1024t
\end{align*}$$ Está claro que dando valores a t obtendremos soluciones de la ecuación cuyos valores serán los cocos recolectados, pero los valores negativos no tienen sentido. Por tanto hemos de ver para qué valores de t tendremos C positivo. Para ello: $$\begin{align*}
-40137504+ 15625t &\geq 0\\
t &\geq \frac{40137504}{15625}\\
t & \geq 2569
\end{align*}$$ Esa es el menor valor de t que requerimos para que haya cocos. Comprobamos que $$\begin{align*}
t &= 2568 \Rightarrow C = -12504\\
t &= 2569 \Rightarrow C = 3121
\end{align*}$$ Entonces, los náufragos recolectaron 3121 cocos, de los cuáles 624 se quedó el primer náufrago, 499 el segundo, 399 el tercero, 319 el cuarto, 255 el quinto, 5 el mono y luego 204 cocos sobrantes para cada uno de los náufragos.