Resolución de ecuaciones diofánticas

Las ecuaciones diofánticas contienen 2 incógnitas en una sola ecuación y están generalmente expresadas en la forma ax + by = c

Cuando hay dos incógnitas, tal vez nos resulte más familiar un sistema de dos ecuaciones como nos enseñaron en primaria, por ejemplo:

  • 2x + 2 = 6y
  • 4y + 2 = x + 6

Ahora bien, una ecuación diofántica también nos resulta familiar expresada en la forma ax + by – c = 0 , pues se trata de la ecuación de una recta. Al tratarse de una recta sus soluciones serán infinitas, si tiene solución.

Aunque el conjunto de puntos de una recta está en R, al igual que hemos hecho con las congruencias contemplaremos sólo las soluciones en Z. En este conjunto, hay un teorema debido al matemático indio Brahmagupta, que nos dice que la condición necesaria y suficiente para que la ecuación diofántica ax + by = c tenga solución es que d = mcd(a, b) | c En este caso, si (x1, y1) es una solución, todas las demás soluciones se obtienen mediante las expresiones:

  • x = x1 + (b / d) * k
  • y = y1 – (a / d) * k

Este teorema nos resulta familiar con las ecuaciones de congruencia; vimos que ax ≡ b (mod m) tendrá solución si d | b En los dos artículos anteriores, 1 y 2, vimos también que solucionar ecuaciones de congruencia lineal se reduce a resolver congruencias donde el coeficiente de la x, a, y el módulo m son primos entre si. El procedimiento es el mismo para las ecuaciones diofánticas. Por el teorema de Bezout sabemos que existen coeficientes s y t tales que:

a*s + b * t = d

Si e = c / d y multiplicamos ambos lados por e tendremos:

  • x1 = s * e
  • y1 = t * e

Vamos a resolver 23x – 4y = 11 Mediante el algoritmo de Euclides tenemos:

  • 23 = -4 * (-5) + 3 ⇒ 2 = 23 – 4 * 5
  • -4 = 3 * (-2) + 2 ⇒ 2 = -4 + 3 * 2
  • 3 = 2 * 1 + 1 ⇒ 1 = 3 -2 * 1

Obtenemos mcd(23, -4) = 1 Usemos el algoritmo extendido de Euclides para hallar un s y t:

1 = 3 – 2 * 1 = 3 – (-4 + 3*2) * 1 = 3 + 4 – 3 * 2 = 4 – 3 * 1 = 4 – (23 – 4 * 5) * 1 = 4 -23 * 1 + 4 * 5 = 23 * (-1) + 4 * 6

Sabiendo s y t tenemos tendremos x1 e y1:

23 * (-1) – 4 * (-6) = 1

23 * (-11) – 4 * (-66) = 11

  • x1 = -11
  • y1 = -66

Reemplacemos para encontrar las expresiones que dan todas las soluciones:

  • x = -11 + (-4 / 1) * k = -11 – 4k
  • y = -66 – (-23 / 1) * k = -66 – 23k

Siguiendo con las familiaridades, podemos ver que estas expresiones para x e y coinciden con la forma paramétrica de la ecuación de la recta.

Si usamos fracciones continuas para resolver la ecuación diofántica llegaremos a este resultado:

  • x1 ⇒ x = 1 – 4k
  • y1 ⇒ y = 3 – 23k

Cómo resolver ecuaciones diofánticas mediante fracciones continuas puede encontrarse en Google, lo que quiero destacar es que aparentemente hemos llegado a un resultado diferente pero no es así. Veamos que ambas soluciones representan la misma recta:

23x - 4y - 11 = 0La segunda solución nos conduce a la misma ecuación 23x – 4y – 11 = 0

23x -4y - 11 = 0El algoritmo extendido de Euclides nos da un par s y t y cualquier otro par nos dará soluciones que son la misma recta. El resto de pares nos los da la expresión:

1 = 23*( -1 – (-4) * h) + (-4)*(-6 + 23 * h) ∀ h ∈ Z

Para h = 1 y multiplicando luego por 11:

  • x1 = 33 ⇒ x = 33 – 4k
  • y1 = 66 ⇒ y = 187 – 23k

Podemos ver que se trata de la misma recta:

