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:
- 4x ≡ 5 (mod 7)
- 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
