Acerca de la identidad de Bézout y las ecuaciones diofánticas lineales

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 $\text{m.c.d.}(a,b)$—, es la denominada identidad de Bézout, que dice así:

Sea $\mathbb{Z} \ni d=\text{m.c.d.}(a,b)$, entonces existen infinitas parejas de números enteros $x,y$, tales que $d=ax+by$.

Veamos un ejemplo:
Consideremos los números enteros $a=4$ y $b=2$ —para hacerlo sencillo, los hemos elegido positivos—. Sabemos que el máximo común divisor de estos dos números es $d=\text{m.c.d.}(4,2)=2$, entonces, según el resultado que nos ocupa (identidad de Bézout), podremos encontrar otros dos números $x,y$ (no necesariamente únicos) tales que $2=4x+2y$. En efecto, es claro que una posibilidad es $x_1=0$ e $y_1=1$, entre otras infinitas parejas que satisfacen esta igualdad, y se puede justificar que son 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}$$ es decir, en el caso que nos ocupa: $$\left\{\begin{matrix}x=0+\lambda\,\dfrac{2}{2}=\lambda \\ y=1-\lambda\,\dfrac{4}{2}=1-2\,\lambda\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$ esto es $$\{(0,1),(1,-1),(-1,3),(2,-3),(-2,5),\ldots\}$$

Otro ejemplo:
Dados los números enteros $a=1170$ y $b=363$, nos proponemos encontrar los pares de valores enteros $x,y$ tales que $x\,a+y\,b=d$ (donde $d=\text{m.c.d.}(a,b)$. Lo primero que haremos es calcular el máximo común divisor; y, como vamos a ver enseguida, nos vendrá muy bien hacerlo aplicando el algoritmo de Euclides. Sigamos los pasos necesarios:
  (1)   $1170=363\cdot 3+81$
  (2)   $363=81\cdot 4+39$
  (3)   $81=39\cdot 2+3$
  (4)   $39=13\cdot 3+0 \Rightarrow d=3$
Procedemos ahora a encontrar una solución particular $x_1,y_1$:
  De (3), $3=81-39\cdot 2$
    y teniendo en cuenta (2), podemos escribir que
    $3=81-(363-81\cdot 4)\cdot 2=81-363\cdot 2 +81\cdot 8=9\cdot 81 -263\cdot 2$
    que, siguiendo a partir de (1), puede escribirse de la forma
    $3=9\cdot 81 -263\cdot 2=9\cdot 1170-27\cdot 363-363\cdot 2 = 9\cdot 1170 -29\cdot 363 \Rightarrow x_1=9$ y $y_1=-29$
Con lo cual, como ya sabemos la estructura de la solución general, llegamos a que ésta es: $$\left\{\begin{matrix}x=9+\lambda\,\dfrac{363}{3} \\ y=-29-\lambda\,\dfrac{1170}{3}\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$ esto es $$\left\{\begin{matrix}x=9+121\,\lambda \\ y=-29-390\,\lambda\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$ obteniendo (dando valores arbitrarios a $\lambda$: $0,\pm1,\pm2\,\ldots$) las infinitas parejas de que consta la solución: $$\{(9,-29),(130,-419),(-112,361),\ldots\}$$

-oOo-

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$, siendo también $c,d$ y $k$, números enteros, y siendo $k|d=\text{m.c.d.}(a,b)$. En estas condiciones, la solución general de dicha ecuación diofántica lineal está formada por un conjunto de parejas de números enteros $x$ e $y$. Para encontrar dicha solución general, a partir de una solución particular, se parte del resultado básico de la identidad de Bézout. En cursos superiores, aprenderéis a resolver este tipo de ecuaciones. Si sóis personas curiosas, os sugiero que os avancéis y leáis este otro artículo —como ampliación opcional— para ver como se hace.

Nota: El nombre que se le da a estas ecuaciones de números enteros viene del matemático Diofanto (s. III d.C.), quien en su obra Arithmetica expuso la resolución de algunas de dichas ecuaciones. $\diamond$

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

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) y que, en este caso en particular, han de ser números enteros 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)\}$.

-oOo-

Aquí puedes ver otra manera de resolver el problema: empleando el método estándar de resolución de las ecuaciones diofánticas lineales (que se basa en el lema de Bézout)

$\diamond$

Acerca de la identidad 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 $\text{m.c.d.}(a,b)$—, es la denominada identidad de Bézout, que dice así:

Sea $\mathbb{Z} \ni d=\text{m.c.d.}(a,b)$, entonces existen infinitas parejas de números enteros $x,y$, tales que $d=ax+by$.

Veamos un ejemplo:
Consideremos los números enteros $a=4$ y $b=2$ —para hacerlo sencillo, los hemos elegido positivos—. Sabemos que el máximo común divisor de estos dos números es $d=\text{m.c.d.}(4,2)=2$, entonces, según el resultado que nos ocupa (identidad de Bézout), podremos encontrar otros dos números $x,y$ (no necesariamente únicos) tales que $2=4x+2y$. En efecto, es claro que una posibilidad es $x_1=0$ e $y_1=1$, entre otras infinitas parejas que satisfacen esta igualdad, y se puede justificar que son 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}$$ es decir, en el caso que nos ocupa: $$\left\{\begin{matrix}x=0+\lambda\,\dfrac{2}{2}=\lambda \\ y=1-\lambda\,\dfrac{4}{2}=1-2\,\lambda\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$ esto es $$\{(0,1),(1,-1),(-1,3),(2,-3),(-2,5),\ldots\}$$

Otro ejemplo:
Dados los números enteros $a=1170$ y $b=363$, nos proponemos encontrar los pares de valores enteros $x,y$ tales que $x\,a+y\,b=d$ (donde $d=\text{m.c.d.}(a,b)$. Lo primero que haremos es calcular el máximo común divisor; y, como vamos a ver enseguida, nos vendrá muy bien hacerlo aplicando el algoritmo de Euclides. Sigamos los pasos necesarios:
  (1)   $1170=363\cdot 3+81$
  (2)   $363=81\cdot 4+39$
  (3)   $81=39\cdot 2+3$
  (4)   $39=13\cdot 3+0 \Rightarrow d=3$
Procedemos ahora a encontrar una solución particular $x_1,y_1$:
  De (3), $3=81-39\cdot 2$
    y teniendo en cuenta (2), podemos escribir que
    $3=81-(363-81\cdot 4)\cdot 2=81-363\cdot 2 +81\cdot 8=9\cdot 81 -263\cdot 2$
    que, siguiendo a partir de (1), puede escribirse de la forma
    $3=9\cdot 81 -263\cdot 2=9\cdot 1170-27\cdot 363-363\cdot 2 = 9\cdot 1170 -29\cdot 363 \Rightarrow x_1=9$ y $y_1=-29$
Con lo cual, como ya sabemos la estructura de la solución general, llegamos a que ésta es: $$\left\{\begin{matrix}x=9+\lambda\,\dfrac{363}{3} \\ y=-29-\lambda\,\dfrac{1170}{3}\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$ esto es $$\left\{\begin{matrix}x=9+121\,\lambda \\ y=-29-390\,\lambda\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$ obteniendo (dando valores arbitrarios a $\lambda$: $0,\pm1,\pm2\,\ldots$) las infinitas parejas de que consta la solución: $$\{(9,-29),(130,-419),(-112,361),\ldots\}$$

-oOo-

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$, siendo también $c,d$ y $k$, números enteros, y siendo $k|d=\text{m.c.d.}(a,b)$. En estas condiciones, la solución general de dicha ecuación diofántica lineal está formada por un conjunto de parejas de números enteros $x$ e $y$. Para encontrar dicha solución general, a partir de una solución particular, se parte del resultado básico de la identidad de Bézout. En cursos superiores, aprenderéis a resolver este tipo de ecuaciones. Si sóis personas curiosas, os sugiero que os avancéis y leáis este otro artículo —como ampliación opcional— para ver como se hace.

Nota: El nombre que se le da a estas ecuaciones de números enteros viene del matemático Diofanto (s. III d.C.), quien en su obra Arithmetica expuso la resolución de algunas de dichas ecuaciones. $\diamond$

Ecuaciones diofánticas lineales