23x - 4y - 11 = 0En el artículo anterior resolvimos la congruencia 12x ≡ 15 (mod 21) y podemos ver que resolver esta ecuación equivale a encontrar todos los enteros x que satisfagan la ecuación diofántica 12x + 21y = 15. Vamos a resolverla:

12x + 21y = 15 equivale a 4x + 7y = 5

Bezout: 4s + 7t = 1

Podemos ver que s = 2 y t = -1 satisfacen la ecuación. Por lo tanto:

4(2 * 5) + 7(-1 * 5) = 5

  • x1 = 10 ⇒ x = 10 + 7k
  • y1 = -5 ⇒ y = -5 – 4k

La solución para x son todos los múltiplos de 7 + 10 En “términos” de congruencias diríamos que estamos en Z7 y que 10 pertenece a la clase de equivalencia [3] Sabemos que el mcd es 3, por lo tanto los 3 primeros residuos serán las soluciones: 3, 10 y 17

También vemos que el conjunto de soluciones k = {-1, 0, 1} dan las soluciones de la ecuación de congruencia 12x ≡ 15 (mod 21) x = {3, 10, 17}  Gracias a lo que sabemos de congruencias podemos suponer que otra forma paramétrica correcta para x es:

x = 3 + 7k Por lo tanto x1 = 3. Para encontrar y1 reemplazamos:

4*(3) + 7y = 5 ⇒ y1 = -1 ⇒ y = -1 – 4k Así que otra forma paramétrica equivalente es:

  • x = 3 + 7k
  • y = -1 – 4k

Si desarrollamos como hemos visto anteriormente veremos que ambas formas paramétricas conducen a la misma ecuación de la recta: -4x -7y + 5 = 0

Las congruencias como clases de equivalencia

En este artículo trataré el caso particular de ecuaciones de congruencia lineal que dejé pendiente en el anterior artículo: la solución cuando a y m no son primos entre si, es decir mcd(a, m) > 1 y b es un múltiplo del mcd, es decir mcd | b. Recordemos que si b no es múltiplo del mcd no existirá ninguna solución.

Para poder explicar cómo se solucionan y no dar meramente la fórmula como hace la Wikipedia, hay que introducir las clases de equivalencia y el conjunto de restos. Las clases de equivalencia permiten agrupar los enteros de manera que dos números están en la misma clase sólo si dan el mismo resto módulo m. Esto equivale a decir que a y b están en la misma clase módulo m si m | a – b , es decir, si a – b es un múltiplo de m.

Como la clase de equivalencia de un número a es el conjunto de números que dan el mismo resto al dividirlos por m, es decir [a] = {x ∈ Z: x ≡ a (mod m)} podemos afirmar que una congruencia es una clase de equivalencia.

Por ejemplo, 13 y 24 están en la misma clase módulo 11 al dar el mismo resto 2 y al ser 11 | (24-13). En general, para todo módulo m:

Si [0] = {… ,−2m, −m, 0, m, 2m, …}

[1] será = {…, -2m+1, -m+1, 1, m+1, 2m+1, …}

[2] = {…, -2m+2, -m+2, 2, m+2, 2m+1, …} Indicados en negrita están 13 y 24 para módulo 11.

Así hasta llegar a [m – 1]. El conjunto de restos de un número m será {0, 1, …, m-1} El conjunto de restos de m se designa por Zm. Continuando con el ejemplo:

Z11 = {[0], [1], [2], [3], [4], …, [10]}

Por lo tanto, todo entero será congruente módulo m con algún elemento del conjunto de restos módulo m: {0, 1, …, m-1}. Por ejemplo, todo entero módulo 5 dará uno de estos restos: {0, 1, 2, 3, 4} Si cogemos un número cualquiera, por ejemplo 1234567890123456789, vemos que su resto es 4, por lo tanto 1234567890123456789 ≡ 4 (mod 5)

Por ejemplo, si en el conjunto de los enteros consideramos la clase de equivalencia módulo 5, las clases de equivalencia de -22, -6, 0 y 3 son:

-22 => El resto de -22 / 5 es 3, por lo tanto la clase de equivalencia son todos los múltiplos de 5 + 3:

[-22] = {…, -12, -7, -2, 3, 8, 13, 18, …}

-6 => El resto de -6 / 5 es 4, por lo tanto la clase de equivalencia son todos los múltiplos de 5 + 4:

[-6] = {… , −11, −6, −1, 4, 9, 14, 19, …}

