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 Z_m. Continuando con el ejemplo:

Z₁₁ = {[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í:

Z_m = {[0]_m, [1]_m, …, [m – 1]_m}

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

Z = Z_m = [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:

x₁ + x₁ + m₁ , …, x₁ + (d – 1)*m₁

Donde m₁ = m/d, a₁ = a/d, b₁ = b/d y x₁ es la solución de la congruencia a₁ x ≡ b₁ (mod m₁ ) Es decir, las soluciones serán los múltiplos de m₁ + x₁ Como el número de soluciones es d, se cumple x_d < 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 Z₇ 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 x_d la da x₂ + m: 17. Todas las demás soluciones están en la misma clase de equivalencia [3] en Z₇

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 Z₇ tenemos que [3] = [10] = [17] = [24] = [31] = … = [3+7^♦] = [45]

En Z₂₁ tenemos que [3] = [24] = [45] = … = [3+21^♦]

Segundo:

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

[3] en Z₇ lo forman 7^♦+ 3 = 10, 17, 24, 25, …, 45

[3] en Z₂₁ lo forman 21^♦+ 3 = 24, 45

[1] en Z₇ lo forman 7^♦+ 1 = 8, 22, 29, 43, …

[1] en Z₂₁ lo forman 21^♦+ 1 = 22, 43, …

Tercero:

Z₂₁ tiene d veces las clases residuales que tiene de Z₇

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 Z₁₃ [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