Resolución de un problema de números enteros que pasa por resolver una ecuación diofántica lineal

En otro artículo de este blog resolví una ecuación diofántica lineal mediante un procedimiento muy básico, sin utilizar el método habitual, llamémosle estándar, basado en el lema de Bézout (también conocido como identidad de Bézout). Ahora voy a resolver el mismo problema, empleando este procedimiento estándar. El problema era el siguiente:

Se nos informa de que dos equipos, $X$ e $Y$, (del deporte que queráis imaginar) han jugado un conjunto de partidos, de tal manera que el doble de los partidos ganados por $X$ más el número de partidos ganados por $Y$ es igual a $12$. ¿Cuáles son las maneras (resultados) en que tal cosa ha podido acontecer?.

-oOo-

Recordemos sucintamente, primero, en qué consiste —en otros artículos de este mismo blog ya he trato este asunto— este procedimiento estándar. Sea la ecuación diofántica lineal $ax+by=c\; a,b\in \mathbb{Z}$, entonces existe solución, esto es, un conjunto de parejas de números enteros $(x,y)$ que satisfacen dicha ecuación, si y sólo si el máximo común divisor de los coeficientes $a$ y $b$, $\text{m.c.d}(a,b)$ (que denotaremos de manera abreviada por $d$), es divisor del coeficiente $c$ (el resto de la división entera $d\div c$ es $0$), lo cual se suele denotar por $d|c$.

