Resolución de ecuaciones diofánticas de la forma Ax+By=C

Paco Villegas |

En este artículo facilito un fichero que permite resolver múltiples ejercicios de ecuaciones diofánticas del tipo Ax±By=CAx\pm By=C. De nuevo uso el paquete xlop de LaTeX para realizar las divisiones de números enteros. El fichero está preparado para generar las soluciones en los diferentes casos que se pueden presentar: no exista solución o tenga infinitas soluciones. El código LyX usado es mínimo y casi todo el que se ha usado está escrito directamente en LaTeX.

El paquete xloppresenta algunas limitaciones como son:

  1. Las divisiones euclídeas en modo <<gráfico>> solo son correctas con números naturales. Por ese motivo no las muestro si están implicados números negativos.
  2. Las divisiones euclídeas en modo <<texto>> con números negativos no se calculan bien si son exactas, así por ejemplo el resultado de usar\opidiv[style=text]{-4}{2} no es correcto y se obtiene −4=2×(−3)+2-4=2\times(-3)+2. En ese caso no se hace uso del paquete y se realiza la división de forma directa.

El fichero permite que los coeficientes de las ecuaciones diofánticas se puedan introducir de forma manual o que se generen de forma aleatoria. También podemos determinar qué número de ejercicios deseamos resolver.

Lo único que tendremos que adecuar en el fichero es:

# Listas de posibles ejercicios (coeficientes de las ecuaciones diofánticas)
# para que luego las incorpore deben tener de nombre Ei, i:1..n
E1 = [3,5,7]
E2 = [4,6,8]
E3 = [4,6,7]
E4 = [3,-2,4]
E5 = [-14,21,777]
E6 = [-37,-25,-3]
E7 = [12,-16,20]
E8 = [83,50,-5]
E9 = [176,-583,55]
E10 = [38,-34,6]
E11 = [-10,-54,8]
E12 = [30,-25,15]
E13 = [27,99,18]
E14 = [-57,105,-5]
E15 = [69,63,15]
E16 = [29,-40,5]
E17 = [75,213,7]
E18 = [-138,-57,-8]
E19 = [-29,-25,3]
E20 = [-98,-94,92]

# Podemos optar por obtener los coeficientes de las ecuaciones de forma: aleatoria o manual (de dos formas)
# a -> aleatoria
# m1 -> Se resuelven todos/algunos de  los ejercicios propuestos anteriormente.
# El número de ellos se define con el valor de 'maxejer' comentado después.
# m2 -> Valor por defecto. Podemos definirla "a mano" a partir de los valores de ejercicios anteriores, por ejemplo con
ListaEjer = [E14, E1, E5, E20]

opcion = 'a'

# Rango en el que obtener los valores aleatorios (-rango, rango)
rango = 100

# Número máximo de ejercicios. Tiene una doble función:
# Si optamos por valores aleatorios es el número de ejercicios que se generarán.
# Si optamos por valores introducidos a mano:
# Es el número máximo de ejercicios que se resolverán, comenzando por los números Ei menores.
# Si tenemos definidos 10 ejercicios y aquí ponemos 15, se resolverán los 10.
# Si tenemos definidos 10 ejercicios y aquí ponemos 3, solo se resolverán los 3 primeros: E1, E2 y E3
maxejer = 25

# Si es True, al final aparece la solución directa con sympy
comprobar = True
#comprobar = False

Con los datos anteriores de entrada se han generado 25 ejercicios aleatorios. En el pdf que se puede descargar al final del artículo se muestra el resultado.

En el html que sigue muestro los que se generan con la opción m2 y la lista de ejercicios [E14, E1, E5, E20] cuyos datos se han introducidos de forma manual.

La ecuación diofántica Ax+By=CAx+By=C tiene solución si y solo si d=mcd(A,B)d=mcd(A,B) es un divisor de CC. En ese caso la ecuación tiene infinitas soluciones.

Si resolvemos la ecuación A⋅x+B⋅y=dA\cdot x+B\cdot y=d y q=C/dq=C/d tenemos que q⋅A⋅x+q⋅B⋅y=q⋅d=Cq\cdot A\cdot x+q\cdot B\cdot y=q\cdot d=C.

