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

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$

Cálculo con congruencias (clases de resto módulo m)

Notación:
Designaremos un número entero con una letra minúscula
Denotamos el máximo común divisor de $m$ y $n$ por $(m,n)$
Para expresar que $a$ divide a $b$ ( $b$ es múltiplo de $a$ ), escribiremos $a|b$ ( con lo cual notaremos $b=\dot{a}$ )

Lema (de Bézout)
Sea $d=(m,n)$, entonces se puede encontrar una combinación $a\,m+b\,n$ tal que $$d \,| \,(a\,m+b\,n)$$

Definición ( $a$ congruente con $a$ módulo $m$ )
Sea $m$ un entero no negativo. Decimos que $a=b\, \text{mod} \, m$ ( o también $a\equiv b\, (\text{mod} \, m)$ ) si y sólo si $m \,| \,(b-a)$

Pequeño teorema de Fermat
Sea $a$ un número entero no negativo y $p$ primo, tales que $a \neq \dot{p}$, entonces $a^{p-1} = 1 \;( \,\text{mod}\, p)$

Otra forma de enunciar el Pequeño Teorema de Fermat
Sea $a$ un número entero no negativo y $p$ primo, entonces $a^p = a \; ( \,\text{mod}\, p)$