Sistemas lineales de congruencias: Teorema chino del resto

Paco Villegas |

En esta ocasión, el fichero LyX que podéis descargar permite resolver varios ejercicios de sistemas de ecuaciones modulares que cumplan las condiciones del Teorema Chino del Resto. De igual forma que en el artículo anterior, para realizar las divisiones de números enteros se hace uso del paquete xlop de LaTeX, lo que provoca que existan algunas limitaciones en los valores permitidos de los coeficientes (deben ser números naturales).

El código python que contiene el fichero no es muy elegante pero por lo que he comprobado funciona bien. Destacar que no permite resolver sistemas de ecuaciones modulares que tienen solución pero en los que no es directo emplear el Teorema Chino del Resto: si los módulos no son coprimos entre sí, ni sistemas con ecuaciones redundantes o si las ecuaciones se pueden simplificar.

Para algunos valores de entrada los cálculos realizados pueden ser redundantes.

  • Lo único que tendremos que adecuar se comenta en propio fichero y consiste en:

    # Datos a modificar del programa. Tienen que ser enteros positivos y sus valores
# están condicionados por lo permitido por el paquete xlop de LaTeX

# Datos
# Si por ejemplo nuestra congruencia es de la forma:
# a1*x = b1 (mód n1)
# a2*x = b2 (mód n2)
# la matriz de datos es de la forma
# Matrix([[a1,b1,n1],[a2,b2,n2]])

# Para que construya bien la lista de ejercicios el nombre de la variable que
# contiene los datos tiene que ser de la forma E+número de ejercicio,
# como por ejemplo el listado que sigue. En el pdf no se respeta el
# número que ponemos aquí

E1 = Matrix([[1,1,15],[1,1,16]])
E2 = Matrix([[118,18,169],[238,38,13*17]])
E3 = Matrix([[2,5,3],[3,2,7]])
E4 = Matrix([[168,24,220],[56,40,69]])
E5 = Matrix([[168,24,221],[56,40,69]])
E6 = Matrix([[1,5495,7643],[1,7569,8765]])
E7 = Matrix([[1,2,3],[1,3,5],[1,2,7]])
E8 = Matrix([[3,1,2],[1,1,3],[2,3,5]])
E9 = Matrix([[6,2,25],[5,2,7],[7,3,18]])
E10 = Matrix([[3*13,4,11*17],[2,27,135],[10,19,47*7]])
E11 = Matrix([[1,0,7],[1,1,3],[1,7,8],[1,19,23]])
E12 = Matrix([[1,2,3],[1,3,5],[1,6,8],[1,10,11]])
E13 = Matrix([[4,2,9],[5,3,7],[3,4,5],[7,5,22]])
E14 = Matrix([[5,6,11],[3,13,16],[2,9,21],[7,19,25],[4,9,13]])

# Número máximo de ejercicios.
# Si ponemos más de 15 tenemos que aumentar este valor para que se construya
# bien la lista de ejercicios. Si tenemos definidos 10 ejercicios y aquí ponemos
# 3, solo se resolveran los 3 primeros: E1, E2 y E3
maxejer = 15

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

# La lista de ejercicios que deseamos obtener se construye de forma automática
# a partir de los datos anteriores de la forma:
#ListaEjer = [E1, E2, ....]

ListaEjer = []
for i in range(maxejer):
    ejer = 'E'+str(i+1)
    if ejer in locals():
        ListaEjer.append(locals()[ejer])

# Podemos definirla "a mano con"
# ListaEjer = [E1, E4, E6]

    Es decir:

    • Podemos resolver a la vez tantos ejercicios como deseemos a partir de una serie de matrices en las que almacenamos los datos de las congruencias.
    • Podemos optar por comprobar que los cálculos realizados son correctos obteniendo el resultado de forma directa con sympy.

En el pdf que se puede descargar al final están resueltos los 14 ejercicios que se listan antes. En formato html solo pondré uno de ellos, en concreto el número 10.

Ejemplo de salida de uno de los ejercicios:

Teorema chino del resto: Si en el sistema

a1x≡b1 (modn1)a2x≡b2 (modn2)⋮asx≡bs (modns)}\left.\begin{array}{ccc} a_{1}x & \equiv & b_{1}\ {(mod {n_{1}})}\\ a_{2}x & \equiv & b_{2}\ {(mod {n_{2}})}\\ & \vdots\\ a_{s}x & \equiv & b_{s}\ {(mod {n_{s}})} \end{array}\right\}

