Ecuaciones diofantinas lineales

Introducción

En este capítulo vamos a estudiar las ecuaciones lineales diofantinas, para estas ecuaciones vamos a obtener soluciones en el dominio de los números enteros. Estas ecuaciones deben su nombre a Diofanto de Alejandría, un matemático griego del siglo III d.C., considerado uno de los primeros en desarrollar métodos que parecen algebraicos para resolver problemas con soluciones enteras.
Las ecuaciones diofantinas son útiles para modelar situaciones o problemas en las que se buscan soluciones enteras a partir de relaciones entre cantidades, por ejemplo, si quisiéramos encontrar dos números enteros cuya suma sea \(20\) y cuya diferencia sea \(4\), podríamos plantear que \(x\) sea el primer número y \(y\) el segundo y representar el problema con las siguientes ecuaciones,

\[\begin{split}\begin{cases} x + y = 20, \\ & \\ x - y = 4. \end{cases}\end{split}\]

Ahora, imaginemos que necesitamos pagar \(85\) pesos por una compra realizada en la tienda, el problema es que sólo tenemos monedas de \(5\) y \(10\) pesos. ¿Cuántas monedas de cada tipo necesitamos usar para pagar el importe exacto?. Podríamos plantear que \(x\) represente el número de monedas de \(5\) pesos y \(y\) el número de monedas de \(10\) pesos, el problema se representa con la siguiente ecuación,

\[5x + 10y = 85.\]

En este capítulo veremos cómo resolver ecuaciones diofantinas en dos variables mediante varios métodos y después extenderemos la idea a ecuaciones diofantinas con \(n\) variables.

Ecuaciones diofantinas lineales en dos variables

Definición 13 (Ecuación diofantina lineal en dos variables)

La ecuación \(ax + by = c\), donde \(a,b\) y \(c\) son números enteros fijos, es llamada ecuación diofantina lineal en dos variables. En estas ecuaciones se buscan soluciones enteras para las variables involucradas \(x\) y \(y\).

Los siguientes ejemplos son de ecuaciones que hemos visto alguna vez en nuestros cursos de matemáticas de preparatoria, pero bajo cierta restricción se pueden considerar ecuaciones diofantinas. Para tener más claridad en las soluciones, las vamos a relacionar con ideas geométricas.

Ejemplo 32

Cuando restringimos las soluciones a números enteros, las siguientes ecuaciones son diofantinas.

• \(2x+3y=4\).

Geométricamente las soluciones de la ecuación son puntos que viven sobre la recta \(2x+3y=4\), donde las coordenadas de estos puntos son números enteros. Por ejemplo, el punto \((-1,2)\) es una solución de la ecuación anterior, de hecho, esta ecuación tiene una infinidad de soluciones enteras las cuales son de la forma \((2+3t,-2t)\), donde \(t\) es un entero arbitrario.

• \(x^2+y^2=1\).

La ecuación tiene exactamente \(4\) soluciones enteras: \((-1,0),(1,0),(0,1)\) y \((0,-1)\), que son los puntos en donde la circunferencia de radio \(1\) intercepta con los ejes \(x\) y \(y\).

• \(2x+4y=5\).

En este caso, no importa cuáles sean los enteros \(x\) y \(y\), esta ecuación no puede cumplirse. Podemos observar que el lado izquierdo de la ecuación \(2x+4y\) siempre será un número par, mientras que el lado derecho de la ecuación es \(5\) que es un número impar, y como la suma de dos números pares es par, entonces podemos concluir que esta ecuación no tendrá soluciones enteras.

• \(x^2+y^2=z^2\).

Las soluciones enteras de la ecuación representan las longitudes de los lados de un triángulo rectángulo; \((3,4,5)\) es una de sus soluciones. Esta ecuación también tiene un número infinito de soluciones enteras.

La clase más simple de ecuaciones diofantinas son las ecuaciones diofantinas lineales en dos variables.
Como podemos ver en los ejemplos anteriores, las ecuaciones diofantinas pueden tener una infinidad de soluciones, pocas soluciones o no tener ninguna solución entera. Veamos un teorema que nos ayudará a identificar cuándo una ecuación diofantina tiene solución.

Teorema 10

La ecuación diofantina \(ax+by=c\) tiene solución si y sólo si \(d\mid c\), donde \(d=(a,b)\).
Además, si \(x_0\) y \(y_0\) es una solución particular de la ecuación diofantina, entonces todas sus soluciones están dadas por

\[x=x_0+ \left( \frac{b}{d} \right)t, \quad y=y_0- \left( \frac{a}{d} \right)t,\]

donde \(t\) es un entero arbitrario.

Demostración. La demostración del teorema consiste de \(4\) partes.

• Primero probaremos que si la ecuación lineal diofantina \(ax+by=c\) tiene solución, entonces \(d|c\).

Supongamos que \(x = \alpha, y= \beta\) es una solución de la ecuación. Entonces se satisface que

\[a \alpha + b \beta = c.\]

Ya que \(d=(a,b)\), tenemos que \(d|a\) y \(d|b\), luego por la propiedad \(4\) de la Proposición 2 sucede que \(d|(a \alpha + b \beta)\), y por lo tanto \(d|c\).

• Ahora veamos que si \(d|c\), entonces la ecuación lineal diofantina \(ax+by=c\) tiene solución.

Por hipótesis tenemos que \(d|c\).
Entonces \(c=de\) para algún entero \(e\). Ya que \(d=(a,b)\), por el Lema 2 podemos escribir el máximo común divisor como una combinación lineal de \(a\) y \(b\), es decir, existen \(r\) y \(s\) tal que \(ra + sb = d\). Si multiplicamos ambos lados de la igualdad por \(e\) tenemos que,

\[\begin{align*} rae + sbe &= de, \\ & \\ a(re) + b(se) &=c. \end{align*}\]

Así, \(x_0=re\) y \(y_0=se\) es una solución de la ecuación lineal diofantina.

• Ahora mostraremos que \(x = x_0 + \left( \frac{b}{d} \right)t\) y \( y = y_0 - \left( \frac{a}{d} \right)t\) es una solución de la ecuación lineal diofantina \(ax+by=c\).

Si sustituimos la solución en la ecuación \(ax+by=c\) tenemos que,

