9 Ecuaciones diofanticas lineales

Definición 9.1 (Ecuacion diofantica lineal).

Una ecuacion diofantica lineal con dos incognitas es una ecuacion del tipo

\displaystyle ax+by=c

donde

$\displaystyle a,b,c\in\mathbb{Z}$ son los coeficientes
$\displaystyle x,y$ son las incognitas que pueden tomar valores en $\displaystyle\mathbb{Z}$ .

Teorema 9.1.

Sean $\displaystyle a,b,c\in\mathbb{Z}$ con $\displaystyle a,b\neq 0$ , sea $\displaystyle d=\mathrm{m.c.d.}(a,b)$ y consideremos la ecuacion

\displaystyle ax+by=c

La ecuacion tiene solucion si y solo si $\displaystyle d\mid c$ . Ademas, si $\displaystyle(x_{0},y_{0})$ es una solucion de la ecuacion, entonces el conjunto de todas las soluciones

\displaystyle\begin{dcases}x=x_{0}+\frac{b}{d}t\\ y=y_{0}-\frac{a}{d}t\end{dcases}

con $\displaystyle t\in\mathbb{Z}$ un parametro que recorre todo $\displaystyle\mathbb{Z}$ .

Demostración.

Considero $\displaystyle ax+by$ $\displaystyle\;x,y\in\mathbb{Z}$ . Por el teorema de Bezout, $\displaystyle\{ax+by\mid x,y\in\mathbb{Z}\}=d\mathbb{Z}$ . Luego $\displaystyle ax+by=c$ si y solo si $\displaystyle c$ es multiplo de $\displaystyle d$ . Vamos a demostrar que si $\displaystyle(x_{0},y_{0})$ es una solucion entonces

\displaystyle\begin{dcases}x=x_{0}+\frac{b}{d}t\\ y=y_{0}-\frac{a}{d}t\end{dcases}\quad t\in\mathbb{Z}

son todas las soluciones. Tenemos que demostrar que todas esas parejas son soluciones y que no hay mas.

1.

Veamos que son soluciones.

$a(x_{0}+\frac{b}{d}z)+b(y_{0}-\frac{a}{d}t)=a\cdot x_{0}+a\cdot\frac{b}{d}% \cdot z+b\cdot y_{0}-b\frac{a}{d}t=a\cdot x_{0}+by_{0}=\\ =a\cdot x_{0}+a\cdot y_{0}=c\text{ porque }(x_{0},y_{0})\text{ es solucion}$
2.

Voy a ver que todas las soluciones son asi. Sea $\displaystyle(x_{1},y_{1})$ otra solucion de la ecuacion. Entonces $\displaystyle ax_{1}+by_{1}=c$ . Como $\displaystyle ax_{0}+by_{0}=c\Rightarrow ax_{1}+by_{1}=ax_{0}+by_{0}$ $\displaystyle\Rightarrow ax_{1}-ax_{0}=by_{0}-by_{1}$ $\displaystyle a(x_{1}-x_{0})=b(y_{0}-y_{1})$ $\displaystyle\frac{a}{d}(x_{1}-x_{0})=\frac{b}{d}(y_{0}-y_{1})$ Entonces $\displaystyle\frac{a}{d}\mid\frac{b}{d}(y_{0}-y_{1})$ Ademas, por el lema 8.9 $\displaystyle\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$ Aplicando el lema de Euclides $\displaystyle\frac{a}{d}\mid(y_{0}-y_{1})\Rightarrow\exists t\in\mathbb{Z}$ tal que $\displaystyle y_{0}-y_{1}=t\cdot\frac{a}{d}$ Por tanto $\displaystyle y_{1}=y_{0}-t\cdot\frac{a}{d}$ . Voy a obtener $\displaystyle x_{1}$ :

$\displaystyle\frac{a}{d}(x_{1}-x_{0})=\frac{b}{d}t\frac{a}{d}\Rightarrow x_{1}% -x_{0}=\frac{b}{d}t\Rightarrow x_{1}=x_{0}+\frac{b}{d}t$

∎

Ejemplo.

Encuentra (si existen) todas las soluciones enteras de las ecuaciones:

1.

$\displaystyle 224x+92y=82$ $\displaystyle\mathrm{m.c.d.}(224,92)=4$ Luego $\displaystyle 4\nmid 82\Rightarrow\not\exists$ sol de la ecuacion.
2.

$\displaystyle 224x+92y=44$ $\displaystyle\mathrm{m.c.d.}(224,92)=4\mid 44\Rightarrow\exists\text{ soluciones}$ Para encontrar una solucion particular $\displaystyle(x_{0},y_{0})$ nos apoyamos en una identidad de Bezout entre 224 y 92. $\displaystyle 224\cdot 7+92\cdot(-17)=4$ (7 y -17 calculado anteriormente con el algoritmo extendido de Euclides) Multiplico por 11: $\displaystyle 224\cdot 11\cdot 7+92\cdot 11\cdot(-17)=44$ Luego $\displaystyle x_{0}=11\cdot 7=77$ , $\displaystyle y_{0}=(-17)\cdot 11=-187$ El teorema que hemos demostrado me dice que el conjunto de soluciones es

$\displaystyle\begin{dcases}x=x_{0}+\frac{b}{d}t\\ y=y_{0}-\frac{a}{d}t\end{dcases}\Rightarrow\begin{dcases}x=77+23t\\ y=-187-56t\end{dcases}\quad t\in\mathbb{Z}$
3.

$\displaystyle 224x-92y=-20$ $\displaystyle\mathrm{m.c.d.}(224,-92)=\mathrm{m.c.d.}(224,92)=4$ $\displaystyle 4\mid-20\Rightarrow\exists$ soluciones A partir de $\displaystyle 4=224\cdot 7+92\cdot(-17)$ multiplicando por 5: $\displaystyle-20=224\cdot(-5)\cdot 7+92\cdot(-5)\cdot(-17)\Rightarrow-20=224% \cdot(-35)-92\cdot(-85)$ Luego $\displaystyle x_{0}=-35,y_{0}=-85$ es una solucion.

$\displaystyle\begin{dcases}x=-35-23t\\ y=-85-56t\end{dcases}$

Observación.

Si existen soluciones, encontrar una solucion particular $\displaystyle(x_{0},y_{0})$ se hace facilmente a traves de una identidad de Bezout. Si la ecuaicon es $\displaystyle ax+by=c$ y tenemos una identidad de Bezout $\displaystyle au+bv=d$ entonces $\displaystyle(x_{0},y_{0})=(um,vm)$ es una solucion particular, donde $\displaystyle m=\frac{c}{d}$ .