9 Ecuaciones diofanticas lineales ‣ Part III Aritmética entera y modular ‣ Matemática discreta

Definition 9.1 (Ecuacion diofantica lineal).

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

ax+by=c

donde

•

$a,b,c\in\mathbb{Z}$ son los coeficientes
•

$x,y$ son las incognitas que pueden tomar valores en $\mathbb{Z}$ .

Theorem 9.2.

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

ax+by=c

La ecuacion tiene solucion si y solo si $d\mid c$ .

Ademas, si $(x_{0},y_{0})$ es una solucion de la ecuacion, entonces el conjunto de todas las soluciones

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

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

Proof 9.3.

Considero $ax+by$ $\;x,y\in\mathbb{Z}$ .

Por el teorema de Bezout, $\left\{ax+by\mid x,y\in\mathbb{Z}\right\}=d\mathbb{Z}$ . Luego $ax+by=c$ si y solo si $c$ es multiplo de $d$ .

Vamos a demostrar que si $(x_{0},y_{0})$ es una solucion entonces

\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 $(x_{1},y_{1})$ otra solucion de la ecuacion.

Entonces $ax_{1}+by_{1}=c$ . Como $ax_{0}+by_{0}=c\Rightarrow ax_{1}+by_{1}=ax_{0}+by_{0}$ $\Rightarrow ax_{1}-ax_{0}=by_{0}-by_{1}$

$a(x_{1}-x_{0})=b(y_{0}-y_{1})$

$\frac{a}{d}(x_{1}-x_{0})=\frac{b}{d}(y_{0}-y_{1})$

Entonces $\frac{a}{d}\mid\frac{b}{d}(y_{0}-y_{1})$

Ademas, por el lema 8.51 $\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$

Aplicando el lema de Euclides $\frac{a}{d}\mid(y_{0}-y_{1})\Rightarrow\exists t\in\mathbb{Z}$ tal que $y_{0}-y_{1}=t\cdot\frac{a}{d}$

Por tanto $y_{1}=y_{0}-t\cdot\frac{a}{d}$ .

Voy a obtener $x_{1}$ :

$\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$

Example 9.4.

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

1.

$224x+92y=82$

$\mathrm{m.c.d.}(224,92)=4$

Luego $4\nmid 82\Rightarrow\not\exists$ sol de la ecuacion.
2.

$224x+92y=44$

$\mathrm{m.c.d.}(224,92)=4\mid 44\Rightarrow\exists\text{ soluciones}$

Para encontrar una solucion particular $(x_{0},y_{0})$ nos apoyamos en una identidad de Bezout entre 224 y 92.

$224\cdot 7+92\cdot(-17)=4$ (7 y -17 calculado anteriormente con el algoritmo extendido de Euclides)

Multiplico por 11: $224\cdot 11\cdot 7+92\cdot 11\cdot(-17)=44$

Luego $x_{0}=11\cdot 7=77$ , $y_{0}=(-17)\cdot 11=-187$

El teorema que hemos demostrado me dice que el conjunto de soluciones es

$\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.

$224x-92y=-20$

$\mathrm{m.c.d.}(224,-92)=\mathrm{m.c.d.}(224,92)=4$

$4\mid-20\Rightarrow\exists$ soluciones

A partir de $4=224\cdot 7+92\cdot(-17)$ multiplicando por 5:

$-20=224\cdot(-5)\cdot 7+92\cdot(-5)\cdot(-17)\Rightarrow-20=224\cdot(-35)-92% \cdot(-85)$

Luego $x_{0}=-35,y_{0}=-85$ es una solucion.

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

Remark 9.5.

Si existen soluciones, encontrar una solucion particular $(x_{0},y_{0})$ se hace facilmente a traves de una identidad de Bezout.

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