\[\begin{align*} ax+by &= a \left[ x_0+\left( \frac{b}{d} \right) t \right] + b \left[ y_0 - \left( \frac{a}{d} \right) t \right] \\ & \\ &= (ax_0 + by_0) + \frac{abt}{d} - \frac{abt}{d} \\ & \\ &= ax_0 + by_0 = c. \end{align*}\]

Así, \(x = x_0 + \left( \frac{b}{d} \right) t \) y \(y = y_0 - \left( \frac{a}{d} \right) t\) es una solución para cualquier entero \(t\).

• Por último, veamos que toda solución \(x', y'\) es de la forma \(x' = x_0 + \left( \frac{b}{d} \right) t \) y \(y' = y_0 - \left( \frac{a}{d} \right) t\).

Ya que \(x_0, y_0\) y \(x', y'\) son soluciones de la ecuación lineal diofantina, tenemos que,

\[\begin{split}\begin{cases} ax_0 + by_0 = c, \\ & \\ a x' + b y' = c. \end{cases}\end{split}\]

Luego, podemos igualar las igualdades y agrupar los términos de la siguiente manera,

\[\begin{align*} ax_0 + by_0 &= a x' + b y', \\ & \\ a( x' - x_0) &= b(y_0 - y'). \\ \end{align*}\]

Dividiendo ambos lados entre \(d\) tenemos que,

\[\left( \frac{a}{d} \right) \left( x' - x_0 \right) = \left( \frac{b}{d} \right) \left( y_0 - y' \right).\]