0 => El resto de 0 / 5 es 0, por lo tanto forman parte de la clase todos los múltiplos de 5:

[0] = {…, -15, -10, -5, 0, 5, 10, 15, …}

3 => El resto de 3 / 5 es 3, por lo tanto:

[3] = [-22]

Vemos que mod m divide el conjunto de los números enteros Z en m-1 clases, lo que podemos expresar así:

Zm = {[0]m, [1]m, …, [m – 1]m}

Y como todos los infinitos enteros están contenidos en Zm :

Z = Zm = [0]m ∪ [1]m ∪ … ∪ [m – 1]m

Volviendo a la ecuación de congruencia ax ≡ b (mod m), llamando d al mcd de a y m y siendo d > 1 y d|b, las soluciones serán:

x1 + x1 + m1 , …, x1 + (d – 1)*m1

Donde m1 = m/d, a1 = a/d, b1 = b/d y x1 es la solución de la congruencia a1 x ≡ b1 (mod m1 ) Es decir, las soluciones serán los múltiplos de m1 + x1 Como el número de soluciones es d, se cumple xd < m

Vamos a calcular 12x ≡ 15 (mod 21):

mcd(12, 21) = 3 Por lo que la solución de 4x ≡ 5 (mod 7) será también solución de la ecuación que queremos resolver. El inverso de 4 ≡ 1 (mod 7) es 2. Formemos entonces las dos congruencias como vimos en el artículo previo:

  1. 4x ≡ 5 (mod 7)
  2. 2 ≡ 2 (mod 7)

Al multiplicarlas resulta la congruencia x ≡ 2 * 5 (mod 7), x ≡ 10 (mod 7), En Z7 10 y 3 son la misma clase de equivalencia, por lo tanto es equivalente x ≡ 3 (mod 7) Efectivamente 3 y 10 son soluciones de la ecuación inicial:

3*12 / 21 da resto 15 así como también lo da 120 / 21 La siguiente y última solución xd la da x2 + m: 17. Todas las demás soluciones están en la misma clase de equivalencia [3] en Z7

Además de que la primera solución nos da la clase de equivalencia donde encontraremos todas las soluciones también podemos observar los cuatro puntos siguientes:

Primero:

En Z7 tenemos que [3] = [10] = [17] = [24] = [31] = … = [3+7] = [45]

En Z21 tenemos que [3] = [24] = [45] = … = [3+21]

Segundo:

Todos los enteros que forman la clase de equivalencia de cada clase de resto en Z7 están también en Z21Las clases de restos que forman Z7 son {0, 1, 2, 3, 4, 5, 6} pero para abreviar veremos sólo [3] y [1]:

[3] en Z7 lo forman 7+ 3 = 10, 17, 24, 25, …, 45

[3] en Z21 lo forman 21+ 3 = 24, 45

[1] en Z7 lo forman 7+ 1 = 8, 22, 29, 43, …

[1] en Z21 lo forman 21+ 1 = 22, 43, …

Tercero:

Z21 tiene d veces las clases residuales que tiene de Z7

Cuarto:

Las soluciones de la ecuación de congruencia que hemos resuelto son los primeros d enteros de la clase [3] = 3, 10 y 17

En el artículo anterior tratamos los casos en que mcd(a, m) = 1. Usemos un ejemplo ya resuelto anteriormente: vimos que x ≡ 6 (mod 13) era la solución de 3x ≡ 5 (mod 13) Entonces Z13 [6] = 6, 19, 32,… Como mcd = 1 cogemos el primer entero de la clase de equivalencia: el 6. Por lo tanto, lo aquí expuesto es válido para toda ecuación de congruencia lineal.

El programa definitivo que resuelve cualquier tipo de ecuación de congruencia lineal es:

import sys
from sys import argv

def extendedEuclideanAlgorithm(old_r, r):
    negative = False
    s, old_t = 0, 0
    old_s, t = 1, 1

    if (r < 0):
        r = abs(r)
        negative = True

    while r > 0:
            q = old_r / r
            #MCD:
            r, old_r = old_r - q * r, r
            #Coeficiente s:
            s, old_s = old_s - q * s, s
            #Coeficiente t:
            t, old_t = old_t - q * t, t

    if negative:
        old_t = old_t * -1
        
    return old_r, old_s, old_t