se verifica que mcd(ni,nj)=1 ∀i≠jmcd(n_{i},n_{j})=1\ \forall i\mathrel{\char`≠} j, y que mcd(ai,ni)=1 ∀imcd(a_{i},n_{i})=1\ \forall i, entonces tiene solución, que será única módulo n1⋅n2⋯nsn_{1}\cdot n_{2}\cdots n_{s}.

Resuelve {39x≡4(mod187)2x≡27(mod135)10x≡19(mod329)\left\{ \begin{aligned}39x & \equiv4\pmod{187}\\ 2x & \equiv27\pmod{135}\\ 10x & \equiv19\pmod{329} \end{aligned} \right.

Solución

Comprobemos que los módulos son coprimos dos a dos:

image

mcd(187,135)=1, mcd(187,329)=1, mcd(135,329)=1

Obtengamos el inverso de 39 módulo 187

(103901187)\left(\begin{matrix}1 & 0 & \textcolor{blue}{39}\\ 0 & 1 & \textcolor{blue}{187} \end{matrix}\right)

image ⇒\Rightarrow 187 = 4 · 39 + 31 ⇒\Rightarrow 187 - 4 · 39 = 31 ⇒\Rightarrow Restamos a la segunda fila 4 veces la primera

(1039−4131)\left(\begin{matrix}1 & 0 & \textcolor{blue}{39}\\ -4 & 1 & \textcolor{blue}{31} \end{matrix}\right)

image1 ⇒\Rightarrow 39 = 1 · 31 + 8 ⇒\Rightarrow 39 - 1 · 31 = 8 ⇒\Rightarrow Restamos a la primera fila 1 veces la segunda

(5−18−4131)\left(\begin{matrix}5 & -1 & \textcolor{blue}{8}\\ -4 & 1 & \textcolor{blue}{31} \end{matrix}\right)

image2 ⇒\Rightarrow 31 = 3 · 8 + 7 ⇒\Rightarrow 31 - 3 · 8 = 7 ⇒\Rightarrow Restamos a la segunda fila 3 veces la primera

(5−18−1947)\left(\begin{matrix}5 & -1 & \textcolor{blue}{8}\\ -19 & 4 & \textcolor{blue}{7} \end{matrix}\right)

image3 ⇒\Rightarrow 8 = 1 · 7 + 1 ⇒\Rightarrow 8 - 1 · 7 = 1 ⇒\Rightarrow Restamos a la primera fila 1 veces la segunda

(24−51−1947)\left(\begin{matrix}24 & -5 & \textcolor{blue}{1}\\ -19 & 4 & \textcolor{blue}{7} \end{matrix}\right)

image4 ⇒\Rightarrow 7 = 7 · 1 + 0 ⇒\Rightarrow 7 - 7 · 1 = 0 ⇒\Rightarrow Restamos a la segunda fila 7 veces la primera

(24−51−187390)\left(\begin{matrix}24 & -5 & \textcolor{blue}{1}\\ -187 & 39 & \textcolor{blue}{0} \end{matrix}\right)

Por tanto 39−1=2439^{-1}=24 y el mcd( 39 , 187 )=1

Obtengamos el inverso de 2 módulo 135

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

image5 ⇒\Rightarrow 135 = 67 · 2 + 1 ⇒\Rightarrow 135 - 67 · 2 = 1 ⇒\Rightarrow Restamos a la segunda fila 67 veces la primera

(102−6711)\left(\begin{matrix}1 & 0 & \textcolor{blue}{2}\\ -67 & 1 & \textcolor{blue}{1} \end{matrix}\right)

image6 ⇒\Rightarrow 2 = 2 · 1 + 0 ⇒\Rightarrow 2 - 2 · 1 = 0 ⇒\Rightarrow Restamos a la primera fila 2 veces la segunda

(135−20−6711)\left(\begin{matrix}135 & -2 & \textcolor{blue}{0}\\ -67 & 1 & \textcolor{blue}{1} \end{matrix}\right)

Por tanto 2−1=−67≡68(mod135)2^{-1}=-67\equiv68\pmod{135} y el mcd( 2 , 135 )=1

Obtengamos el inverso de 10 módulo 329

(101001329)\left(\begin{matrix}1 & 0 & \textcolor{blue}{10}\\ 0 & 1 & \textcolor{blue}{329} \end{matrix}\right)

image7 ⇒\Rightarrow 329 = 32 · 10 + 9 ⇒\Rightarrow 329 - 32 · 10 = 9 ⇒\Rightarrow Restamos a la segunda fila 32 veces la primera

(1010−3219)\left(\begin{matrix}1 & 0 & \textcolor{blue}{10}\\ -32 & 1 & \textcolor{blue}{9} \end{matrix}\right)

image8 ⇒\Rightarrow 10 = 1 · 9 + 1 ⇒\Rightarrow 10 - 1 · 9 = 1 ⇒\Rightarrow Restamos a la primera fila 1 veces la segunda

(33−11−3219)\left(\begin{matrix}33 & -1 & \textcolor{blue}{1}\\ -32 & 1 & \textcolor{blue}{9} \end{matrix}\right)

image9 ⇒\Rightarrow 9 = 9 · 1 + 0 ⇒\Rightarrow 9 - 9 · 1 = 0 ⇒\Rightarrow Restamos a la segunda fila 9 veces la primera

(33−11−329100)\left(\begin{matrix}33 & -1 & \textcolor{blue}{1}\\ -329 & 10 & \textcolor{blue}{0} \end{matrix}\right)

Por tanto 10−1=3310^{-1}=33 y el mcd( 10 , 329 )=1

Tenemos las ecuaciones nuevas:
39x≡4(mod187)⇒x≡39−1⋅4(mod187)≡24⋅4(mod187)≡96(mod187)39x\equiv4\pmod{187}\Rightarrow x\equiv39^{-1}\cdot4\pmod{187}\equiv24\cdot4\pmod{187}\equiv96\pmod{187}
2x≡27(mod135)⇒x≡2−1⋅27(mod135)≡68⋅27(mod135)≡1836(mod135)≡81(mod135)2x\equiv27\pmod{135}\Rightarrow x\equiv2^{-1}\cdot27\pmod{135}\equiv68\cdot27\pmod{135}\equiv1836\pmod{135}\equiv81\pmod{135}
10x≡19(mod329)⇒x≡10−1⋅19(mod329)≡33⋅19(mod329)≡627(mod329)≡298(mod329)10x\equiv19\pmod{329}\Rightarrow x\equiv10^{-1}\cdot19\pmod{329}\equiv33\cdot19\pmod{329}\equiv627\pmod{329}\equiv298\pmod{329}

El sistema original quedaría {x≡96(mod187)x≡81(mod135)x≡298(mod329)\left\{ \begin{aligned}x & \equiv96\pmod{187}\\ x & \equiv81\pmod{135}\\ x & \equiv298\pmod{329} \end{aligned} \right.

La solución de la última ecuación es:

x=329t3+298⇒x=329t_{3}+298\Rightarrow

298+329t3≡81(mod135)298+329t_{3}\equiv81\pmod{135} y como 298=135⋅2+28298=135\cdot2+28 ⇒28+329t3≡81(mod135)\Rightarrow28+329t_{3}\equiv81\pmod{135} ⇒329t3≡53(mod135)\Rightarrow329t_{3}\equiv53\pmod{135} y como 329=135⋅2+59329=135\cdot2+59 ⇒59t3≡53(mod135)\Rightarrow59t_{3}\equiv53\pmod{135}

(105901135)\left(\begin{matrix}1 & 0 & \textcolor{blue}{59}\\ 0 & 1 & \textcolor{blue}{135} \end{matrix}\right)

image10 ⇒\Rightarrow 135 = 2 · 59 + 17 ⇒\Rightarrow 135 - 2 · 59 = 17 ⇒\Rightarrow Restamos a la segunda fila 2 veces la primera

(1059−2117)\left(\begin{matrix}1 & 0 & \textcolor{blue}{59}\\ -2 & 1 & \textcolor{blue}{17} \end{matrix}\right)

image11 ⇒\Rightarrow 59 = 3 · 17 + 8 ⇒\Rightarrow 59 - 3 · 17 = 8 ⇒\Rightarrow Restamos a la primera fila 3 veces la segunda

(7−38−2117)\left(\begin{matrix}7 & -3 & \textcolor{blue}{8}\\ -2 & 1 & \textcolor{blue}{17} \end{matrix}\right)

image12 ⇒\Rightarrow 17 = 2 · 8 + 1 ⇒\Rightarrow 17 - 2 · 8 = 1 ⇒\Rightarrow Restamos a la segunda fila 2 veces la primera

(7−38−1671)\left(\begin{matrix}7 & -3 & \textcolor{blue}{8}\\ -16 & 7 & \textcolor{blue}{1} \end{matrix}\right)

image13 ⇒\Rightarrow 8 = 8 · 1 + 0 ⇒\Rightarrow 8 - 8 · 1 = 0 ⇒\Rightarrow Restamos a la primera fila 8 veces la segunda

(135−590−1671)\left(\begin{matrix}135 & -59 & \textcolor{blue}{0}\\ -16 & 7 & \textcolor{blue}{1} \end{matrix}\right)

Por tanto 59−1=−16≡119(mod135)⇒59^{-1}=-16\equiv119\pmod{135}\Rightarrow

t3≡119⋅53(mod135)t_{3}\equiv119\cdot53\pmod{135} ⇒t3≡6307(mod135)⇒\Rightarrow t_{3}\equiv6307\pmod{135}\Rightarrow t3≡97(mod135)t_{3}\equiv97\pmod{135}

t3=135t2+97⇒t_{3}=135t_{2}+97\Rightarrow

x=329t3+298⇒x=329t_{3}+298\Rightarrow x=329⋅(135t2+97)+298⇒x=329\cdot(135t_{2}+97)+298\Rightarrow

x=44415t2+32211⇒x=44415t_{2}+32211\Rightarrow

32211+44415t2≡96(mod187)32211+44415t_{2}\equiv96\pmod{187} y como 32211=187⋅172+4732211=187\cdot172+47 ⇒47+44415t2≡96(mod187)\Rightarrow47+44415t_{2}\equiv96\pmod{187} ⇒44415t2≡49(mod187)\Rightarrow44415t_{2}\equiv49\pmod{187} y como 44415=187⋅237+9644415=187\cdot237+96 ⇒96t2≡49(mod187)\Rightarrow96t_{2}\equiv49\pmod{187}

(109601187)\left(\begin{matrix}1 & 0 & \textcolor{blue}{96}\\ 0 & 1 & \textcolor{blue}{187} \end{matrix}\right)

image14 ⇒\Rightarrow 187 = 1 · 96 + 91 ⇒\Rightarrow 187 - 1 · 96 = 91 ⇒\Rightarrow Restamos a la segunda fila 1 veces la primera

(1096−1191)\left(\begin{matrix}1 & 0 & \textcolor{blue}{96}\\ -1 & 1 & \textcolor{blue}{91} \end{matrix}\right)

image15 ⇒\Rightarrow 96 = 1 · 91 + 5 ⇒\Rightarrow 96 - 1 · 91 = 5 ⇒\Rightarrow Restamos a la primera fila 1 veces la segunda

(2−15−1191)\left(\begin{matrix}2 & -1 & \textcolor{blue}{5}\\ -1 & 1 & \textcolor{blue}{91} \end{matrix}\right)

image16 ⇒\Rightarrow 91 = 18 · 5 + 1 ⇒\Rightarrow 91 - 18 · 5 = 1 ⇒\Rightarrow Restamos a la segunda fila 18 veces la primera

(2−15−37191)\left(\begin{matrix}2 & -1 & \textcolor{blue}{5}\\ -37 & 19 & \textcolor{blue}{1} \end{matrix}\right)

image17 ⇒\Rightarrow 5 = 5 · 1 + 0 ⇒\Rightarrow 5 - 5 · 1 = 0 ⇒\Rightarrow Restamos a la primera fila 5 veces la segunda

(187−960−37191)\left(\begin{matrix}187 & -96 & \textcolor{blue}{0}\\ -37 & 19 & \textcolor{blue}{1} \end{matrix}\right)

Por tanto 96−1=−37≡150(mod187)⇒96^{-1}=-37\equiv150\pmod{187}\Rightarrow

t2≡150⋅49(mod187)t_{2}\equiv150\cdot49\pmod{187} ⇒t2≡7350(mod187)⇒\Rightarrow t_{2}\equiv7350\pmod{187}\Rightarrow t2≡57(mod187)t_{2}\equiv57\pmod{187}

t2=187t1+57t_{2}=187t_{1}+57

x=44415t2+32211⇒x=44415t_{2}+32211\Rightarrow x=44415⋅(187t1+57)+32211⇒x=44415\cdot(187t_{1}+57)+32211\Rightarrow

x=8305605t1+2563866x=8305605t_{1}+2563866

x=8305605t1+2563866⇔x≡2563866(mod8305605)\boldsymbol{x=8305605t_{1}+2563866\Leftrightarrow x\equiv2563866\pmod{8305605}}

Solución directa con sympy: x=8305605t1+2563866x=8305605t_{1}+2563866

39⋅2563866=99990774=187⋅534710+4{\color{blue}39}\cdot2563866=99990774={\color{blue}{\color{blue}187}}\cdot534710+{\color{blue}4}

2⋅2563866=5127732=135⋅37983+27{\color{blue}2}\cdot2563866=5127732={\color{blue}135}\cdot37983+{\color{blue}27}

10⋅2563866=25638660=329⋅77929+19{\color{blue}10}\cdot2563866=25638660={\color{blue}329}\cdot77929+{\color{blue}19}