Problemas

  1. Resuelve la ecuación diofántica

    −57x+105y=−5\boldsymbol{-57x+105y=-5}

    Solución

    image

    −5=3×−2+1-5=3\times-2+1

    No tiene solución ya que el mcd(A,B) no divide a C

  2. Resuelve la ecuación diofántica

    3x+5y=7\boldsymbol{3x+5y=7}

    Solución

    image1

    Resolvamos la ecuación

    3x+5y=13x+5y=1

    con q=7/1=7q=7/1=7 .

    Partimos del sistema {1⋅x+0⋅y=30⋅x+1⋅y=5\begin{cases} 1\cdot x+0\cdot y & =3\\ 0\cdot x+1\cdot y & =5 \end{cases} que tiene como soluciones x=3x=3 e y=5.y=5. Su forma matricial es:

    Paso 0

    (103015)\left(\begin{matrix}1 & 0 & \textcolor{blue}{3}\\ 0 & 1 & \textcolor{blue}{5} \end{matrix}\right)

    image2 5=3×1+25=3\times1+2 ⇒\Rightarrow Restamos a la segunda fila 1 veces la primera

    Paso 1

    (103−112)\left(\begin{matrix}1 & 0 & \textcolor{blue}{3}\\ -1 & 1 & \textcolor{blue}{2} \end{matrix}\right)

    image3 3=2×1+13=2\times1+1 ⇒\Rightarrow Restamos a la primera fila 1 veces la segunda

    Paso 2

    (2−11−112)\left(\begin{matrix}2 & -1 & \textcolor{blue}{1}\\ -1 & 1 & \textcolor{blue}{2} \end{matrix}\right)

    image4 2=1×22=1\times2 ⇒\Rightarrow Restamos a la segunda fila 2 veces la primera

    Paso 3

    (2−11−530)\left(\begin{matrix}2 & -1 & \textcolor{blue}{1}\\ -5 & 3 & \textcolor{blue}{0} \end{matrix}\right)

    Obtenemos el sistema de ecuaciones equivalente al primero:

    {(2)⋅x+(−1)⋅y=1(−5)⋅x+(3)⋅y=0⇒\begin{cases} \left(2\right)\cdot x+\left(-1\right)\cdot y & =1\\ \left(-5\right)\cdot x+\left(3\right)\cdot y & =0 \end{cases}\Rightarrow{(2)⋅(3)+(−1)⋅(5)=1(−5)⋅(3)+(3)⋅(5)=0xxxxxeq:4\begin{cases} \left(2\right)\cdot\left(3\right)+\left(-1\right)\cdot\left(5\right) & =1\\ \left(-5\right)\cdot\left(3\right)+\left(3\right)\cdot\left(5\right) & =0 \end{cases}\phantom{xxxxx}{eq:4}

    Además hemos obtenido que mcd(3,5)=1mcd(3,5)=1. La primera igualdad de ([eq:4]) la tenemos que multiplicar por q=7

    (2)⋅(3)+(−1)⋅(5)=1 ⇒\left({\color{red}2}\right)\cdot\left(3\right)+\left(\mathbin{\color{red}-}{\color{red}1}\right)\cdot\left(5\right)={\color{red}1}\,\Rightarrow7⋅(2)⋅(3)+7⋅(−1)⋅(5)=7⋅1⇒7\cdot\left({\color{red}2}\right)\cdot\left(3\right)+7\cdot\left(\mathbin{\color{red}-}{\color{red}1}\right)\cdot\left(5\right)=7\cdot1\Rightarrow

    (14)⋅(3)+(−7)⋅(5)=7xxxxxeq:5\left({\color{red}14}\right)\cdot\left(3\right)+\left(\mathbin{\color{red}-}{\color{red}7}\right)\cdot\left(5\right)=7\phantom{xxxxx}{eq:5}

    Multipliquemos la segunda igualdad de ([eq:4]) por t

    (−5t)⋅(3)+(3t)⋅(5)=0xxxxxeq:6\left(-5t\right)\cdot\left(3\right)+\left(3t\right)\cdot\left(5\right)=0\phantom{xxxxx}{eq:6}

    Sumamos ([eq:5]) a ([eq:6]) sacando factor común:

    (14−5t)⋅(3)+(3t−7)⋅(5)=7\left(14-5t\right)\cdot\left(3\right)+\left(3t-7\right)\cdot\left(5\right)=7

    Solución general {x=14−5ty=3t−7   t∈Z\begin{cases} x= & 14-5t\\ y= & 3t-7 \end{cases}\,\,\,t\in\mathbb{Z}

  3. Resuelve la ecuación diofántica

    −14x+21y=777\boldsymbol{-14x+21y=777}

    Solución

    image5

    Dividimos todos los coeficientes por 7 obteniendo la siguiente ecuación:

    −2x+3y=111-2x+3y=111

    Resolvamos la ecuación

    −2x+3y=1-2x+3y=1

    con q=111/1=111q=111/1=111

    Partimos del sistema {1⋅x+0⋅y=−20⋅x+1⋅y=3\begin{cases} 1\cdot x+0\cdot y & =-2\\ 0\cdot x+1\cdot y & =3 \end{cases} que tiene como soluciones x=−2x=-2 e y=3.y=3. Su forma matricial es:

    Paso 0

    (10−2013)\left(\begin{matrix}1 & 0 & \textcolor{blue}{-2}\\ 0 & 1 & \textcolor{blue}{3} \end{matrix}\right)

    3=−2×−1+13=-2\times-1+1 ⇒\Rightarrow Sumamos a la segunda fila 1 veces la primera

    Paso 1

    (10−2111)\left(\begin{matrix}1 & 0 & \textcolor{blue}{-2}\\ 1 & 1 & \textcolor{blue}{1} \end{matrix}\right)

    −2=1×(−2)-2=1\times(-2) ⇒\Rightarrow Sumamos a la primera fila 2 veces la segunda

    Paso 2

    (320111)\left(\begin{matrix}3 & 2 & \textcolor{blue}{0}\\ 1 & 1 & \textcolor{blue}{1} \end{matrix}\right)

    Obtenemos el sistema de ecuaciones equivalente al primero:

    {(1)⋅x+(1)⋅y=1(3)⋅x+(2)⋅y=0⇒\begin{cases} \left(1\right)\cdot x+\left(1\right)\cdot y & =1\\ \left(3\right)\cdot x+\left(2\right)\cdot y & =0 \end{cases}\Rightarrow{(1)⋅(−2)+(1)⋅(3)=1(3)⋅(−2)+(2)⋅(3)=0xxxxxeq:7\begin{cases} \left(1\right)\cdot\left(-2\right)+\left(1\right)\cdot\left(3\right) & =1\\ \left(3\right)\cdot\left(-2\right)+\left(2\right)\cdot\left(3\right) & =0 \end{cases}\phantom{xxxxx}{eq:7}

    Además hemos obtenido que mcd(−2,3)=1mcd(-2,3)=1. La primera igualdad de ([eq:7]) la tenemos que multiplicar por q=111

    (1)⋅(−2)+(1)⋅(3)=1 ⇒\left({\color{red}1}\right)\cdot\left(-2\right)+\left({\color{red}1}\right)\cdot\left(3\right)={\color{red}1}\,\Rightarrow111⋅(1)⋅(−2)+111⋅(1)⋅(3)=111⋅1⇒111\cdot\left({\color{red}1}\right)\cdot\left(-2\right)+111\cdot\left({\color{red}1}\right)\cdot\left(3\right)=111\cdot1\Rightarrow

    (111)⋅(−2)+(111)⋅(3)=111xxxxxeq:8\left({\color{red}111}\right)\cdot\left(-2\right)+\left({\color{red}111}\right)\cdot\left(3\right)=111\phantom{xxxxx}{eq:8}

    Multipliquemos la segunda igualdad de ([eq:7]) por t

    (3t)⋅(−2)+(2t)⋅(3)=0xxxxxeq:9\left(3t\right)\cdot\left(-2\right)+\left(2t\right)\cdot\left(3\right)=0\phantom{xxxxx}{eq:9}

    Sumamos ([eq:8]) a ([eq:9]) sacando factor común:

    (3t+111)⋅(−2)+(2t+111)⋅(3)=111\left(3t+111\right)\cdot\left(-2\right)+\left(2t+111\right)\cdot\left(3\right)=111

    Solución general {x=3t+111y=2t+111   t∈Z\begin{cases} x= & 3t+111\\ y= & 2t+111 \end{cases}\,\,\,t\in\mathbb{Z}

  4. Resuelve la ecuación diofántica

    −98x−94y=92\boldsymbol{-98x-94y=92}

    Solución

    Multiplicamos todos los coeficientes por -1 obteniendo la siguiente ecuación:

    98x+94y=−9298x+94y=-92

    image6

    −92=2×(−46)-92=2\times(-46)

    Dividimos todos los coeficientes por 2 obteniendo la siguiente ecuación:

    49x+47y=−4649x+47y=-46

    Resolvamos la ecuación

    49x+47y=149x+47y=1

    con q=−46/1=−46q=-46/1=-46

    Partimos del sistema {1⋅x+0⋅y=490⋅x+1⋅y=47\begin{cases} 1\cdot x+0\cdot y & =49\\ 0\cdot x+1\cdot y & =47 \end{cases} que tiene como soluciones x=49x=49 e y=47.y=47. Su forma matricial es:

    Paso 0

    (10490147)\left(\begin{matrix}1 & 0 & \textcolor{blue}{49}\\ 0 & 1 & \textcolor{blue}{47} \end{matrix}\right)

    image7 49=47×1+249=47\times1+2 ⇒\Rightarrow Restamos a la primera fila 1 veces la segunda

    Paso 1

    (1−120147)\left(\begin{matrix}1 & -1 & \textcolor{blue}{2}\\ 0 & 1 & \textcolor{blue}{47} \end{matrix}\right)

    image8 47=2×23+147=2\times23+1 ⇒\Rightarrow Restamos a la segunda fila 23 veces la primera

    Paso 2

    (1−12−23241)\left(\begin{matrix}1 & -1 & \textcolor{blue}{2}\\ -23 & 24 & \textcolor{blue}{1} \end{matrix}\right)

    image9 2=1×22=1\times2 ⇒\Rightarrow Restamos a la primera fila 2 veces la segunda

    Paso 3

    (47−490−23241)\left(\begin{matrix}47 & -49 & \textcolor{blue}{0}\\ -23 & 24 & \textcolor{blue}{1} \end{matrix}\right)

    Obtenemos el sistema de ecuaciones equivalente al primero:

    {(−23)⋅x+(24)⋅y=1(47)⋅x+(−49)⋅y=0⇒\begin{cases} \left(-23\right)\cdot x+\left(24\right)\cdot y & =1\\ \left(47\right)\cdot x+\left(-49\right)\cdot y & =0 \end{cases}\Rightarrow{(−23)⋅(49)+(24)⋅(47)=1(47)⋅(49)+(−49)⋅(47)=0xxxxxeq:10\begin{cases} \left(-23\right)\cdot\left(49\right)+\left(24\right)\cdot\left(47\right) & =1\\ \left(47\right)\cdot\left(49\right)+\left(-49\right)\cdot\left(47\right) & =0 \end{cases}\phantom{xxxxx}{eq:10}

    Además hemos obtenido que mcd(49,47)=1mcd(49,47)=1. La primera igualdad de ([eq:10]) la tenemos que multiplicar por q=-46

    (−23)⋅(49)+(24)⋅(47)=1 ⇒\left(\mathbin{\color{red}-}{\color{red}23}\right)\cdot\left(49\right)+\left({\color{red}24}\right)\cdot\left(47\right)={\color{red}1}\,\Rightarrow−46⋅(−23)⋅(49)+−46⋅(24)⋅(47)=−46⋅1⇒-46\cdot\left(\mathbin{\color{red}-}{\color{red}23}\right)\cdot\left(49\right)+-46\cdot\left({\color{red}24}\right)\cdot\left(47\right)=-46\cdot1\Rightarrow

    (1058)⋅(49)+(−1104)⋅(47)=−46xxxxxeq:11\left({\color{red}1058}\right)\cdot\left(49\right)+\left(\mathbin{\color{red}-}{\color{red}1104}\right)\cdot\left(47\right)=-46\phantom{xxxxx}{eq:11}

    Multipliquemos la segunda igualdad de ([eq:10]) por t

    (47t)⋅(49)+(−49t)⋅(47)=0xxxxxeq:12\left(47t\right)\cdot\left(49\right)+\left(-49t\right)\cdot\left(47\right)=0\phantom{xxxxx}{eq:12}

    Sumamos ([eq:11]) a ([eq:12]) sacando factor común:

    (47t+1058)⋅(49)+(−49t−1104)⋅(47)=−46\left(47t+1058\right)\cdot\left(49\right)+\left(-49t-1104\right)\cdot\left(47\right)=-46

    Solución general {x=47t+1058y=−49t−1104   t∈Z\begin{cases} x= & 47t+1058\\ y= & -49t-1104 \end{cases}\,\,\,t\in\mathbb{Z}

Enlaces al fichero fuente y al pdf final de una posible compilación.