Si existiese solución, para encontrar el conjunto de pares $(x,y)$ de números enteros que la conforman, se procede primero a encontrar una pareja cualesquiera que satisfaga la igualdad numérica expresada en la ecuación (esta pareja de números es pues una solución particular, y la denotaremos por $(x_P,y_P)$; y, a continuación, encontramos las otras parejas de la siguiente forma $$\left\{\begin{matrix}x=x_P+\lambda\cdot \dfrac{b}{d} \\ y=y_P-\lambda\cdot \dfrac{a}{d} \end{matrix}\right.\; \text{donde}\, \lambda \in \mathbb{Z}$$ que constituyen la solución general.

-oOo-

Procedo, pues. La ecuación diofántica lineal que hay que resolver es $2x+y=12$. Los coeficientes de la ecuación son $a=2$ y $b=1$. Parto de una solución particular, pongamos que de la pareja formada por $x_P=5$ e $y_P=2$ —cumple la igualdad $2x+y=12$; en efecto: $2\cdot 5 +2 = 12$—, que, como he anunciado, denoto de la forma $(5,12)$. Por otra parte el máximo común divisor de los coeficientes $a=2$ y $b=1$ es, $d=1$. Así pues, las otras parejas han de ser de la forma: $$\left\{\begin{matrix}x=5+\lambda\cdot \dfrac{1}{1}=5+\lambda \\ y=2-\lambda\cdot \dfrac{2}{1}=2-2\lambda \end{matrix}\right.\; \text{donde}\, \lambda \in \mathbb{Z}$$ Teniendo en cuenta el sentido «físico» de la solución, es claro que no todo valor de $\lambda \in \mathbb{Z}$ (hay infinitos, por supuesto) proporciona una pareja que forme parte de la solución. Hay que ir probando valores consistentes con la naturaleza de la solución. Así pues, voy a ir dando valores al parámetro $\lambda$ para así ir encontrando el resto de parejas. Es conveniente empezar a probar valores de $\lambda$ pequeños (en valor absoluto) y ir aumento incrementándolos/decrementándolos según proceda:

• Si $\lambda=0$, entonces $x=5+0=5$ y $y=2-2\cdot 0=2-0=2$, esto es obtenemos la pareja $(5,2)$ como parte de la solución general.
• Si $\lambda=1$, entonces $x=5+1=6$ y $y=2-2\cdot 1=0$, esto es obtenemos la pareja $(6,0)$ como parte de la solución general.
• Si $\lambda=-1$, entonces $x=5+(-1)=4$ y $y=2-2\cdot (-1)=4$, esto es obtenemos la pareja $(4,4)$ como parte de la solución general.
• Si $\lambda=2$, entonces $x=5+2=7$ y $y=2-2\cdot 2=-2\lt 0$, que no tiene sentido en nuestro problema, y por tanto este valor de $\lambda$ no aporta nada a la solución, como tampoco lo hacen (por la misma razón) los valores de $\lambda$ mayores que $2$
• Si $\lambda=-2$, entonces $x=5+(-2)=3$ y $y=2-2\cdot (-2)=6$, esto es obtenemos la pareja $(3,6)$ como parte de la solución general.
• Si $\lambda=-3$, entonces $x=5+(-3)=2$ y $y=2-2\cdot (-3)=8$, esto es obtenemos la pareja $(2,8)$ como parte de la solución general.
• Si $\lambda=-4$, entonces $x=5+(-4)=1$ y $y=2-2\cdot (-4)=10$, esto es obtenemos la pareja $(1,10)$ como parte de la solución general.
• Si $\lambda=-5$, entonces $x=5+(-5)=0$ y $y=2-2\cdot (-5)=12$, esto es obtenemos la pareja $(0,12)$ como parte de la solución general.
• Si $\lambda=-6$, entonces $x=5+(-6)\lt 1$ y por tanto este valor de $\lambda$ no aporta nada a la solución, como tampoco lo hacen (por la misma razón) los valores de $\lambda$ menores que $-6$. Y, aquí, terminamos.

En conclusión, la solución de la ecuación diofántica propuesta está formada por las siguientes parejas de números $(x,y)$, enteros no negativos: $$\{(5,2),(6,0),(4,4),(3,6),(2,8),(1,10),(0,12)\}$$

$\diamond$

-oOo-

Referencias

[1] E. Bujalance, et. al, Elementos de matemática discreta (3ª edición), Sanz y Torres, Madrid, 2005

Un caso sencillo de ecuación diofántica lineal, resuelta sin utilizar la identiad de Bézout

En este artículo expongo la resolución de un problema que consiste en resolver una sencilla ecuación con coeficientes enteros cuyas solución debe estar en el conjunto de los números enteros (ecuación diofántica), que, en este caso en particular han de ser no negativos. Y dice así:

Se nos informa de que dos equipos, $X$ e $Y$, (del deporte que queráis imaginar) han jugado un conjunto de partidos, de tal manera que el doble de los partidos ganados por $X$ más el número de partidos ganados por $Y$ es igual a $12$. ¿Cuáles son las maneras (resultados) en que tal cosa ha podido acontecer?.

Escribo primero la ecuación pertinente, de acuerdo con la información del enunciado: $$2x+y=12$$ Desde luego, habrá la solución de dicha ecuación estará formada por más de una pareja de números enteros no negativos — como valores de las variables (incógnitas)—, que denoto por $(x,y)$, y que, al sustituirlos en la ecuación, cumplirán la igualdad numérica entre los dos miembros de la misma, razón por la cual, esta ecuación hay que resolverla en el conjunto de los números naturales, con el añadido del número $0$. Podemos decir, por ello, que es una ecuación diofántica, si bien muy sencilla. Tendremos que contemplar tres casos, que debemos examinar:

1. Caso en que $a=b$
     Entonces, la ecuación pasa a ser $2x+x=12$, y por tanto, $3x=12$, de la cual se obtiene que $x=4$ y, por supuesto, $y=4$. Así, tenemos que en la solución está la pareja $(4,4)$
2. Caso en que $x\gt y$
     Siendo así, $12=2x+y\lt 2x+x$, es decir $3x \gt 12$ y, por tanto, $x \gt 4$; por otra parte, al ser $y\gt 0$, se tiene que $2x\le 12$, luego $x\le 6$. Entonces, los posibles valores de $x$ que aportan solución son tales que $4\lt x \le 6$. Dicho de otro modo, los valores que, en principio, puede tomar $x$ ante esa posibilidad son: $\{5,6\}$. Examino a continuación, qué valores de $y$ corresponden a cada uno de éstos (a partir del despeje de $b$ en la ecuación: $y=12-2x$):
   • Si $x=5$, entonces $y=12-2\cdot 5=12-10=2$, luego $(5,2)$ forma parate de la solución
   • Si $x=6$, entonces $y=12-2\cdot 6=12-12=0$, luego otra pareja que forma parte de la solución es $(6,0)$
   • Si $x=7$, entonces $y=12-2\cdot 7=12-14=-2 \notin \mathbb{N} \cup \{0\} $, por lo que este valor de $x$ no aporta nada a la solución
   Observación: Obviamente, como ya se ha avanzado, si $x \gt 7$, se obtienen números negativos para $y$.
3. Caso en que $y\gt x$
     Siendo así, $12=2x+y \lt 2y+y=3y$, es decir $3y \gt 12$ y, por tanto, $y \gt 4$; y, como, por otra parte, $y\le 12$, los valores posibles son tales que $4 \lt y \le 12$; dicho de otro modo, los valores a examinar que puede tomar $x$ ante esa posibilidad son: $\{5,6,7,8,9,19,11,12\}$. A continuación, voy a examinar de dicho conjunto dan valores de $x$ que sean consistentes, a partir del despeje de $x$ en la ecuación: $x=\dfrac{12-y}{2}$:
   • Si $y=5$, entonces $x=\dfrac{12-5}{2}=\dfrac{7}{2} \notin \mathbb{N}\cup \{0\}$, por lo que este valor no aporta nada a la solución
   • Si $y=6$, entonces $x=\dfrac{12-6}{2}=\dfrac{6}{2}=3 \in \mathbb{N}\cup \{0\}$, luego $(3,6)$ forma parte de la solución
   • Si $y=7$, entonces $x=\dfrac{12-7}{2}=\dfrac{5}{2} \notin \mathbb{N}\cup \{0\}$, por lo que este valor no aporta nada a la solución
   • Si $y=8$, entonces $x=\dfrac{12-8}{2}=\dfrac{4}{2}=2 \in \mathbb{N}\cup \{0\}$, luego $(2,8)$ forma parte de la solución
   • Si $y=9$, entonces $x=\dfrac{12-9}{2}=\dfrac{3}{2} \notin \mathbb{N}\cup \{0\}$, por lo que este valor no aporta nada a la solución
   • Si $y=10$, entonces $x=\dfrac{12-10}{2}=\dfrac{2}{2}=1 \in \mathbb{N}\cup \{0\}$, luego $(1,10)$ forma parte de la solución
   • Si $y=11$, entonces $x=\dfrac{12-11}{2}=\dfrac{1}{2} \notin \mathbb{N}\cup \{0\}$, por lo que este valor no aporta nada a la solución
   • Si $y=12$, entonces $x=\dfrac{12-12}{2}=\dfrac{0}{2}=0 \in \mathbb{N}\cup \{0\}$, luego $(0,12)$ forma parte de la solución

En conclusión, la solución de la ecuación diofántica propuesta está formada por las siguientes parejas de números $(x,y)$, enteros no negativos: $\{(4,4),(5,2),(6,0);(3,6),(2,8),(1,10),(0,12)\}$.

$\diamond$

La identidad de Bézout

El lema de Bézout

Un resultado básico relacionado con el máximo común divisor de dos números (enteros), distintos de cero, $a,b$ —y lo notaremos de la forma $(a,b)$—, es la denominada identidad de Bezout (lema de Bezout), que dice así:

  Sea $\mathbb{Z} \ni d=(a,b)$, entonces existen dos números enteros $x,y$, no necesariamente únicos, tales que $d=ax+by \quad \quad (1)$.

Ejemplo. Consideremos los números enteros $2$ y $4$. El máximo común divisor de estos dos números es $d=2$, luego, según el lema de Bézout, existen (infinitas) parejas de números $x$ e $y$, tales que $2=2x+4y$. Nos proponemos encontrar cómo son estas infinitas parejas de números $x,y$.

En un caso general, consideremos dos soluciones particulares $x_1,y_1$ y $x_2,y_2$ de la ecuación $d=ax+by$, y que por tanto se sastisfaga $d=a\,x_1+b\,y_1$ y $d=a\,x_2+b\,y_2$. Entonces, como la estructura algebraica que liga los otros infinitos pares de valores es lineal, estas parejas de números enteros están alineadas en una recta cuyas ecuaciones paramétricas son $\left\{\begin{matrix}x-x_1 = \lambda\,(x_2-x_1)\\y-y_1=\lambda\,(y_2-y_1)\end{matrix}\right.\,; \lambda\in \mathbb{Z}$, o, dicho de otro modo, la solución general vendrá dada por $$\left\{\begin{matrix}x=x_1+ \lambda\,(x_2-x_1)\\y=y_1+\lambda\,(y_2-y_1)\end{matrix}\right.\,; \lambda\in \mathbb{Z}\quad \quad (2)$$ donde $x_2-x_1$ e $y_2-y_1$ son, desde luego, números enteros.

Se puede comprobar sin dificultad que, para toda solución particular$x_p,y_p$ de (1), entonces $x_p+kb$ e $y_p-ka$, para cualquier $k\in \mathbb{R}$, también constituye otra solución particular de la misma ecuación; en efecto $a\,(x_p+kb)+b\,(y_p-ka) = a\,x_p+kab+b\,y_p-kab=a\,x_p+b\,y_p$, y, por tanto, $a\,(x_p+kb)+b\,(y_p-ka)=d$. Entonces, podemos escoger los números enteros $x_2-x_1$ e $y_2-y_1$ de los segundos términos de los respectivos segundos miembros de (2) de la forma $x_2-x_1:=\dfrac{b}{d}$ e $y_2-y_1:=-\dfrac{a}{d}$, habida cuenta de que $\dfrac{b}{d} \in \mathbb{Z}$ y $\dfrac{a}{d}\in \mathbb{Z}$ por ser $d=(a,b)$. Así las cosas, podemos escribir las ecuaciones paramétricas (2) de la forma: $$\left\{\begin{matrix} x=x_1+\lambda\,\dfrac{b}{d} \\y=y_1-\lambda\,\dfrac{a}{d} \end{matrix}\right.\,;\lambda\in \mathbb{Z} $$

Resolvamos ahora el ejemplo concreto que nos hemos planteado. Fácilmente, vemos que una solución particular es $x_1=-1$, $y_1=1$ —en efecto, comprobamos que para estos valores de $x$ e $y$ se satisface (1): $2=2\cdot (-1)+4\cdot 1$—, con lo cual, y según lo que hemos razonado arriba, se tiene que $$\left\{\begin{matrix}x=-1+\dfrac{4}{2}\,\lambda\\y=1-\dfrac{2}{2}\,\lambda\end{matrix}\right.\,; \lambda \in \mathbb{Z}$$ esto es $$\left\{\begin{matrix}x=-1+2\,\lambda\\y=1-\lambda\end{matrix}\right.\,; \lambda \in \mathbb{Z}$$ Podemos pues encontrar los infinitos pares de valores $x$ e $y$ que son solución de (1) asignando valores arbitraios al parámetro entero $\lambda$. Así, para $\lambda=0$ se obtiene la solución particular de la que hemos partido: $x=-1$ e $y=1$; para $\lambda=1$, $x=1$ e $y=0$; para $\lambda=2$, $x=3$ e $y=-1$; para $\lambda=-1$, $x=-3$ e $y=2$; para $\lambda=-2$, $x=-5$ e $y=3$, etcétera.

Ecuaciones diofánticas lineales

Una utilidad muy importante de la identidad de Bézout es la de formar parte del proceso de resolución de una ecuación diofántica lineal, $cx+dy=k$, con $c,d,k\in \mathbb{Z}$, para encontrar la solución general, a partir de una solución particular, se procede de una forma muy parecida a la que estamos empleando para encontrar las parejas de valores $x,y$ de la igualdad de Bézout, y lo expongo en este otro artículo (de este mismo cuaderno), mediante un ejemplo práctico.$\diamond$

Introducción a la resolución de ecuaciones diofánticas

Antes de exponer la solución del ejercicio que resolveremos como ejemplo, vamos a decir algunas cosas sobre las ecuaciones con números enteros; en concreto, las que toman la forma $ax+by=c$ (que son las más sencillas), y que llamamos ecuaciones diofánticas lineales. Los coeficientes $a,b,c \in \mathbb{Z}$ vienen dados; y, de tener solución la ecuación, las incógnitas $x$ e $y$, que debemos determinar deben ser, también, números enteros.

Algo de teoría:
Veamos lo que nos dice la teoría: Una ecuación diofántica lineal del tipo $ax+by=c$ tiene solución si y sólo si $d\overset{.}{=}\text{m.c.d.}(a,b)$ es divisor del término independiente $c$, lo cual anotamos de la forma abreviada $d|c$; y, teniendo solución dicha ecuación, se demuestra que hay infinitos pares de valores $(x,y)$ que satisfacen dicha ecuación. Encontramos las infinitas soluciones ( solución general ) encontrando, primero, una solución particular $(x_1,y_1)$, y, a continuación, la solución general, que es de la forma

$$\left\{\begin{matrix}
x=x_1+\lambda\,\dfrac{b}{d} & \\
\\
y=y_1-\lambda\,\dfrac{a}{d} & \\
\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$

Vamos, ahora, a exponer un ejemplo.

ENUNCIADO:
Sea la ecuación diofántica lineal $6x+50y=108$. ¿ Tiene solución ? En caso afirmativo, ¿ cómo son los infinitos pares de valores enteros $(x,y)$ ?

SOLUCIÓN:
Observemos que $a=6$, $b=50$ y $c=108$. Como el máximo común divisor de $a$ y $b$, $d:=\text{m.c.d.}(6,50)=2$, es divisor del término independiente $c=108$, esto es $2 | 108$, podemos afirmar que la ecuación tiene solución en $\mathbb{Z}$ y que ésta consta de infinitos pares de números enteros $(x,y)$, que vamos a ver cómo son a continuación.

Encontremos, para empezar, una solución particular de la ecuación dada. Para ello, determinaremos primero una solución particular de la ecuación $ax+by=d$ (identidad de Bézout) y, partiendo de ésta, encontraremos la solución general a una ecuación diofántica lineal.

La identidad de Bézout, $ax+by=d$ es, en el caso que nos ocupa, $6x+50y=2$. Y vemos fácilmente que, $-8$ y $1$ son dos números enteros que cumplen dicha igualdad; en efecto, $6(-8)+50\cdot 1 = 2$   (1). Y, como el término independiente, $108$, de la ecuación pedida se obtiene multiplicando el término independiente de la identidad de Bézout ( que es $2$ ) por $108/2=54$, mutiplicaremos pues ambos miembros de (1) por $54$ para obtener $$6\cdot (-8)\cdot 54+50\cdot 1 \cdot 54 = 2 \cdot 54$$ con lo cual $$6 \cdot \underset{x_1}{\underbrace{\left((-8)\cdot 54\right)}}+50 \cdot \underset{y_1}{\underbrace{\left( 1 \cdot 54 \right)}}= 108$$ es decir $$6 \cdot \underset{x_1}{\underbrace{(-432)}}+50 \cdot \underset{y_1}{\underbrace{54}}= 108$$ luego una solución particular es $$x_1=-432\,,\,y_1=54$$ Así pues, finalmente, construyendo la solución general, llegamos a $$\left\{\begin{matrix}
x=-432+\lambda\,\dfrac{50}{2} & \\
\\
y=54-\lambda\,\dfrac{6}{2} & \\
\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$
es decir
$$\left\{\begin{matrix}
x=-432+25\,\lambda \\
\\
y=54-3\,\lambda \\
\end{matrix}\right. \quad \quad \forall \lambda \in \mathbb{Z}$$

Ahora, dando valores (enteros) arbitrarios al parámetro $\lambda$ podemos encontrar cualesquiera de los pares de números enteros $(x,y)$ - hay infinitos - que constituyen la solución general; así, por ejemplo, para $\lambda = 4$, encontramos $(-332,42)$, etcetera.


Referencias:
  [1] BUJALANCE, E.; et. al., Elementos de Matemática Discreta, Sanz y Torres, Madrid, 2005 ( tercera edición )
  [2] PARSONS, P.; DIXON, G.et. al., Matemáticas en segundos, Librero, Madrid, 2020 ( pp. 42-43 )
  [3] Wikipedia, https://es.wikipedia.org/wiki/Ecuación_diofántica

$\square$