a = long(argv[1])
b = long(argv[2])
m = long(argv[3])
#Para las soluciones no necesitaremos t pero lo recogemos para evitar el error.
mcd, s, t = extendedEuclideanAlgorithm(a, m)
if mcd == 1:
    inverse = (s * b) % m
    print "x ≡ {0} (mod {1})" . format(inverse, m)
elif b%mcd == 0:
    m1, b1, = m / mcd, b / mcd
    equivRelation = (s * b1) % abs(m1)
    print "x ≡ {0} (mod {1})" . format(equivRelation, m1)
    for i in range(mcd):
        print "Solución {0}: {1}" . format(i + 1, i * m1 + equivRelation)
else:
    print "No tiene solución"

Resolvamos la ecuación 4x ≡ 10 (mod 30):

vic@LESBIAN:~/mates$ ./inversoModuloNsoluciones.py 4 10 30
x ≡ 10 (mod 15)
Solución 1: 10
Solución 2: 25

La CIA hackea Notepad++

Notepad ++

Esta cara le quedó cuando se enteró.

En la última actualización rutinaria del extendidísimo editor Notepad++ miro de reojo el log de bugs arreglados y mejoras y me encuentro el siguiente fix:

1.  Fix CIA Hacking Notepad++ issue (https://wikileaks.org/ciav7p1/cms/page_26968090.html).

Aparentemente, el inocente e inofensivo Notepad++, forma parte de las herramientas hackeadas por la CIA.

Programa para resolver ecuaciones de congruencia lineal

Editado el 11/03/2018:

Casi un año después de su publicación, observo en Google Analytics que este artículo tiene un porcentaje de rebote muy elevado. Tal vez este sea debido a que la mayoría de visitantes estén buscando simplemente un programa que resuelva congruencias lineales. Si es tu caso, puedes instalar fácilmente el intérprete de Python 2 en tu ordenador, es muy ligero y existe para todas las plataformas. Como alternativa, dispones de intérpretes en línea (1, 2) donde puedes copiar y pegar el código; después deberás modificarlo ligeramente porque los parámetros no serán argumentos pasados a través de la línea de comandos.


Una ecuación de congruencia es una congruencia entre expresiones literales, los valores que la satisfacen son sus soluciones. Por ejemplo 13x ≡ 5 (mod 77) es una ecuación de congruencia.

Sus soluciones nos las da x ≡ 30 (mod 77) Es decir, todos los infinitos x que al dividirlos por 77 dan el mismo resto que 30/77 Dicho resto es 30 y todos los x serían múltiplos de 77· + 30: 30, 107, 184, 261…

Si reemplazamos estos x en la ecuación de congruencia lineal inicial veremos que son soluciones:

13*30 ≡ 30 (mod 77) => Resto 5. Así como dan el mismo resto:

13*107 ≡ 30 (mod 77)

13*184 ≡ 30 (mod 77)

Para poder encontrar la solución de una congruencia lineal en primer lugar hay que saber hallar el inverso de a (mod m) Este inverso, a’, es un número tal que a’*a ≡ 1 (mod m)

Por ejemplo, el inverso de 6 (mod 11) es 2: 2*6 ≡ 1 (mod 11)

Teorema: La condición necesaria y suficiente para que dos números a y b sean congruentes respecto al módulo m es que su diferencia sea un múltiplo de m, es decir, m | (a -b)

Por lo tanto en el ejemplo sería 11 | (a’ * 6 – 1) => 6a’ – 1 = 11· , 6a’ = 11· + 1 Como ha de ser un múltiple de 11 + 1 vemos fácilmente que a’ = 2 cumple la condición.

Si para hallar el inverso de 2 (mod 8) hacemos: 8 | (a’ * 2 – 1) Vemos que no hay solución pues 2a’ -1 siempre será un número impar mientras que 8 es par. Por lo tanto no siempre existe un inverso. El siguiente teorema nos permite saber cuando existe el inverso:

La condición necesaria y suficiente para que un entero a posea un inverso módulo m, m > 1, es que mcd(a, m) = 1 Además, si existe tal inverso, ese inverso es único módulo m.

Esto nos resulta familiar con el teorema de Bezout explicado en el artículo anterior. Por ejemplo, para calcular el inverso de 111 (mod 250) primero calculamos mcd(111, 250) = 1 Por lo tanto sabemos que existe un inverso a’ y que habrá un s y un t tal que:

111 *s + 250 * t = 1

Aplicando el algoritmo del artículo obtenemos s = -9 y t = 11 y por lo tanto a’ = -9. Así es:

-9 * 111 ≡ 1 (mod 250)

  • -999 dividido entre 250 da el mismo resto que 1 entre 250, r = 1
  • 250 | (-9 * 111 -1) => 250· = -9 * 111 – 1 => Efectivamente -1000 es múltiplo de 250

Ahora bien, existe un teorema que matiza el anterior:

Existe un entero positivo único a’ menor que m que es un inverso de a (mod m) y cualquier otro inverso de a (mod m) será congruente con a’ (mod m)

Como dijimos en el anterior artículo, el par s y t no es único. La expresión general que nos da todos los coeficientes es:

1 =111(-9 + 250h) + 250(4 – 111h) ∀ h ∈ Z

Para h = 1 tendríamos:

1 = 111*241 + 250*(-107)

Como s = 241 y t = -107 tendremos 111*241 ≡ 1 (mod 250) Por lo tanto es 241 el inverso positivo menor que 250.

Si por un lado tenemos la ecuación de congruencia lineal ax ≡ b (mod m) y esta tiene un a’ ∈ Z tal que a’*a = 1 (mod m) Por otro lado, como cualquier número es congruente consigo mismo módulo m podemos crear la congruencia a’ ≡ a’ (mod m).

Un importante teorema dice:

Sean a, b, c y d enteros y m un entero positivo. Si es ab (mod m) y cd (mod m), entonces también es ac ≡ bd (mod m).

Con este teorema, de las dos congruencias anteriores resulta:

ax * a’ ≡ a’ * b (mod m)

Como a’ * a (mod m) = 1 Queda:

1 * x ≡ a’ * b (mod m)

Si existe el inverso modular, es decir, si m y a son primos relativos, o lo que es lo mismo, si mcd(m, a) = 1, todo x congruente con a’ * b (mod m) será solución a la ecuación de congruencia.

Vamos a calcular la solución de 3x ≡ 5 (mod 13):

El programa del artículo anterior, para a y m, es decir, 3 y 13 nos devuelve:

m.c.d. = 1

Bezout s = -4

Bezout t = 1

Como a y m son primos entre si, sin más cálculos podemos ver que el inverso de 3 (mod 13) es 9, pero procedamos como hemos visto. Si el inverso es -4 necesitamos encontrar el positivo, busquemos para ello otro par s y t con h = 1:

1 = 3*(-4 + 13*1) + 13*(1 – 3*1) = 3*9 + 13*(-2)

Por esta vía también obtenemos a’ = 9. Todo x congruente con 9*5 (mod 13) será solución. Como 45 (mod 13) = 6, todos los múltiples de 13· + 6 serán las soluciones a 3x ≡ 5 (mod 13). Por lo tanto, x ≡ 6 (mod 13) es una congruencia equivalente más simple.

Vamos a calcular la solución de 5x ≡ 2 (mod 6):

El programa nos devuelve:

m.c.d. =  1
Bezout s =  -1
Bezout t =  1

Como a y m son primos entre si, tendremos que el inverso a’ es -1. Busquemos el positivo:

1 = 5 * (-1 + 6*1) + 6*(1 – 5*1) = 5 * 5 + 6 * -4

El inverso positivo menor que m es 5.

5*2 (mod 6), 10 (mod 6), x ≡ 10 (mod 6) Los infinitos x congruentes con 10 módulo 6 serán solución de 5x ≡ 2 (mod 6). Es decir, todos los múltiples 6· + 4 Por lo tanto, es equivalente x ≡ 4 (mod 6)

Cuando a y m no son primos entre si, es decir mcd(a, m) > 1 y b es un múltiplo del mcd, es decir mcd | b, la congruencia tiene solución. Si queremos entender el proceso para hallar las soluciones y no limitarnos a aplicar fórmulas será necesario introducir los conjuntos de restos y las clases de equivalencia, pero para ello será necesario un nuevo artículo.

El siguiente programa en Python calcula las ecuaciones de congruencia que se han tratado en este artículo.

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Resuelve ecuaciones de congruencia tipo ax ≡ b (mod m)

import sys
from sys import argv

def extendedEuclideanAlgorithm(old_r, r):
    negative = False
    s, old_t = 0, 0
    old_s, t = 1, 1

    if (r < 0):
        r = abs(r)
        negative = True

    while r > 0:
            q = old_r / r
            #MCD:
            r, old_r = old_r - q * r, r
            #Coeficiente s:
            s, old_s = old_s - q * s, s
            #Coeficiente t:
            t, old_t = old_t - q * t, t

    if negative:
        old_t = old_t * -1
        
    return old_r, old_s, old_t

a = long(argv[1])
b = long(argv[2])
m = long(argv[3])
#Para las soluciones no necesitaremos t pero lo recogemos para evitar el error.
mcd, s, t = extendedEuclideanAlgorithm(a, m)
if mcd == 1:
    inverse = (s * b) % m
    print "x ≡ {0} (mod {1})" . format(inverse, m)
elif b%mcd == 0:
    print "Ver siguiente artículo"
else:
    print "No tiene solución"

Para resolver la ecuación 3x ≡ 5 (mod 13) haríamos:

vic@LESBIAN:~/mates$ ./inversoModulo.py 3 5 13
x ≡ 6 (mod 13)

Cálculo del mcd y la identidad de Bezout

Editado el 11/03/2018:

Casi un año después de su publicación, observo en Google Analytics que este artículo tiene un porcentaje de rebote muy elevado. Tal vez este sea debido a que la mayoría de visitantes estén buscando simplemente un programa que calcule el mcd de dos números y sus coeficientes de Bezout. Si es tu caso, puedes instalar fácilmente el intérprete de Python 2 en tu ordenador, es muy ligero y existe para todas las plataformas. Como alternativa, dispones de intérpretes en línea (1, 2) donde puedes copiar y pegar el código; después deberás modificarlo ligeramente porque los parámetros no serán argumentos pasados a través de la línea de comandos.


He hecho un breve programa en Python que calcula el máximo común divisor (mcd) de dos números pasados como parámetros y sus coeficientes de Bezout. El teorema de Bezout nos dice que dados dos números a y b, cuyo mcd(a, b) = d existen dos números enteros s y t tales que:

a*s + b*t = d

Estos dos números s y t son los llamados coeficientes de Bezout. Este par s y t no tiene por qué ser único, pueden haber otros s y t que cumplan la igualdad. La identidad de Bezout no es una mera curiosidad matemática sino que tiene muchas aplicaciones: desde calcular el inverso de a módulo m, lo que permite resolver ecuaciones de congruencia lineal, hasta resolver ecuaciones diofánticas.

El máximo común divisor se puede calcular a mano como nos enseñaron en la escuela mediante el algoritmo de Euclides. Los coeficientes de Bezout los podemos calcular a mano mediante el algoritmo extendido de Euclides, pero a la hora de programar es más fácil implementar el siguiente algoritmo explicado en la Wikipedia.

Todos estos valores se calculan mediante la división euclídea y esta impone la condición 0 >= r < |d| Es decir, el resto debe ser mayor o igual a 0 y menor que el valor absoluto del divisor. Como expliqué en un artículo anterior, Python no hace la división euclídea cuando el divisor es negativo, por lo tanto en el código hago una pequeña manipulación al signo del segundo número para obtener los coeficientes de Bezout con los signos correctos.

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import sys
from sys import argv

old_r = long(argv[1])
r = long(argv[2])
negative = False
s, old_t = 0, 0
old_s, t = 1, 1

if r < 0:
    r = abs(r)
    negative = True

while r > 0:
    q = old_r / r
    #MCD:
    r, old_r = old_r - q * r, r
    #Coeficiente s:
    s, old_s = old_s - q * s, s
    #Coeficiente t:
    t, old_t = old_t - q * t, t

if negative:
    old_t = old_t * -1
    
print "m.c.d. = ", old_r
print "Bezout s = ", old_s
print "Bezout t = ", old_t

Ejemplo de su ejecución desde la terminal:

vic@LESBIAN:~/mates$ ./bezoutYmcd.py 23 -4
m.c.d. =  1
Bezout s =  -1
Bezout t =  -6

Si convertimos este programa en una función tendremos una herramienta útil para calcular el inverso de a módulo m, resolver ecuaciones de congruencia lineal y ecuaciones diofánticas.