Sabemos que, por la Proposición 8 \(\left( \frac{a}{d},\frac{b}{d} \right) = 1\), y por el Corolario 2, tenemos que \(\frac{b}{d} \mid ( x' - x_0)\), es decir que \(x' - x_0 = \left( \frac{b}{d} \right) t\) para algún entero \(t\). Y por lo tanto

\[x' = x_0 + \left( \frac{b}{d} \right) t.\]

Ahora, sustituyendo \(x' - x_0 = \left( \frac{b}{d} \right) t\) tenemos que,

\[\begin{align*} a( x' - x_0) &= b(y_0 - y'), \\ & \\ a \left( \frac{b}{d} \right)t &= b(y_0 - y'), \\ & \\ \left( \frac{a}{d} \right)t &= (y_0 - y'), \\ & \\ y' &= y_0 - \left( \frac{a}{d} \right) t. \end{align*}\]

Por lo tanto, toda solución de la ecuación lineal diofantina es de la forma \(x' = x_0 + \left( \frac{b}{d} \right) t \) y \(y' = y_0 - \left( \frac{a}{d} \right) t\). \(\square\)

Del Teorema 10 se sigue que, si una ecuación lineal diofantina \(ax+by=c\) tiene solución, entonces tiene una infinidad de soluciones. Están dadas por la solución general \(x = x_0+ \left( \frac{b}{d} \right)t\) y \(y = y_0- \left( \frac{a}{b} \right)t\). Si damos diferentes valores enteros a la variable \(t\) podemos encontrar una infinidad de soluciones. De este teorema tenemos el siguiente corolario.

Corolario 3

Si \((a,b)=1\), entonces la ecuación lineal diofantina \(ax+by=c\) tiene solución y la solución general está dada por \(x = x_0 + bt, y = y_0 - at\), donde \(x_0, y_0\) es una solución particular.

Veamos dos ejemplos, en el segundo mostraremos una manera de encontrar soluciones. En estos ejemplos funciona el procedimiento mostrado porque trabajamos con números pequeños, pero cuando los números son más grandes este procedimiento no es la mejor manera de buscar soluciones.

Ejemplo 33

Determina si las siguientes ecuaciones lineales diofantinas tienen solución. Después, encuentra una solución particular y da la solución general.

• \(6x + 8y = 25\).

• \(12x + 18y = 30\).

Solución.

• \(6x + 8y = 25\).

1. Calculamos el máximo común divisor de \((a,b) = d\).

Utilizando el algoritmo de Euclides, tenemos que \((6,8) = 2\).

2. Revisamos que \(d|c\).

Entonces, como \(d = 2\) y \(c = 25\) tenemos que \(2\nmid 25\). Por lo tanto, la ecuación no tiene solución.

• \(12x + 18y = 30\).

1. Calculamos el máximo común divisor de \((a,b) = d\).

Utilizando el algoritmo de Euclides, tenemos que \((12,18) = 6\).

2. Revisamos que \(d | c\).

Como \(d = 6\) y \(c = 30\) tenemos que \(6|30\), por lo tanto la ecuación \(12x + 18y = 30\) sí tiene solución.

3. Buscamos una solución particular de la ecuación \(12x + 18y = 30\).

Veamos que podemos encontrar una solución particular si despejamos una de las variables de la ecuación y tratamos por prueba y error.

\[\begin{align*} 12x + 18y &= 30 \\ & \\ 12x &= -18y + 30 \\ & \\ x &= \frac{-18y+30}{12} \end{align*}\]

Ahora, probamos algunos valores enteros de \(y\) hasta encontrar un valor de \(x\) que sea entero.

\[\begin{align*} y &= 1, &\quad x &= \frac{-18\cdot 1+30}{12} = \frac{12}{12} = 1, \\ & \\ y &= 2, &\quad x &= \frac{-18\cdot 2+30}{12} = \frac{-6}{12} = - \frac{1}{2}, \\ & \\ y &= 3, &\quad x &= \frac{-18\cdot 3+30}{12} = \frac{-24}{12} = -2, \\ & \\ y &= 4, &\quad x &= \frac{-18\cdot 4+30}{12} = \frac{-42}{12} = - \frac{7}{2}, \\ & \vdots & & \vdots \end{align*}\]

Usamos \(x_0 = 1\), \(y_0 = 1\) como solución.

4. Damos la solución general.

Por último, con la solución particular encontrada podemos dar la solución general de la ecuación, esto es,

\[\begin{align*} x &= x_0 + \left( \frac{b}{d} \right)t, &\quad y &= y_0 - \left( \frac{a}{d} \right)t, \\ & \\ x &= 1 + \left( \frac{18}{6} \right)t, &\quad y &= 1 - \left( \frac{12}{6} \right)t, \\ & \\ x &= 1 + 3t, &\quad y &= 1 - 2t. \end{align*}\]

Por lo tanto, la solución general es \(x = 1 + 3t\) y \(y = 1 - 2t\).

Algoritmo de Euclides para resolver ecuaciones diofantinas lineales

En el Ejemplo 33 anterior buscamos una solución por prueba y error. Ahora, vamos a ver que el algoritmo de Euclides es un método eficiente para encontrar soluciones de las ecuaciones diofantinas, la idea es la siguiente.

Observación 3

Si tenemos la ecuación diofantina \(ax + by = c\), vamos a buscar el máximo común divisor de \(a\) y \(b\), digamos que \((a,b) = d\). Luego, por el algoritmo de Euclides tendríamos que existen \(n\) y \(m\) tales que,

\[d = an + bm.\]

Por el Teorema 10, sabemos que la ecuación tiene solución si \(d|c\), en otras palabras \(c = de\) para algún entero \(e\). Si multiplicamos la combinación lineal por \(e\), entonces tendríamos que

\[\begin{align*} d &= an + bm, \\ & \\ de &= ane + bme, \\ & \\ c &= ax_0 + by_0. \end{align*}\]

De esta manera, obtendríamos la solución particular \(x_0,y_0\), donde \(x_0 = ne, y_0 = me\).

Veamos con un ejemplo cómo encontrar la solución de una ecuación diofantina utilizando el algoritmo de Euclides.

Ejemplo 34

Determina si la ecuación lineal diofantina \(63x-23y=-7\) tiene solución. Además, encuentra la solución general.

Solución.

1. Comprobemos si la ecuación tiene solución.

Aplicando el algoritmo de Euclides tenemos que:

\[\begin{align*} 63 &= 23\cdot 2 + 17, \\ & \\ 23 &= 17\cdot 1 + 6, \\ & \\ 17 &= 6\cdot 2 + 5, \\ & \\ 6 &= 5\cdot 1 + 1, \\ & \\ 5 &= 1\cdot 5 + 0. \end{align*}\]

Por lo tanto, tenemos que \((63,23) = 1\), y como \(1|(-7)\) la ecuación \(63x - 23y = -7\) tiene solución.

2. Vamos a escribir el máximo común divisor como una combinación lineal de \(63\) y \(23\).

Utilizamos las ecuaciones anteriores para sustituir de manera inversa.

\[\begin{split}\begin{cases} 1 = 6 - 5\cdot 1, \ldots (1) \\ & \\ 5 = 17 - 6\cdot 2, \ldots (2) \\ & \\ 6 = 23 - 17\cdot 1, \ldots (3) \\ & \\ 17 = 63 - 23\cdot 2, \ldots (4) \end{cases}\end{split}\]

Entonces tendremos lo siguiente:

\[\begin{align*} 1 &= 6 - 5\cdot 1 \\ & \\ &= 6 - (17 - 6\cdot 2) \cdot 1 \quad \text{ (sustituyendo la ecuación $2$)} \\ & \\ &= 6\cdot 1 - 17\cdot 1 + 6\cdot 2 \\ & \\ &= 6\cdot 3 - 17\cdot 1 \\ & \\ &= (23 - 17\cdot 1)\cdot 3 - 17\cdot 1 \quad \text{ (sustituyendo la ecuación $3$)} \\ & \\ &= 23\cdot 3 - 17\cdot 3 - 17\cdot 1 \\ & \\ &= 23\cdot 3 - 17\cdot 4 \\ & \\ &= 23\cdot 3 - (63 - 23\cdot 2)\cdot 4 \quad \text{ (sustituyendo la ecuación $4$)} \\ & \\ &= 23\cdot 3 - 63\cdot 4 + 23\cdot 8 \\ & \\ &= 23\cdot 11 - 63\cdot 4. \end{align*}\]

Por lo tanto, la combinación lineal es \(1 = 23\cdot 11 - 63\cdot 4\).

3. Ahora, obtenemos una solución particular.

Multiplicamos ambos lados de la combinación lineal obtenida por \((-7)\).

\[\begin{align*} 23\cdot 11 - 63\cdot 4 &= 1, \\ & \\ 23\cdot 11\cdot (-7) - 63\cdot 4\cdot (-7) &= 1\cdot (-7), \\ & \\ 23\cdot (-77) - 63\cdot (-28) &= -7, \\ & \\ 63\cdot 28 - 23\cdot 77 &= -7. \end{align*}\]

Por lo tanto, la solución particular es \(x_0=28\) y \(y_0=77\).

4. Por último, damos la solución general.

Por el Corolario 3 la solución general está dada por \(x = x_0 + bt = 28 - 23t\) y \(y = y_0 - at = 77 - 63t\), donde \(t\) es un entero arbitrario.

Como vimos en Teorema 9, el algoritmo extendido de Euclides también nos permite expresar el máximo común divisor de dos números como combinación de lineal de éstos. Esto nos da otra manera de encontrar una solución particular de una ecuación diofantina.

Observación 4

Consideremos la ecuación \(ax + by = c\), donde \(a,b,c\) son enteros. Sea \(d = (a,b)\) y supongamos que \(d|c\). Aplicando el Teorema 9 podemos escribir que:

\[as_n + bt_n = d,\]

donde \(s_n\) y \(t_n\) son enteros. Como \(d|c\) tenemos que \(c = d e\), entonces podemos multiplicar la ecuación por \(e\) y tenemos que:

\[ase + bte = de = c.\]

Por lo tanto tendríamos que \(x_0 = se\) y \(y_0 = te\) es una solución particular de la ecuación.

Ejemplo 35

Encuentra una solución particular de la ecuación \(696x + 408y = 48\), usando el algoritmo extendido de Euclides.

Solución.

1. Veamos si la ecuación tiene soluciones enteras.

Aplicando la Observación 2, tenemos que:

\[\begin{align*} 696 &= 408\cdot 1 + 288, \\ & \\ 408 &= 288\cdot 1 + 120, \\ & \\ 288 &= 120\cdot 2 + 48, \\ & \\ 120 &= 48\cdot 2 + 24, \\ & \\ 48 &= 24\cdot 2 + 0. \end{align*}\]

Por lo tanto, tenemos que \((696,408) = 24\), y como \(24|48\) la ecuación \(696x + 408y = 48\) tiene solución.

2. Vamos a aplicar Teorema 9 para encontrar la combinación lineal.

Tenemos que \(r_0 = 696\) y \(r_1 = 408\).

• Para \(j = 0\) y \(j = 1\) tenemos:

\[\begin{align*} s_0 &= 1, &\quad t_0 &= 0, \\ & \\ s_1 &= 0, &\quad t_1 &= 1. \end{align*}\]

• Para \(j = 2\) tenemos:

\[s_2 = s_0 - s_1q_1 = 1-0\cdot 1 = 1, \quad t_2 = t_0 - t_1q_1 = 0 - 1\cdot 1 = -1.\]

• Para \(j = 3\) tenemos:

\[s_3 = s_1 - s_2q_2 = 0-1\cdot 1 = -1, \quad t_3 = t_1 - t_2q_2 = 1 - (-1)\cdot 1 = 2.\]

• Para \(j = 4\) tenemos:

\[s_4 = s_2 - s_3q_3 = 1-(-1)\cdot 2 = 3, \quad t_4 = t_2 - t_3q_3 = -1 - 2\cdot 2 = -5.\]

• Para \(j = 5\) tenemos:

\[s_5 = s_3-s_4q_4 = -1 - 3\cdot 2 = -7, \quad t_5 = t_3 - t_4q_4 = 2 - (-5)\cdot 2 = 12.\]

Por lo tanto tenemos que:

\[\begin{align*} r_5 &= s_5a + t_5b, \\ & \\ 24 &= (-7)\cdot 696 + 12\cdot 408. \end{align*}\]

3. Por último damos la solución particular.

Como \(24|48\) tenemos que \(48 = 24\cdot 2\), entonces multiplicamos la combinación lineal por \(2\) y obtenemos que,

\[\begin{align*} 24 &= -7\cdot 696 + 12\cdot 408, \\ & \\ 2\cdot 24 &= 2\cdot (-7)\cdot 696 + 2\cdot 12\cdot 408, \\ & \\ 48 &= 696\cdot (-14) + 408\cdot 24. \end{align*}\]

Así, \(x_0 = -14\) y \(y_0 = 24\) es una solución particular.

Por último, veremos un método ideado por Euler para resolver ecuaciones diofantinas lineales empleando el algoritmo de la división. Veamos cómo funciona a través de un ejemplo.

Ejemplo 36

Resuelve la ecuación lineal diofantina \(1076x + 2076y = 3076\) utilizando el método de Euler.

Solución.

Ya que \((1076,2076) = 4\) y \(4|3076\), la ecuación tiene solución.
El método de Euler involucra la solución para la variable con el coeficiente más pequeño, en este caso sería \(x\). Entonces despejamos la variable \(x\) de la ecuación,

\[x = \frac{-2076y+3076}{1076},\]

bajo operaciones algebraicas en el lado derecho tendremos que,

\[\begin{align*} x &= \frac{-1076y -1000y + 2152+ 924}{1076} \\ & \\ &= \frac{-1076y + 2152 + (-1000y + 924)}{1076} \\ & \\ &= \frac{-1076y}{1076} + \frac{2152}{1076} + \frac{-1000y + 924}{1076} \\ & \\ &= -y + 2 + \frac{-1000y+924}{1076}. \end{align*}\]

Luego, sea

\[u = \frac{-1000y+924}{1076}.\]

Por el Teorema 3 tenemos que el residuo \(u\) es entero. Así, obtenemos la ecuación diofantina lineal \(1076u+1000y=924\), la cual tiene coeficientes más pequeños que la original.

Vamos a repetir el proceso, despejamos la variable con el coeficiente más pequeño, en este caso es \(y\). Entonces tendremos lo siguiente,

\[y = \frac{-1076u+924}{1000},\]

nuevamente bajo operaciones algebraicas,

\[\begin{align*} y &= \frac{-1000u -76u + 924}{1000} \\ & \\ &= \frac{-1000u + (-76u + 924)}{1000} \\ & \\ &= \frac{-1000u}{1000} + \frac{-76u + 924}{1000} \\ & \\ &= -u + \frac{-76u + 924}{1000}. \end{align*}\]

Ahora, haremos

\[v = \frac{-76u + 924}{1000}.\]

Así, obtenemos la ecuación \(76u + 1000v = 924\). Siguiendo con la idea, ahora la variable con coeficiente más chico es \(u\) y tendremos lo siguiente,

\[\begin{align*} u &= \frac{-1000v + 924}{76} \\ & \\ &= \frac{-988v -12v + 912 + 12}{76} \\ & \\ &= \frac{-988v + 912 + (-12u + 12)}{76} \\ & \\ &= \frac{-988v}{76} + \frac{912}{76} + \frac{-12v + 12}{76} \\ & \\ &= -13v + 12 + \frac{-12v + 12}{76}. \end{align*}\]

Como última iteración, haremos

\[w = \frac{-12v + 12}{76},\]

para obtener \(12v + 76w = 12\). Como la variable con coeficiente más chico es \(v\), tendremos lo siguiente,

\[\begin{align*} v &= \frac{-76w + 12}{12} \\ & \\ &= \frac{-72w -4w + 12}{12} \\ & \\ &= \frac{-72w + 12 + (-4w)}{12} \\ & \\ &= \frac{-72w}{12} + \frac{12}{12} + \frac{-4w}{12} \\ & \\ &= -6w + 1 + \frac{-4w}{12} \\ & \\ &= -6w + 1 - \frac{w}{3}. \end{align*}\]

Por el Teorema 3 tenemos que el residuo \(\frac{w}{3}\), debe ser entero, por lo tanto podemos igualarlo a un entero \(t\), teniendo que \(\frac{w}{3}=t\).

Para obtener una solución particular hacemos \(t=0\), entonces tendríamos que:

\[w = 3t = 3 \cdot 0 = 0.\]

Como \(w = 0\), podemos sustituirlo para encontrar \(v\),

\[v = -6w + 1 - \frac{w}{3} = -6\cdot 0 + 1 - 0 = 1.\]

Como \(v=1\), podemos encontrar el valor de \(u\),

\[u = \frac{-1000v + 924}{76} = \frac{-1000\cdot 1 + 924}{76} = \frac{-76}{76} = -1.\]

Como \(u = -1\), podemos encontrar el valor de \(y\),

\[y = \frac{-1076u + 924}{1000} = \frac{-1076\cdot (-1) + 924}{1000} = \frac{2000}{1000} = 2.\]

Por último, como \(y = 2\), entonces encontramos \(x\),

\[x = \frac{-2076y + 3076}{1076} = \frac{-2076\cdot 2 + 3076}{1076} = \frac{-1076}{1076} = -1.\]

Finalmente, obtuvimos una solución particular \(x_0 = -1\) y \(y_0=2\).
Por lo tanto, tenemos que:

\[1076(-1)+2076(2)=3076.\]

Para encontrar la solución general, como \(t\) es un entero arbitrario, sustituimos en orden inverso las ecuaciones, entonces tendremos lo siguiente,

\[\begin{align*} w &= 3t, \\ & \\ v &= -6w + 1 - \frac{w}{3} = -6(3t) + 1 - \frac{3(3t)}{3} = -19t + 1, \\ & \\ u &= -13v + 12 + w = -13(-19t + 1) + 12 + (3t) = 250t - 1, \\ & \\ y &= -u + v = -(250t - 1) + (-19t + 1) = -269t + 2, \\ & \\ x &= -y + 2 + u = -(-269t + 2) + 2 + (250t - 1) = 519t - 1. \end{align*}\]

Así, la solución general es \(x = 519t - 1\) y \(y = -269t + 2\).

Código para encontrar una solución particular de una ecuación diofantina de la forma \(ax + by = c\)

A lo largo de la notas vamos a utilizar códigos realizados en secciones anteriores, en algunas ocasiones necesitaremos hacer cambios a estos códigos, como cambiar el valor de la salida que nos arrojan entre otras cosas. Estos cambios serán explicados en la sección de explicación del código.

En esta ocasión usaremos la función que construimos para escribir el máximo común divisor de \(a\) y \(b\) como una combinación lineal de \(a\) y \(b\) utilizando el algoritmo extendido de Euclides.

def euclides_extendido_ciclos(a,b):
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return s[-2],t[-2],a

El siguiente código nos ayudará a resolver ecuaciones lineales diofantinas de la forma \(ax + by = c\). Además, si la ecuación tiene solución, nos arrojará una solución particular.

def diofantina_2_variables(a,b,c):
    s,t,mcd = euclides_extendido_ciclos(a,b)

    if c % mcd != 0:
        print(f"No hay solución entera para la ecuación: {a}x + {b}y = {c}")
    else: 
        x_0 = (s * (c // mcd))
        y_0 = (t * (c // mcd))
        print(f"Una solución particular de la ecuación {a}x + {b}y = {c} es x = {x_0}, y = {y_0}")    

diofantina_2_variables(6,8,25)

No hay solución entera para la ecuación: 6x + 8y = 25

diofantina_2_variables(12,18,30)

Una solución particular de la ecuación 12x + 18y = 30 es x = -5, y = 5

diofantina_2_variables(63,-23,-7)

Una solución particular de la ecuación 63x + -23y = -7 es x = 28, y = 77

Ecuaciones diofantinas lineales en más de dos variables

El siguiente resultado nos muestra que podemos extender la idea del Teorema 10 a ecuaciones diofantinas que contengan tres o más variables.

Teorema 11

Si \(a_1, a_2, \ldots, a_n\) son enteros positivos distintos de cero, entonces la ecuación

\[a_1x_1 + a_2x_2 + \ldots + a_nx_n = c\]

tiene solución si y sólo si \(d = (a_1, a_2, \ldots, a_n)|c\).

Demostración. Vamos a demostrar las dos implicaciones.

• Primero veamos que si \(a_1x_1 + a_2x_2 + \ldots + a_nx_n = c\) tiene solución, entonces \(d|c\).

Supongamos que \(x_i = \beta_i\) para \(i = 1, 2, \ldots, n\) es una solución, entonces tendríamos que satisface la ecuación

\[a_1\beta_1 + a_2\beta_2 + \ldots + a_n\beta_n = c.\]

Ya que \(d = (a_1, a_2, \ldots, a_n)\), tenemos que \(d|a_i\) para cada \(i\). Luego, extendiendo la idea de la propiedad \(4\) de la Proposición 2 por inducción, tenemos que \(d|(a_1\beta_1 + a_2\beta_2 + \ldots + a_n\beta_n)\) y por lo tanto \(d|c\).

• Ahora veamos que si \(d|c\), entonces la ecuación \(a_1x_1 + a_2x_2 + \ldots + a_nx_n = c\) tiene solución.

Procedamos por inducción sobre el número de variables.

Base inductiva. Cuando \(n = 2\) tenemos que si \(d|c\) la ecuación \(ax + by = c\) tiene solución. Notemos que por el Teorema 10 lo anterior es cierto.

Hipótesis inductiva. Supongamos que si \(d|c\), la ecuación \(a_1x_1 + a_2x_2 + \ldots + a_nx_n = c\) tiene solución.

Paso inductivo. Ahora, vamos a probar que si \(d|c\), la ecuación \(a_1x_1 + a_2x_2 + \ldots + a_nx_n + a_{n+1}x_{n+1} = c\) tiene solución.

Por el Teorema 7 tenemos que,

\[d = (a_1,a_2, \ldots, a_{n+1}) = ((a_1,a_2, \ldots, a_n),a_{n+1}) = (d',a_{n+1}).\]

Entonces existen \(s'\) y \(t'\) tales que,

\[d's' + a_{n+1}t' = d.\]

Por la hipótesis inductiva tenemos que existen \(s_i\) para \(i = 1,2,\ldots, n\), tales que

\[d' = (a_1,a_2, \ldots, a_n) = a_1s_1 + a_2s_2 + \ldots + a_ns_n.\]

Sustituyendo la hipótesis inductiva tenemos lo siguiente,

\[\begin{align*} d's' + a_{n+1}t' &= d, \\ & \\ (a_1s_1 + a_2s_2 + \ldots + a_ns_n)s' + a_{n+1}t' &= d, \\ & \\ a_1s_1s' + a_2s_2s' + \ldots + a_ns_ns' + a_{n+1}t' &= d. \end{align*}\]

Luego, como \(d|c\) tenemos que \(c = de\) para algún entero \(e\), entonces multiplicando la ecuación por \(e\) obtenemos que,

\[\begin{align*} a_1s_1s'e + a_2s_2s'e + \ldots + a_ns_ns'e + a_{n+1}t'e &= de, \\ & \\ a_1(s_1s'e) + a_2(s_2s'e) + \ldots + a_n(s_ns'e) + a_{n+1}(t'e) &= c. \\ \end{align*}\]

Por la tanto, la ecuación con \(n+1\) variables tiene solución, esta es \(x_i = s_is'e\) para \(i = 1,2,\ldots, n\) y \(x_{n+1} = t'e\). \(\square\)

Ejemplo 37

Determina si la ecuación lineal diofantina \(6x+8y+12z=10\) tiene solución y encuentra su solución general.

Solución.

Ya que \((6,8,12) = 2\) y \(2|10\) la ecuación tiene solución.

Ahora, para encontrar la solución general hagamos lo siguiente.

Sabemos que \(8y + 12z\) es una combinación lineal de \(8\) y \(12\), entonces podríamos formar una ecuación en donde el lado izquierdo de esta sea la combinación lineal \(8y + 12z\) y el lado derecho un múltiplo de \((8,12) = 4\), es decir que,

\[8y + 12z = 4u.\]

Teniendo lo anterior, podemos sustituirlo en la ecuación original obteniendo la siguiente ecuación lineal diofantina en dos variables,

\[6x + 4u = 10.\]

Notemos que \((6,4) = 2\), entonces esta ecuación tiene solución ya que \(2|10\). Ahora, encontremos una solución para esta ecuación.

Por el algoritmo de Euclides, tenemos que

\[6 = 4\cdot 1 + 2,\]

entonces, la combinación lineal es

\[6\cdot 1 + 4\cdot (-1) = 2.\]

Multiplicamos todos los términos de la ecuación por \(5\), obteniendo que

\[\begin{align*} 6\cdot 1\cdot 5 + 4\cdot (-1)\cdot 5 = 2\cdot 5, \\ & \\ 6\cdot 5 + 4\cdot (-5) = 10. \end{align*}\]

Podemos ver que una solución particular es \(x_0 = 5 \) y \(u_0 = -5\), y su solución general es \(x = x_0 + \left( \frac{b}{d} \right)t = 5 + 2t\) y \(u = u_0 - \left( \frac{a}{d} \right)t = -5 -3t\), en donde \(t\) es un entero arbitrario.

Si sustituimos \(u\) en \(8y + 12z = 4u\) tendríamos que \(8y+12z = 4(-5-3t)\). Por otro lado, como \((8,12) = 4\) podemos escribir esto como una combinación lineal de \(12\) y \(8\), entonces tendremos que

\[8\cdot (-1) + 12\cdot 1 = 4.\]

Si multiplicamos esta ecuación por \(u\), tenemos que

\[8 \cdot (-1)\cdot u + 12 \cdot 1\cdot u = 4\cdot u.\]

Sustituyendo \(u = -5 -3t\) obtendríamos que,

\[\begin{align*} 8 \cdot (-1)\cdot (-5 -3t) + 12 \cdot 1\cdot (-5 -3t) &= 4\cdot (-5 -3t), \\ & \\ 8\cdot (5 + 3t) + 12\cdot (-5 -3t) &= 4\cdot (-5 -3t). \end{align*}\]

Entonces, una solución particular para la ecuación \(8y + 12z = 4u\), es

\[y_0 = 5 + 3t, \quad z_0 = -5 -3t.\]

Y la solución general sería,

\[y = y_0 + \left( \frac{b}{d} \right) t'= 5 + 3t + 3t', \quad z = z_0 - \left( \frac{a}{d} \right) t' = -5 -3t -2t',\]

donde \(t'\) es un entero arbitrario.

Por lo tanto, la solución general a la ecuación diofantina \(6x + 8y + 12z = 10\) es:

\[\begin{align*} x &= 5 + 2t, \\ & \\ y &= 5 + 3t + 3t', \\ & \\ z &= -5 -3t -2t'. \end{align*}\]

Código para encontrar una solución particular de una ecuación diofantina de la forma \(a_1x + a_2y + a_3z = c\)

Vamos a utilizar la función que construimos para calcular el máximo común divisor utilizando el algoritmo de Euclides.

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return b

El siguiente código nos ayudará a calcular el máximo común divisor de \(2\) o más números enteros.

def mcd_n_numeros(lista):
    lista_1 = lista.copy()
    while len(lista_1) != 1: 
        mcd = algoritmo_euclides(lista_1[0],lista_1[1])
        del lista_1[0:2]
        lista_1 = [mcd] + lista_1
    return lista_1[0]

mcd_n_numeros([6,8])

2

mcd_n_numeros([3,6,9])

3

mcd_n_numeros([12,36,60,108])

12

También utilizaremos las funciones «euclides_extendido_ciclos» y «diofantina_2_variables» para resolver una ecuación diofantina de tres variables. Una de las ventajas de trabajar en el entorno de Jupyter Notebook es que, al ejecutar el código en celdas anteriores, este permanece disponible para su uso posterior. Por ello, no es necesario volver a escribir la función, ya que podemos reutilizarla aunque el código se encuentre en celdas previas. Sin embargo, debemos asegurarnos de que las celdas anteriores hayan sido ejecutadas correctamente para que las funciones estén disponibles.

El siguiente código nos ayudará a resolver ecuaciones diofantinas lineales de la forma \(a_1x + a_2y + a_3z = c\). Si la ecuación tiene solución nos arrojará una solución particular, en caso contrario nos dirá que la ecuación no tiene solución.

def diofantina_3_variables(lista,c):
    mcd = mcd_n_numeros(lista)
    if c % mcd != 0:
        print(f"La ecuación no tiene solución ya que {lista[0],lista[1],lista[2]} = {mcd} no divide a {c}")
    else: 
        mcd_1 = mcd_n_numeros(lista[0:2])
        u_1,z = diofantina_2_variables(mcd_1,lista[2],c)
        x,y = diofantina_2_variables(lista[0],lista[1],mcd_1*u_1)
        print(f"La solución a la ecuación {lista[0]}x + {lista[1]}y + {lista[2]}z = {c} es x = {x} , y = {y} , z = {z}")

diofantina_3_variables([6,7,12],10)

La solución a la ecuación 6x + 7y + 12z = 10 es x = -10 , y = 10 , z = 0

diofantina_3_variables([21,3,4],5)

La solución a la ecuación 21x + 3y + 4z = 5 es x = 0 , y = -5 , z = 5

diofantina_3_variables([7,21,35],8)

La ecuación no tiene solución ya que (7, 21, 35) = 7 no divide a 8

diofantina_3_variables([98,107,57],45)

La solución a la ecuación 98x + 107y + 57z = 45 es x = -540 , y = 495 , z = 0

Explicación del código

En esta ocasión reutilizamos códigos creados en secciones anteriores, pero los modificamos. Lo que nos interesa de los códigos es su valor de salida. Es decir, en lugar de que nos muestre información detallada, sólo queremos obtener los valores calculados. Mostraremos los códigos originales y la modificación que se les hizo.

Código original.

def euclides_extendido_ciclos(a,b):
    num1 = a
    num2 = b
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return print(f"La combinación lineal de {num1} y {num2} es: {num1}({s[-2]}) + {num2}({t[-2]}) = {a}")

Código modificado.

def euclides_extendido_ciclos(a,b):
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return s[-2],t[-2],a

Eliminamos algunas variables «num1» y «num2» ya que no necesitábamos guardar el valor de \(a\) y \(b\).
Modificamos el valor de salida de la función, anteriormente regresaba un texto que nos decía cual era la combinación lineal, el código modificado solamente nos regresa los coeficientes de la combinación lineal y el máximo común divisor en una tupla.

En Python, una tupla es una estructura de datos que se utiliza para almacenar una colección ordenada de elementos. Es similar a una lista, pero a diferencia de las listas, las tuplas son inmutables, lo que significa que una vez que se crean, no se pueden modificar.

Código original.

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        print(a,"=",b,"x",a//b,"+",a%b)
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return print("El máximo común divisor es: ",b)

Código modificado.

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return b

Eliminamos la función print() dentro del bucle while, la cual nos iba mostrando en cada iteración las divisiones realizadas.
Modificamos el valor de salida de la función, eliminando el texto y dejando únicamente el valor del máximo común divisor.

Ahora, veamos los comandos nuevos utilizados en este capítulo.
En este capítulo vimos un nuevo método para las listas, lista.copy(). Esto nos sirve si queremos crear una copia de la lista original y así ésta no se vea afectada a modificaciones en nuestros códigos.

lista_original = [1,2,3,4,5]  

lista_copia = lista_original.copy()

También usamos la función len() la cual recibe como argumento una lista. Es una función que se utiliza para obtener la longitud de una lista. La longitud de una lista es simplemente el número de elementos que contiene.

mi_lista = [1, 2, 3, 4, 5]

longitud = len(mi_lista)

En el ejemplo anterior la variable «longitud» nos diría que la lista contiene \(5\) elementos.

En Python podemos sumar listas con el operador +. Este operador concatena dos listas, creando una nueva lista que contiene todos los elementos de ambas listas en el orden en que se proporcionan.

lista_1 = [1,2,3,4]  

lista_2 = [5,6,7,8]  

suma_1 = lista_1 + lista_2

suma_2 = lista_2 + lista_1

En el ejemplo anterior el valor de la variable «suma_1» sería una nueva lista con los elementos \([1,2,3,4,5,6,7,8]\) y el valor de la variable «suma_2» sería \([5,6,7,8,1,2,3,4]\).

Otra forma de seleccionar elemento de una lista es el slicing, es una técnica en Python que nos permite seleccionar una parte específica de una lista utilizando un rango de índices. Esto nos permite extraer subconjuntos de la secuencia según nuestras necesidades. La sintaxis sería nombre_de_la_lista[inicio:fin], debemos tomar en cuenta que el índice final es excluido del subconjunto de la lista que se toma.

lista = [1,2,3,4,5,6,7,8,]

sub_lista = lista[1:6]

En el ejemplo anterior el valor de la variable «sub_lista» tiene como resultado una lista con los elementos \([2,3,4,5,6]\).

Ahora, veamos cómo funcionan los nuevos códigos creados para este capítulo.

Primero, veamos el código para resolver ecuaciones diofantinas lineales en dos variables.

def diofantina_2_variables(a,b,c):
    s,t,mcd = euclides_extendido_ciclos(a,b)
    if c % mcd != 0:
        print(f"No hay solución entera para la ecuación: {a}x + {b}y = {c}")
    else: 
        x_0 = (s * (c // mcd))
        y_0 = (t * (c // mcd))
        print(f"Una solución particular de la ecuación {a}x + {b}y = {c} es x = {x_0}, y = {y_0}")    

1. Creamos una función llamada «diofantina_2_variables» la cual recibe como argumento los coeficientes \(a, b\) y \(c\) de la ecuación diofantina \(ax + by = c\).

def diofantina_2_variables(a,b,c):

2. Aplicamos la función «euclides_extendido_ciclos» para calcular los coeficientes de la combinación lineal del máximo común divisor de \(a\) y \(b\) en términos de los valores \(a\) y \(b\). La función nos devuelve 3 valores y los asignamos a las variables «s»,»t» y «mcd».

    s,t,mcd = euclides_extendido_ciclos(a,b)  

3. Luego pasa a los condicionales if y else. En esta parte del código se comprueba si la ecuación tiene solución usando el Teorema 10.
   En caso de que la condición en el condicional if sea verdadera, es decir, que el residuo de dividir \(c\) entre la variable \(mcd\) sea diferente de cero, el código nos dirá que no hay solución para la ecuación \(ax + by = c\). En caso contrario el código pasa al condicional else en el cual el código calcula las soluciones particulares de la ecuación y nos muestra cuáles son.

    if c % mcd != 0:
        print(f"No hay solución entera para la ecuación: {a}x + {b}y = {c}")
    else: 
        x_0 = (s * (c // mcd))
        y_0 = (t * (c // mcd))
        print(f"Una solución particular de la ecuación {a}x + {b}y = {c} es x = {x_0}, y = {y_0}")  

Para el segundo código creamos primero una función que calculara el máximo común divisor de dos o más números y así poder utilizar el Teorema 11 para comprobar si la ecuación diofantina en \(3\) variables \(a_1x + a_2y + a_3z = c\) tiene solución.
Luego, modificamos la salida de la función «diofantina_2_variables» para que sólo nos regrese dos valores, las soluciones de una ecuación diofantina en \(2\) variables.

Expliquemos cómo funciona el código para calcular el máximo común divisor de \(2\) o mas números.

def mcd_n_numeros(lista):
    lista_1 = lista.copy()
    while len(lista_1) != 1: 
        mcd = algoritmo_euclides(lista_1[0],lista_1[1])
        del lista_1[0:2]
        lista_1 = [mcd] + lista_1
    return lista_1[0]

1. Creamos una función llamada «mcd_n_numeros» que recibe como argumento una lista con números enteros. La lista debe contener \(2\) o más elementos.

def mcd_n_numeros(lista):

2. Luego creamos una variable llamada «lista_1», la cual es una copia de la lista que se pasa como argumento a la función. Esta copia nos servirá para no modificar la lista original dada.

    lista_1 = lista.copy()

3. Iniciamos un ciclo while el cual repite el bloque de código dentro de él, siempre y cuando se cumpla la condición de que la longitud de la lista sea diferente de \(1\).

    while len(lista_1) != 1: 

4. Lo que hace el ciclo es calcular el máximo común divisor de todos los números dentro de la lista y para ello usamos el Teorema 7, el código hace lo siguiente.
   Supongamos que tenemos la lista \([a_1,a_2,a_3, \ldots, a_n]\), entonces el código calcula el máximo común divisor de \(a_1\) y \(a_2\), luego elimina a \(a_1,a_2\) de la lista y agrega al inicio de la lista la variable «mcd». Luego, se vuelve a repetir el proceso, es decir, toma los primeros dos elementos de la lista, calcula su máximo común divisor, los elimina de la lista y agrega el máximo común divisor de estos dos números al inicio de la lista. El proceso se repite hasta que la lista contenga 1 elemento el cual será el máximo común divisor de todos los números de la lista. Finalmente, el valor de salida de la función es el único elemento de la lista.

        mcd = algoritmo_euclides(lista_1[0],lista_1[1])
        del lista_1[0:2]
        lista_1 = [mcd] + lista_1
    return lista_1[0]

Por último, veamos el código que nos ayuda a resolver ecuaciones diofantinas lineales en \(3\) variables.

def diofantina_3_variables(lista,c):
    mcd = mcd_n_numeros(lista)
    if c % mcd != 0:
        print(f"La ecuación no tiene solución ya que {lista[0],lista[1],lista[2]} = {mcd} no divide a {c}")
    else: 
        mcd_1 = mcd_n_numeros(lista[0:2])
        u_1,z = diofantina_2_variables(mcd_1,lista[2],c)
        x,y = diofantina_2_variables(lista[0],lista[1],mcd_1*u_1)
        print(f"La solución a la ecuación {lista[0]}x + {lista[1]}y + {lista[2]}z = {c} es x = {x} , y = {y} , z = {z}")

1. Creamos una función llamada «diofantina_3_variables» la cual recibe como primer argumento una lista con los coeficientes \(a_1, a_2, a_3\) de la ecuación diofantina lineal \(a_1x_1 + a_2x_2 + a_3x_3 = c\) y como segundo argumento recibe el valor de \(c\).

def diofantina_3_variables(lista,c):

2. Luego, creamos una variable llamada «mcd», la cual nos sirve para guardar el valor del máximo común divisor de los números de la lista.

    mcd = mcd_n_numeros(lista)

3. Después, pasa a los condicionales if y else.
   En esta parte del código comprobamos si la ecuación tiene solución usando el Teorema 11. En caso de que la condición dentro del condicional if sea verdadera, es decir que, el residuo al dividir \(c\) entre \(mcd\) sea diferente de cero, el código nos dirá que la ecuación no tiene solución.

    if c % mcd != 0:
        print(f"La ecuación no tiene solución ya que {lista[0],lista[1],lista[2]} = {mcd} no divide a {c}")

4. Si la condición if fue falsa, el código pasa al condicional else. En este caso se sigue la idea de la demostración del Teorema 11. El código calcula el máximo común divisor de los primeros dos números de la lista, es decir, \((a_1, a_2) = d\) para poder reducir la ecuación de tres variables \(a_1x_1 + a_2x_2 + a_3x_3 = c\), a dos variables \(du + a_3x_3 = c\), haciendo \(a_1x_1 + a_2x_2 = du\).
   Luego, calcula las soluciones \(u\) y \(x_3\) con la función «diofantina_2_variables». Con el valor de \(u\) obtenido procede a resolver la ecuación de dos variables \(a_1x_1 + a_2x_2 = du\), encontrando el valor de \(x_1\) y \(x_2\). Luego, como salida nos imprime la ecuación y la solución que obtuvo.

    else: 
        mcd_1 = mcd_n_numeros(lista[0:2])
        u_1,z = diofantina_2_variables(mcd_1,lista[2],c)
        x,y = diofantina_2_variables(lista[0],lista[1],mcd_1*u_1)
        print(f"La solución a la ecuación {lista[0]}x + {lista[1]}y + {lista[2]}z = {c} son x = {x} , y = {y} , z = {z}")

Ejercicios de práctica

1. Determina si las siguientes ecuaciones diofantinas de dos variables son solubles, si lo son, encuentra la solución general.

   • \(12x+16y=18\).

   • \(12x+13y=14\).

   • \(28x+91y=119\).

   • \(1776x+1976y=4152\).

2. Determina si las siguientes ecuaciones diofantinas de tres variables son solubles, si lo son, encuentra la solución general.

   • \(2x+3y+4z=5\).

   • \(6x+12y-15z=33\).

   • \(8x+10y+16z=25\).

   • \(12x+30y-42z=66\).

3. Demuestra el Corolario 3.

4. Demuestra que \(ax+by = c\) tiene solución \((x,y)\) si y sólo si \(ax -by = c\) tiene solución \((x,-y)\).

5. Sean \(a\) y \(b\) primos relativos positivos, y sea \(n\) un entero positivo. Una solución \((x,y)\) de la ecuación lineal diofantina \(ax + by = n\) es no negativa cuando \(x\) y \(y\) son no negativos.
   Demuestra que si \(n = ab - a - b\), entonces no hay soluciones no negativas de la ecuación \(ax + by = n\).