Sistemas de congruencias lineales

Introducción

En el capítulo anterior con el Teorema chino del residuo logramos encontrar solución a sistemas de congruencias lineales en dónde los módulo son primos relativos por pares. En este capítulo vamos a ver sistemas de congruencias lineales en donde los módulos no necesariamente son primos relativos, veremos la condición para que estos sistemas tengan solución y mostraremos algunos métodos para resolverlos.

Veremos como resolver sistemas de congruencias lineales de \(2\) variables, sin embargo cuando los sistemas empiezan a tener \(3\) o mas variables la notación matricial es de mucha ayuda, es por eso que utilizaremos algunos resultados de Álgebra lineal para desarrollar un método que nos ayude a resolver dichos sistemas. Dejaremos referencias a los resultados usados por si no estas familiarizado o necesitar recordarlo.

Algunos resultados auxiliares

Teorema 54

El máximo común divisor se distribuye sobre el mínimo común múltiplo, es decir

\[(a,[b,c]) = [(a,b),(a,c)].\]

Demostración. Para demostrar la igualdad vamos a utilizar la Definición 18, entonces tendríamos que podemos expresar \(a,b\) y \(c\) en su descomposición canónica.

\[\begin{align*} a &= p_1^{e_1}p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}, \\ & \\ b &= p_1^{f_1}p_2^{f_2}\cdot \ldots \cdot p_k^{f_k}, \\ & \\ c &= p_1^{g_1}p_2^{g_2}\cdot \ldots \cdot p_k^{g_k}. \\ \end{align*}\]

Ahora con la Definición 19 y la Definición 21 podemos escribir el máximo común divisor y el mínimo común múltiplo en función de la descomposición canónica.

Vamos a expresar el lado izquierdo de la igualdad \((a,[b,c])\). Primero calcularemos \([b,c]\), y después \((a, [b,c])\).

\[[b,c] = p_1^{max\{f_1,g_1 \}}p_2^{max\{f_2,g_2\}}\cdot \ldots \cdot p_k^{max\{f_k,g_k \}}.\]

Entonces tendríamos que

\[(a,[b,c]) = p_1^{min\{e_1, max\{f_1,g_1 \} \}}p_2^{min\{e_2, max\{f_2,g_2 \} \}} \cdot \ldots \cdot p_k^{min\{e_k, max\{f_k,g_k \} \}} .\]

Por otro lado podemos expresar el lado derecho de la igualdad \([(a,b),(a,c)]\). Primero calcularemos \((a,b)\) y \((a,c)\) y después \([(a,b),(a,c)]\).

\[\begin{align*} (a,b) &= p_1^{min\{e_1,f_1 \}}p_2^{min\{e_2,f_2 \}} \cdot \ldots \cdot p_k^{min\{e_k,f_k \}} \\ & \\ (a,c) &= p_1^{min\{e_1,g_1 \}}p_2^{min\{e_2,g_2 \}} \cdot \ldots \cdot p_k^{min\{e_k,g_k \}}. \end{align*}\]

Entonces tendríamos que

\[[(a,b),(a,c)] = p_1^{max\{min\{e_1,f_1 \} , min\{e_1,g_1 \} \} }p_2^{max\{min\{e_2,f_2 \} , min\{e_2,g_2 \} \} } \cdot \ldots \cdot p_k^{max\{min\{e_k,f_k \} , min\{e_k,g_k \} \} }.\]

Para que las expresiones sean iguales, tendríamos que ver que para cada primo \(p_i\) en donde \(1 \le i \le k\), se cumple que

\[min\{e_i, max\{f_i,g_i \} \} = max\{min\{e_i,f_i \} , min\{e_i,g_i \} \} .\]

Vamos a considerar los siguientes casos

• Supongamos que \(e_i \le max\{f_i,g_i \}\). Entonces tendríamos que

  \[min\{e_i, max\{f_i,g_i \} \} = e_i.\]

Además \(e_i\) es menor que \(f_i\) y \(g_i\) sin importar cual sea el valor de \(max\{ f_i, g_i \}\), entonces tendríamos que

\[max\{min\{e_i,f_i \} , min\{e_i,g_i \} \} = max\{e_i , e_i \} = e_i.\]

• Supongamos ahora que \(e_i > max\{f_i,g_i \}\). Entonces tendríamos que

\[min\{e_i, max\{f_i,g_i \} \} = max\{f_i,g_i \}.\]

En este caso \(e_i\) es mas grande que \(f_i\) y \(g_i\) sin importar el valor de \(max\{ f_i, g_i \}\), entonces tendríamos que

\[max\{min\{e_i,f_i \} , min\{e_i,g_i \} \} = max\{f_i , g_i \}.\]

Entonces como la igualdad se cumple para cada primo \(p_i\), en donde \(1\le i\le k\). Podemos concluir que \((a,[b,c]) = [(a,b),(a,c)]\). \(\square\)

El teorema Teorema 54 se puede generalizar.

Teorema 55

El máximo común divisor se distribuye sobre el mínimo común múltiplo, es decir

\[(a,[b_1,b_2,\ldots ,b_k]) = [(a,b_1),(a,b_2), \ldots ,(a,b_k)].\]

La demostración es muy parecida a la del Teorema 54 y se dejará como ejercicio al lector.

Sistemas de congruencias lineales de una variable

En el capítulo anterior estudiamos sistemas de congruencias lineales en donde los módulos necesitaban ser primos relativos por pares para poder poder resolverlos con el Teorema 53. En esta sección vamos a resolver sistemas en donde los módulos no son necesariamente primos relativos.

Teorema 56

El sistema de congruencias lineales

\[\begin{align*} x &\equiv a\pmod{m} \\ & \\ x &\equiv b\pmod{n} \end{align*}\]

tiene solución si y solo si \((m,n)|(a-b)\). Además si tiene solución, la solución es única módulo \([m,n]\).

Demostración. Vamos a probar primero que el sistema tiene solución si y solo si \((m,n)|(a-b)\) y después veremos que esa solución es única módulo \([m,n]\).

• Primero veamos que si el sistema tiene solución entonces \((m,n)|(a-b).\)

Si \(x\) es una solución del sistema entonces satisface la congruencia \(x\equiv a\pmod{m}\) luego por el Teorema 31 tenemos que \(x = a + mu\) para algún entero \(u\). Luego \(x\) también satisface la congruencia \(x \equiv b\pmod{n}\), entonces tendríamos que

\[x = a + mu\equiv b\pmod{n}.\]

Luego nuevamente por el Teorema 31 tendríamos que

\[a + mu = b + nv,\]

para algún entero \(v\). Ahora como \((m,n)|n\) y \((m,n)|m\) tendríamos lo siguiente

\[a - b = nv - mu \equiv 0\pmod{(m,n)}.\]

Por lo tanto \(a\equiv b\pmod{(m,n)}\) lo cual quiere decir que \((m,n)|(a-b).\)

• Ahora veamos que si \((m,n)|(a-b)\) entonces el sistema tiene solución.

Por hipótesis tenemos que \((m,n)|(a-b)\) entonces por la implicación de regreso del Teorema 16 tendríamos que existen enteros \(v\) y \(u\) tales que la ecuación lineal diofantina

\[a -b = nv - mu,\]

tiene solución. Así podemos definir

\[x = a + mu = b + nv.\]

Por lo tanto como \(x = a + mu\) tendríamos que \(x\equiv a\pmod{m}\) y como \(x = b + nv\) tendríamos que \(x\equiv b\pmod{n}\).

• Por último vamos a demostrar que la solución es única módulo \([m,n]\).

Supongamos que \((m,n)|(a-b)\) y que \(x_0\) es una solución del sistema de congruencias lineales. Sea \(x_1\) otra solución arbitraria del sistema. Vamos a demostrar que \(x_1\equiv x_0\pmod{[m,n]}\).

Ya que \(x_0\) y \(x_1\) son soluciones, entonces ambas satisfacen las congruencias, es decir que

\[\begin{align*} x_0 &\equiv a\pmod{m}, \\ & \\ x_0 &\equiv b\pmod{n}, \\ & \\ x_1 &\equiv a\pmod{m}, \\ & \\ x_1 &\equiv b\pmod{n}. \end{align*}\]

Luego por la propiedad \(3\) del Teorema 32 tenemos que \(x_1\equiv x_0\pmod{m}\) y \(x_1\equiv x_0\pmod{n}\), es decir que \(m|(x_1 - x_2)\) y \(n|(x_1 - x_0)\), por el Corolario 17 tendríamos que \([m,n]|(x_1 - x_0)\), esto significa que \(x_1\equiv x_0\pmod{[m,n]}\).

Por lo tanto toda solución es congruente con \(x_0\) módulo \([m,n]\), es decir que la solución es única módulo \([m,n]\). \(\square\)

Aunque del teorema anterior no obtengamos una fórmula para la solución, si obtenemos una solución particular \(x_0\), la solución general es de la forma \(x = x_0 + [m,n]t\) para algún entero arbitrario \(t\).

Ejemplo 139

Determina si el sistema lineal de congruencias

\[\begin{align*} x &\equiv 5\pmod{9} \\ & \\ x &\equiv 8\pmod{12} \end{align*}\]

tiene solución. Si tiene solución, da la solución general.

Solución.

Primero notemos que \((9,12) = 3\), además \(3|(5-8) = -3\), así el sistema tiene solución.

Como \(x\equiv 5\pmod{9}\) tenemos que \(x = 5 + 9t'\), esto lo sustituimos en la segunda congruencia

\[\begin{align*} x &\equiv 8\pmod{12} \\ & \\ 5 + 9t' &\equiv 8\pmod{12} \\ & \\ 9t' &\equiv 8-5\pmod{12} \\ & \\ 9t' &\equiv 3\pmod{12}. \end{align*}\]

Luego por el Lema 13 podemos dividir todos los coeficientes de la congruencia entre \(3\) y tenemos que

\[3t'\equiv 1\pmod{4}.\]

Notemos que \(3\cdot 3 \equiv 1\pmod{4}\), entonces tendríamos que

\[t'\equiv 3\pmod{4}.\]

De lo anterior tenemos que \(t' = 3 + 4t\) para algún entero \(t\).
Por lo tanto tendríamos que

\[x = 5 + 9t' = 5 + 9(3 + 4t) = 5 + 27 + 36t = 32 + 36t.\]

Así \(x = 32\) es la única solución incongruente y la solución general es \(x = 32 + 36t\) en donde \([9,12] = 36\).

Ahora vamos a generalizar el teorema anterior para poder saber cuando un sistema de \(3\) o más congruencias lineales tiene solución.

Teorema 57

El sistema de congruencias lineales

\[\begin{align*} x &\equiv a_1\pmod{m_1}, \\ & \\ x &\equiv a_2\pmod{m_2}, \\ & \vdots \\ x &\equiv a_k\pmod{m_k}, \\ \end{align*}\]

tiene solución si y solo si \((m_i,m_j)|(a_i - a_j)\) para todo \(i\) y \(j\), en donde \(1\le j<i \le k\). Además si el sistema tiene solución, esta es única módulo \([m_1,m_2,\ldots ,m_k]\).

Demostración. Vamos a demostrar las dos implicaciones.

• Primero demostremos que si \((m_i,m_j)|(a_i - a_j)\) para toda \(i,j \in \{1,2,\ldots ,k \}\), entonces el sistema tiene solución y además todas las soluciones son congruentes módulo \([m_1,m_2,\ldots ,m_k]\).

Vamos a utilizar inducción sobre el número de congruencias.

Paso base. Si \(k = 2\) tenemos que \((m_1,m_2)|(a_1,a_2)\) y el sistema

\[\begin{align*} x &\equiv a_1\pmod{m_1}, \\ & \\ x &\equiv a_2\pmod{m_2}, \end{align*}\]

tiene solución y es única módulo \([m_1,m_2]\), estos ya vimos que es cierto en el Teorema 56.

Hipótesis inductiva. Supongamos que \(k>2\), y que la afirmación es cierta para un sistema de congruencias lineales con \(k-1\) congruencias. Es decir que \((m_i,m_j)|(a_i - a_j)\) para toda \(i,j \in \{1,2,\ldots ,k-1 \}\) y además la solución es única módulo \([m_1,m_2, \ldots ,m_{k-1}]\).

Paso inductivo. Por hipótesis de inducción supondremos que hay una solución \(s\) del sistema de las \(k-1\) primeras congruencias y que las demás soluciones son congruentes módulo \([m_1,m_2, \ldots ,m_{k-1}]\), así que el sistema

\[\begin{align*} x &\equiv a_1\pmod{m_1}, \\ & \\ x &\equiv a_2\pmod{m_2}, \\ & \vdots \\ x &\equiv a_{k-1}\pmod{m_{k-1}}, \\ \end{align*}\]

es equivalente a

\[x\equiv s\pmod{[m_1,m_2, \ldots ,m_{k-1}]}\]

Por lo tanto tendríamos el sistema

\[\begin{align*} x &\equiv s\pmod{[m_1,m_2, \ldots ,m_{k-1}]} \\ & \\ x &\equiv a_k\pmod{m_k} \end{align*}\]

Ahora para demostrar que tiene solución necesitamos ver que

\[([m_1,m_2, \ldots ,m_{k-1}], m_k)|(s-a_k).\]

Pero por el Teorema 55 como el máximo común divisor se distribuye sobre el mínimo común múltiplo, entonces tenemos que

\[([m_1,m_2, \ldots ,m_{k-1}], m_k) = [(m_1,m_k),(m_2,m_k), \ldots , (m_{k-1},m_k)].\]

Entonces para demostrar que \(([m_1,m_2, \ldots ,m_{k-1}], m_k)|(s-a_k)\), tenemos que demostrar que cada uno de los \((m_i,m_k)|(s - a_k)\) para toda \(1 \le i < k\).

Como \(s\) es solución de cada \(x\equiv a_i\pmod{m_i}\), tendríamos que \(s = a_i + km_i\), que es lo mismo que \(a_i = s - km_i\). Por otro lado tenemos por hipótesis lo siguiente

\[\begin{align*} (m_i,m_k)|(a_i - a_k) \\ & \\ (m_i,m_k)|(s - km_i - a_k) \\ & \\ (m_i,m_k)|(s - a_k) - km_i. \end{align*}\]

Lo anterior quiere decir que

\[s - a_k\equiv km_i\equiv 0\pmod{(m_i,m_k)}.\]

Por lo tanto el sistema de congruencias lineales con \(k\) congruencias tiene solución, además todas las soluciones son congruentes módulo \([[m_1,m_2, \ldots ,m_{k-1}], m_k] = [m_1,m_2,\ldots ,m_{k-1},m_k].\)

• Ahora veamos que si el sistema de congruencias lineales tiene solución entonces \((m_i,m_j)|(a_i - a_j)\).

Esto sucede ya que para que el sistema tenga solución, cada pareja de congruencias debe tener solución, entonces la pareja de congruencias

\[\begin{align*} x\equiv a_i\pmod{m_i} \\ & \\ x\equiv a_j\pmod{m_j}. \end{align*}\]

Luego por el Teorema 56 sabemos que el sistema tiene solución si y solo si \((m_i,m_j)|(a_i - a_j)\), esto pasa para toda \(i,j\) en donde \(1\le i <j \le k\).

Luego si \(x_1\) y \(x_2\) fueran dos soluciones del sistema, tendríamos que para toda \(i\in \{1,2,\ldots ,k \}\),

\[x_1\equiv x_2\pmod{m_i}.\]

Entonces \(m_i|(x_1 - x_2)\), y por el Corolario 17 tendríamos que \([m_1,m_2,\ldots ,m_{k-1},m_k]|(x_1 - x_2)\) es decir que

\[x_1\equiv x_2\pmod{[m_1,m_2,\ldots ,m_{k-1},m_k]}. \square\]

Ejemplo 140

Resuelve el siguiente sistema de congruencias.

\[\begin{align*} x &\equiv 2\pmod{6}, \\ & \\ x &\equiv 5\pmod{9}, \\ & \\ x &\equiv 8\pmod{11}, \\ & \\ x &\equiv 11\pmod{15}. \\ \end{align*}\]

Solución.

Primero tenemos que verificar si las congruencias tienen solución \(2\) a \(2\), es decir que \((m_i,m_j)|(a_i - a_j)\) para \(i,j\in \{1,2,3,4 \}\).

Para las congruencias \(1\) y \(2\), tenemos

\[(6,9) = 3|(2-5) = -3.\]

Para las congruencias \(1\) y \(3\), tenemos

\[(6,11) = 1|(2-8) = -6.\]

Para las congruencias \(1\) y \(4\), tenemos

\[(6,15) = 3|(2-11) = -9.\]

Para las congruencias \(2\) y \(3\), tenemos

\[(9,11) = 1|(5-8) = -3.\]

Para las congruencias \(2\) y \(4\), tenemos

\[(9,15) = 3|(5-11) = -6.\]

Para las congruencias \(3\) y \(4\), tenemos

\[(11,15) = 1|(8-11) = -3.\]

Por lo tanto el sistema tiene solución. Vamos a resolver el sistema por el método de iteración.
De la congruencia \(x\equiv 2\pmod{6}\) tenemos que \(x = 2 + 6t_1\), sustituyendo esto en la congruencia \(x\equiv 5\pmod{9}\) tenemos que

\[\begin{align*} x &\equiv 5\pmod{9} \\ & \\ 2+6t_1 &\equiv 5\pmod{9} \\ & \\ 6t_1 &\equiv 5-2\pmod{9} \\ & \\ 6t_1 &\equiv 3\pmod{9} \\ & \\ 2t_1 &\equiv 1\pmod{3} \\ & \\ 2\cdot 2t_1 &\equiv 2\cdot 1\pmod{3} \\ & \\ t_1 &\equiv 2\pmod{3}. \end{align*}\]

Ahora de la congruencia \(t_1 \equiv 2\pmod{3}\), tenemos que \(t_1 = 2 + 3t_2\), entonces tendríamos que

\[x = 2 + 6t_1 = 2 + 6(2 + 3t_2) = 2 + 12 + 18t_2 = 14 + 18t_2.\]

Vamos a sustituirlo en la congruencia \(x \equiv 8\pmod{11}\) y tenemos que

\[\begin{align*} x &\equiv 8\pmod{11} \\ & \\ 14 + 18t_2 &\equiv 8\pmod{11} \\ & \\ 18t_2 &\equiv 8-14\pmod{11} \\ & \\ 18t_2 &\equiv -6\pmod{11} \\ & \\ 7t_2 &\equiv 5\pmod{11} \\ & \\ 8\cdot 7t_2 &\equiv 8\cdot 5\pmod{11} \\ & \\ t_2 &\equiv 40\pmod{11} \\ & \\ t_2 &\equiv 7\pmod{11}. \end{align*}\]

Ahora de la congruencia \(t_2 \equiv 7\pmod{11}\), tenemos que \(t_2 = 7 + 11t_3\), entonces tendríamos que

\[x = 14 + 18t_2 = 14 + 18(7 + 11t_3) = 14 + 126 + 198t_3 = 140 + 198t_3.\]

Vamos a sustituirlo en la congruencia \(x\equiv 11\pmod{15}\) y tenemos que

\[\begin{align*} x &\equiv 11\pmod{15} \\ & \\ 140 + 198t_3 &\equiv 11\pmod{15} \\ & \\ 198t_3 &\equiv 11-140\pmod{15} \\ & \\ 198t_3 &\equiv -129\pmod{15} \\ & \\ 3t_3 &\equiv 6\pmod{15} \\ & \\ t_3 &\equiv 2\pmod{5}. \end{align*}\]

Entonces de la congruencia \(t_3 \equiv 2\pmod{5}\) tendríamos que \(t_3 = 2 + 5t_4\) y así

\[x = 140 + 198t_3 = 140 + 198(2 + 5t_4) = 140 + 396 + 990t_4 = 536 + 990t_4.\]

Por lo tanto tenemos que la solución general es \(x = 536 + 990t_4\), donde \(t_4\) es un entero arbitrario.

Sistemas de congruencias lineales de \(2\) variables

Ahora vamos a ver como resolver sistemas de \(2\) congruencias lineales que tienen \(2\) variables.

Definición 54 (Sistema de congruencias lineales de 2 variables )

Un sistema de congruencias lineales de \(2\times 2\) es un sistema formado de dos congruencias lineales de la forma

\[\begin{align*} ax + by \equiv e\pmod{m}, \\ & \\ cx + dy\equiv f\pmod{m}. \end{align*}\]

En donde la solución del sistema lineal es el par \(x\equiv x_0\pmod{m}\), \(y\equiv y_0\pmod{m}\) que satisface ambas congruencias.

Vamos a ver que el método de eliminación que usamos para un sistema de ecuaciones lineales de \(2\times 2\), lo podemos utilizar para resolver los sistemas de congruencias lineales.
Con el siguiente ejemplo vamos a ilustrar el método de eliminación.

Ejemplo 141

Usa el método de eliminación para resolver el siguiente sistema de congruencias lineales

\[\begin{align*} 5x + 6y \equiv 10\pmod{13}, \\ & \\ 6x - 7y\equiv 2\pmod{13}. \end{align*}\]

Solución.

Vamos a eliminar primero la variable \(x\), entonces multiplicamos la primer congruencia por \(6\) y la segunda congruencia por \(5\), y tendríamos que

\[\begin{align*} 30x + 36y \equiv 60\pmod{13}, \\ & \\ 30x - 35y\equiv 10\pmod{13}. \end{align*}\]

Luego, restamos las congruencias y simplificamos los resultados módulo \(13\) para obtener

\[\begin{align*} 71y \equiv 50\pmod{13} \\ & \\ 6y\equiv 11\pmod{13}. \end{align*}\]

Notemos que como \((6,13) = 1|11\) la congruencia tiene solución, además el inverso de \(6\) módulo \(13\) es \(11\), entonces tenemos que

\[\begin{align*} 11\cdot 6y\equiv 11\cdot 11\pmod{13} \\ & \\ 66y\equiv 121\pmod{13} \\ & \\ y\equiv 4\pmod{13}. \end{align*}\]

Para encontrar el valor de \(x\), vamos a sustituir el valor de \(y = 4\) en la primer congruencia del sistema entonces tenemos que

\[\begin{align*} 5x + 6y \equiv 10\pmod{13} \\ & \\ 5x + 6\cdot 4 \equiv 10\pmod{13} \\ & \\ 5x + 24 \equiv 10\pmod{13} \\ & \\ 5x\equiv 10 - 24\pmod{13} \\ & \\ 5x\equiv -14\pmod{13} \\ & \\ 5x\equiv 12\pmod{13}. \end{align*}\]

Nuevamente como \((5,13) = 1|12\) la congruencia tiene solución y además el inverso de \(5\) módulo \(13\) es \(8\), entonces tenemos que

\[\begin{align*} 8\cdot 5x\equiv 8\cdot 12\pmod{13} \\ & \\ 40x\equiv 96\pmod{13} \\ & \\ x\equiv 5\pmod{13}. \end{align*}\]

Así las soluciones son \(x\equiv 5\pmod{13}\) y \(y\equiv 4\pmod{13}\).

El siguiente teorema nos ayuda a determinar si el sistema de congruencias lineales tiene una solución única.

Teorema 58

El sistema lineal

\[\begin{align*} ax + by \equiv e\pmod{m}, \\ & \\ cx + dy\equiv f\pmod{m}, \end{align*}\]

tiene solución única si y solo si \((\Delta, m) = 1\), en donde \(\Delta = ad-bc\pmod{m}\).

Demostración. Supongamos que el sistema tiene una solución, digamos \(x\equiv x_0\pmod{m}\) y \(y\equiv y_0\pmod{m}\), entonces satisface el sistema de congruencias, es decir que

\[\begin{align*} ax_0 + by_0 \equiv e\pmod{m}, \\ & \\ cx_0 + dy_0\equiv f\pmod{m}. \end{align*}\]

Ahora vamos a multiplicar la primer congruencia por \(d\) y la segunda congruencia por \(b\), tenemos que

\[\begin{align*} adx_0 + bdy_0 \equiv ed\pmod{m}, \\ & \\ bcx_0 + bdy_0\equiv bf\pmod{m}. \end{align*}\]

Si restamos las congruencias obtenemos que

\[\begin{align*} adx_0 - bcx_0 \equiv ed-bf\pmod{m}, \\ & \\ (ad-bc)x_0\equiv ed-bf\pmod{m}. \end{align*}\]

Luego por el Corolario 14 tenemos que la congruencia tiene una solución única si y solo si \((\Delta, m) = 1\).

Similarmente, si multiplicamos la primer congruencia por \(-c\) y la segunda congruencia por \(a\) tendríamos que

\[\begin{align*} -acx_0 - bcy_0 \equiv -ce\pmod{m}, \\ & \\ acx_0 + ady_0\equiv af\pmod{m}. \end{align*}\]

Ahora si sumamos las congruencias tenemos que

\[\begin{align*} ady_0 - bcy_0 \equiv af-ce\pmod{m}, \\ & \\ (ad-bc)y_0\equiv af-ce\pmod{m}. \end{align*}\]

Nuevamente por el Corolario 14 tenemos que la congruencia tiene una solución única si y solo si \((\Delta, m) = 1\).
Por lo tanto el sistema tiene solución única módulo \(m\) si y solo si \((\Delta, m) = 1\).\(\square\)

El siguiente teorema nos proporciona como son las soluciones del sistema de congruencias lineales cuando este tiene solución.

Teorema 59

Cuando el sistema de congruencias lineales

\[\begin{align*} ax + by \equiv e\pmod{m}, \\ & \\ cx + dy\equiv f\pmod{m}, \end{align*}\]

tiene solución única módulo \(m\), están dadas por \(x_0\equiv \Delta^{-1}(ed-bf)\pmod{m}\) y \(y_0\equiv \Delta^{-1}(af-ce)\pmod{m}\), en donde \(\Delta = ad-bc\) y \(\Delta^{-1}\) es el inverso de \(\Delta\) módulo \(m\).

Demostración. Por hipótesis tenemos que el sistema tiene solución única, entonces \((\Delta, m) = 1\) y por el Teorema 37 tendríamos que \(\Delta\) tiene inverso módulo \(m\). Entonces se cumple que \(\Delta \Delta^{-1}\equiv 1\pmod{m}\).

Ahora vamos a demostrar que \(x_0\equiv \Delta^{-1}(ed-bf)\pmod{m}\) y \(y_0\equiv \Delta^{-1}(af-ce)\pmod{m}\) satisfacen el sistema, entonces tendríamos que

\[\begin{align*} ax + by &\equiv ax_0 + by_0 \pmod{m} \\ & \\ &\equiv a\Delta^{-1}(ed-bf) + b\Delta^{-1}(af-ce) \pmod{m} \\ & \\ &\equiv aed\Delta^{-1} - abf\Delta^{-1} + abf\Delta^{-1} - bce\Delta^{-1} \pmod{m} \\ & \\ &\equiv aed\Delta^{-1} - bce\Delta^{-1} \pmod{m} \\ & \\ &\equiv e(ad-bc)\Delta^{-1} \pmod{m} \\ & \\ &\equiv e\Delta \Delta^{-1} \pmod{m} \\ & \\ &\equiv e \pmod{m}. \\ \end{align*}\]

Por otro lado también tenemos que

\[\begin{align*} cx + dy &\equiv cx_0 + dy_0 \pmod{m} \\ & \\ &\equiv c\Delta^{-1}(ed-bf) + d\Delta^{-1}(af-ce) \pmod{m} \\ & \\ &\equiv cde\Delta^{-1} - bcf\Delta^{-1} + adf\Delta^{-1} - cde\Delta^{-1} \pmod{m} \\ & \\ &\equiv adf\Delta^{-1} - bcf\Delta^{-1} \pmod{m} \\ & \\ &\equiv f(ad-bc)\Delta^{-1} \pmod{m} \\ & \\ &\equiv f\Delta \Delta^{-1} \pmod{m} \\ & \\ &\equiv f \pmod{m}. \\ \end{align*}\]

Así \(x\equiv x_0\pmod{m}\), \(y\equiv y_0\pmod{m}\) es la única solución del sistema. \(\square\)

Ejemplo 142

Determina si el siguiente sistema de congruencias lineales tiene solución.

\[\begin{align*} 4x - 6y &\equiv 2\pmod{14}, \\ & \\ 7x + 11y &\equiv 11\pmod{14}. \end{align*}\]

Solución.

Primero vamos a calcular el valor de \(\Delta\).

\[\Delta \equiv 4\cdot 11 - 7\cdot (-6) \equiv 44 + 42\equiv 86\equiv 2\pmod{14}.\]

El sistema no tiene una solución única módulo \(14\), ya que como \((2,14) = 2\). Por lo anterior, \(2\) no tiene inverso módulo \(14\) y no podríamos calcular \(\Delta^{-1}\), entonces no podemos calcular las soluciones usando las fórmulas del Teorema 59, sin embargo si podemos usar el método de eliminación para buscarlas.

Multiplicamos la primer congruencia por \(7\) y la segunda congruencia por \(4\) y obtenemos que

\[\begin{align*} 28x - 42y &\equiv 14\pmod{14}, & \\ 28x + 44y &\equiv 44\pmod{14}. \end{align*}\]

Luego si restamos las ecuaciones, tendríamos que

\[\begin{align*} -86y &\equiv -30\pmod{14} \\ & \\ 12y &\equiv 12\pmod{14} \\ & \\ 6y &\equiv 6\pmod{7} \\ & \\ y &\equiv 1\pmod{7}. \\ \end{align*}\]

Por lo tanto \(y = 1\), en general \(y = 1 + 7t\) para algún entero \(t\). Ahora sustituimos esto en la primer congruencia y tenemos que

\[\begin{align*} 4x - 6y &\equiv 2\pmod{14} \\ & \\ 4x - 6 &\equiv 2\pmod{14} \\ & \\ 4x &\equiv 2 + 6\pmod{14} \\ & \\ 4x &\equiv 8\pmod{14} \\ & \\ 2x &\equiv 4\pmod{7} \\ & \\ x &\equiv 2\pmod{7}. \\ & \\ \end{align*}\]

Por lo tanto \(x = 2\) y en general \(x = 2 + 7t\) para algún entero \(t\).

Como la solución no era única módulo \(14\), las dos soluciones que tendríamos serían \(x = 2\),\(y = 1\) y \(x = 9\), \(y = 8\).

Notemos que las fórmulas obtenidas en el Teorema 59 para \(x_0\) y \(y_0\) y el valor de \(\Delta\) los podemos reescribir en términos de determinantes.

\[\begin{align*} \Delta &\equiv ad-bc\equiv \begin{vmatrix} a & b \\ c & d \\ \end{vmatrix} \pmod{m} \\ & \\ x_0 &\equiv \Delta^{-1}(ed-bf)\equiv \Delta^{-1} \begin{vmatrix} e & b \\ f & d \\ \end{vmatrix} \pmod{m} \\ & \\ y_0 &\equiv \Delta^{-1}(af-ce)\equiv \Delta^{-1} \begin{vmatrix} a & e \\ c & f \\ \end{vmatrix} \pmod{m} \\ \end{align*}\]

Sistemas de congruencias lineales en forma matricial

Cuando los sistemas de congruencias lineales son muy grandes es de mucha ayuda usar el lenguaje matricial. En lo que sigue vamos a mostrar los resultados para sistemas de congruencias lineales en general, pero en los ejemplos vamos a trabajar con sistemas pequeños de \(2\times 2\) o \(3\times 3\) para poder mostrarlos.
Lo anterior nos lleva a definir la congruencia entre matrices.

Definición 55 (Matrices congruentes)

Sean \(A\) y \(B\) matrices de tamaño \(n\times k\) donde las entradas son enteros y las entradas de la matriz \(A\) son \(a_{ij}\) y las entradas de la matriz \(B\) son \(b_{ij}\). Diremos que \(A\) es congruente con \(B\) módulo \(m\) si para cada par \((i,j)\) se cumple que \(a_{ij}\equiv b_{ij}\pmod{m}\), en donde \(1\le i\le n\) y \(1\le j\le k.\)
Escribiremos \(A\equiv B\pmod{m}\) si \(A\) es congruente con \(B\) módulo \(m\).

Ejemplo 143

Veamos que las siguientes matrices son congruentes módulo \(13\).

\[\begin{split}A = \begin{pmatrix} 26 & 3 & -2\\ -17 & 14 & 4\\ 2 & 39 & 27 \\ \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 3 & 11\\ 9 & 1 & 17\\ 2 & 0 & 1\\ \end{pmatrix}.\end{split}\]

Como podemos observar se cumplen las siguientes congruencias

\[\begin{align*} 26 &\equiv 0\pmod{13}, & 3 &\equiv 3\pmod{13}, & -2 &\equiv 11\pmod{13}, \\ & \\ -17 &\equiv 9\pmod{13}, & 14 &\equiv 1\pmod{13}, & 4 &\equiv 17\pmod{13}, \\ & \\ 2 &\equiv 2\pmod{13}, & 39 &\equiv 0\pmod{13}, & 27 &\equiv 1\pmod{13}.\\ \end{align*}\]

Por lo tanto se cumple que \(A\equiv B\pmod{13}.\)

Teorema 60

Si \(A\) y \(B\) son matrices de tamaño \(n\times k\), en donde \(A\equiv B\pmod{m}\), \(C\) es una matriz de tamaño \(k\times p\) y \(D\) es una matriz de tamaño \(p\times n\) en donde todas las entradas de las matrices son enteros. Entonces \(AC\equiv BC\pmod{m}\) y \(DA\equiv DB\mod{m}\).

Demostración. Sean \(a_{ij}\), \(b_{ij}\) las entradas de las matrices \(A\) y \(B\) respectivamente, en donde \(1\le i\le n\), \(1\le j\le k\) y \(c_{ij}\) las entradas de la matriz \(C\) para \(1\le i\le k\) y \(1\le j\le p\).

• Primero veamos que \(AC\equiv BC\pmod{m}\).

Si hacemos la operación \(AC\) entonces tendríamos que la \((i,j)\)-ésima entrada de la matriz \(AC\) sería \(\sum_{t=1}^{k}a_{it}c_{tj}\), similarmente si hiciéramos la operación \(BC\) tendríamos que la \((i,j)\)-ésima entrada de la matriz \(BC\) sería \(\sum_{t=1}^{k}b_{it}c_{tj}\), en donde \(1\le i\le n\) y \(1\le j\le k\). Si llegamos a esa expresión habremos terminado.

Por hipótesis tenemos que \(A\equiv B\pmod{m}\) y por la Definición 55 tendríamos que \(a_{it}\equiv b_{it}\pmod{m}\) para toda \(i\) y \(k\). Ahora, usando el Teorema 33 podríamos multiplicar el valor \(c_{tj}\) obteniendo que \(a_{it}c_{tj}\equiv b_{it}c_{tj}\pmod{m}.\) Luego podemos sumar para todos los valores de \(t\) desde \(1\) hasta \(k\) y obtendríamos que

\[\sum_{t=1}^{k}a_{it}c_{tj} \equiv \sum_{t=1}^{k}b_{it}c_{tj}.\]

Por lo tanto se cumple que \(AC\equiv BC\pmod{m}\).

• Ahora veamos que \(DA\equiv DB\mod{m}\).

Primero denotemos las entradas de la matriz \(D\) como \(d_{ij}\), en donde \(1\le i\le p\) y \(1\le j\le n\). Nuevamente, a lo que queremos llegar es ver que la \((i,j)\)-ésima entrada de la matriz \(DA\) es \(\sum_{t=1}^{n}d_{it}a_{tj}\) y la \((i,j)\)-ésima entrada de la matriz \(DB\) sería \(\sum_{t=1}^{n}d_{it}b_{tj}.\)

Similarmente tendríamos que por la Definición 55 tendríamos que \(a_{tj}\equiv b_{tj}\pmod{m}\) para toda \(j\) y \(n\).
En este caso vamos a multiplicar el valor \(d_{it}\) obteniendo que \(d_{it}a_{tj}\equiv d_{it}b_{tj}\pmod{m}.\) Luego podemos sumar para todos los valores de \(t\) desde \(1\) hasta \(n\) y obtendríamos que

\[\sum_{t=1}^{n}d_{it}a_{tj} \equiv \sum_{t=1}^{n}d_{it}b_{tj}.\]

Por lo tanto se cumple que \(DA\equiv DB\pmod{m}\).\(\square\)

Definición 56

El sistema de congruencias lineales módulo \(m\)

\[\begin{align*} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n &\equiv b_1\pmod{m}, \\ & \\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n &\equiv b_2\pmod{m}, \\ & \\ a_{31}x_1 + a_{32}x_2 + \ldots + a_{3n}x_n &\equiv b_3\pmod{m}, \\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + \ldots + a_{nn}x_n &\equiv b_n\pmod{m}. \end{align*}\]

Se puede representar usando notación matricial y es equivalente a

\[AX\equiv B\pmod{m},\]

en donde

\[\begin{split}A = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \ldots & a_{nn}\\ \end{pmatrix}, \quad X = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ \end{pmatrix} , \quad B = \begin{pmatrix} b_1\\ b_2\\ \vdots \\ b_n \\ \end{pmatrix}.\end{split}\]

Ejemplo 144

El sistema de congruencias lineales

\[\begin{align*} x - 2y -z &\equiv 6\pmod{11}, \\ & \\ 2x + 3y + z &\equiv 5\pmod{11}, \\ & \\ 3x + y + 2z &\equiv 2\pmod{11}. \end{align*}\]

Es equivalente en forma matricial a

\[\begin{split} \begin{pmatrix} 1 & -2 & -1 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ z \\ \end{pmatrix} \equiv \begin{pmatrix} 6 \\ 5 \\ 2 \\ \end{pmatrix} \pmod{11}. \end{split}\]

Vamos a presentar algunos resultados previos, después de ellos vamos a poder resolver sistemas de congruencias lineales como los de la Definición 56.

Definición 57 (Matriz inversa)

Si \(A\) y \(\bar{A}\) son matrices de tamaño de \(n\times n\) con entradas enteras y se cumple que \(\bar{A} A\equiv A\bar{A} \equiv I_n\pmod{m}\) en donde \( I_n = \begin{pmatrix} 1 & 0 & \ldots & 0\\ 0 & 1 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1\\ \end{pmatrix}\) es la matriz identidad de tamaño \(n\times n\), entonces decimos que \(\bar{A}\) es la matriz inversa de \(A\) módulo \(m\).

En el siguiente ejemplo vamos a usar el producto de matrices, si no estas familiarizado con esto puedes revisar el siguiente enlace en donde se explica como hacer el producto de matrices.

Ejemplo 145

Veamos que la matriz inversa de \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) es la matriz \(\bar{A} = \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix}\) módulo \(7\).

Vamos a verificar que se cumple la Definición 57.

\[\begin{align*} A \bar{A} &\equiv \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 4\cdot 6 + 5\cdot 1 + 3\cdot 0 & 4\cdot 3 + 5\cdot 2 + 3\cdot 2 & 4\cdot 6 + 5\cdot 0 + 3\cdot 6 \\ 5\cdot 6 + 5\cdot 1 + 2\cdot 0 & 5\cdot 3 + 5\cdot 2 + 2\cdot 2 & 5\cdot 6 + 5\cdot 0 + 2\cdot 6 \\ 3\cdot 6 + 3\cdot 1 + 3\cdot 0 & 3\cdot 3 + 3\cdot 2 + 3\cdot 2 & 3\cdot 6 + 3\cdot 0 + 3\cdot 6 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 24 + 5 + 0 & 12 + 10 + 6 & 24 + 0 + 18 \\ 30 + 5 + 0 & 15 + 10 + 4 & 30 + 0 + 12 \\ 18 + 3 + 0 & 9 + 6 + 6 & 18 + 0 + 18 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 29 & 28 & 42 \\ 35 & 29 & 42 \\ 21 & 21 & 36 \\ \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \equiv I_3 \pmod{7}. \end{align*}\]

\[\begin{align*} \bar{A} A &\equiv \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 6\cdot 4 + 3\cdot 5 + 6\cdot 3 & 6\cdot 5 + 3\cdot 5 + 6\cdot 3 & 6\cdot 3 + 3\cdot 2 + 6\cdot 3 \\ 1\cdot 4 + 2\cdot 5 + 0\cdot 3 & 1\cdot 5 + 2\cdot 5 + 0\cdot 3 & 1\cdot 3 + 2\cdot 2 + 0\cdot 3 \\ 0\cdot 4 + 2\cdot 5 + 6\cdot 3 & 0\cdot 5 + 2\cdot 5 + 6\cdot 3 & 0\cdot 3 + 2\cdot 2 + 6\cdot 3 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 24 + 15 + 18 & 30 + 15 + 18 & 18 + 6 + 18 \\ 4 + 10 + 0 & 5 + 10 + 0 & 3 + 4 + 0 \\ 0 + 10 + 18 & 0 + 10 + 18 & 0 + 4 + 18 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 57 & 63 & 42 \\ 14 & 15 & 7 \\ 28 & 28 & 22 \\ \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \equiv I_3 \pmod{7}. \end{align*}\]

Por lo tanto \(\bar{A}\) es la inversa de \(A\).

Para matrices de tamaño \(2\times 2\), tenemos el siguiente teorema que nos ayuda a encontrar la matriz inversa.

Teorema 61 (Matriz inversa de \(2\times 2\))

Sea \(A = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}\) con entradas enteras, tales que \(\Delta = det(A) = ad - bc\) es primo relativo con el entero positivo \(m\). Entonces la matriz

\[\begin{split} \bar{A} = \bar{ \Delta} \begin{pmatrix} d & -b \\ -c & a \\ \end{pmatrix},\end{split}\]

en donde \(\bar{ \Delta}\) es el inverso de \(\Delta\) módulo \(m\) es la matriz inversa de \(A\) módulo \(m\).

Demostración. Para verificar que \(\bar{A}\) es la inversa de \(A\) módulo \(m\), tenemos que verificar que \(A\bar{A} \equiv \bar{A}A \equiv I_2\pmod{m}\). Notemos que como \((\Delta,m) = 1\) entonces \(\Delta \bar{\Delta} \equiv 1\pmod{m}.\)

Veamos lo siguiente

\[\begin{align*} A\bar{A} &\equiv \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \bar{\Delta} \begin{pmatrix} d & -b \\ -c & a \\ \end{pmatrix} \equiv \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \begin{pmatrix} d \bar{\Delta} & -b\bar{\Delta} \\ -c\bar{\Delta} & a\bar{\Delta} \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} ad\bar{\Delta} -bc\bar{\Delta} & -ab\bar{\Delta} + ab\bar{\Delta} \\ cd\bar{\Delta} -cd\bar{\Delta} & -bc\bar{\Delta} + ad\bar{\Delta} \\ \end{pmatrix} \equiv \begin{pmatrix} (ad-bc)\bar{\Delta} & (-ab+ ab)\bar{\Delta} \\ (cd-cd)\bar{\Delta} & (-bc+ad)\bar{\Delta} \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} \Delta \bar{\Delta} & 0 \\ 0 & \Delta \bar{\Delta} \\ \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \equiv I_2 \pmod{m}. \end{align*}\]

Luego veamos que

\[\begin{align*} \bar{A}A &\equiv \bar{\Delta} \begin{pmatrix} d & -b \\ -c & a \\ \end{pmatrix} \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \equiv \bar{\Delta} \begin{pmatrix} ad-bc & bd-bd \\ -ac+ac & -bc+ad \\ \end{pmatrix} \\ & \\ &\equiv \bar{\Delta} \begin{pmatrix} ad-bc & 0 \\ 0 & -bc+ad \\ \end{pmatrix} \equiv \bar{\Delta} \begin{pmatrix} \Delta & 0 \\ 0 & \Delta \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} \bar{\Delta} \Delta & 0 \\ 0 & \bar{\Delta} \Delta \\ \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \equiv I_2 \pmod{m}. \end{align*}\]

Por lo tanto \(\bar{A}\) es la matriz inversa de \(A\). \(\square\)

Ejemplo 146

Encuentra la matriz inversa de \(A = \begin{pmatrix} 4 & 6 \\ 9 & 2 \\ \end{pmatrix}\) módulo \(13\).

Solución.

Primero vamos a calcular \(\Delta = det(A) = ad - bc = 4\cdot 2 - 6\cdot 9 = 8 - 54 = -46\equiv 6\pmod{13}\). Notemos que \((6,13) = 1\), entonces podemos calcular el inverso de \(6\) módulo \(13\) entonces tenemos que \(\bar{\Delta} = 11\). Luego tendríamos que la matriz inversa es

\[\begin{align*} \bar{A} &\equiv \bar{\Delta} \begin{pmatrix} d & -b \\ -c & a \\ \end{pmatrix} \\ & \\ &\equiv 11\cdot \begin{pmatrix} 2 & -6 \\ -9 & 4 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 2\cdot 11 & -6\cdot 11 \\ -9\cdot 11 & 4\cdot 11 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 22 & -66 \\ -99 & 44 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 9 & 12 \\ 5 & 5 \\ \end{pmatrix}. \end{align*}\]

Ya vimos como calcular el determinante de una matriz de tamaño \(2\times 2\), para calcular el determinante de matrices de tamaño \(n\times n\) en donde \(n>2\) podemos consultar las siguientes notas de Álgebra Superior I.

Veamos un ejemplo de como calcular el determinante de una matriz de tamaño de \(3\times 3\).

Ejemplo 147

Calcula el determinante de la matriz \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) módulo \(7\).

Solución.

Recordemos que los signos correspondientes a las entradas de una matriz de \(3\times 3\) son,

\[\begin{split}\begin{pmatrix} + & - & + \\ - & + & - \\ + & - & + \\ \end{pmatrix}.\end{split}\]

Primero tenemos que seleccionar una fila o columna de la matriz, en este caso vamos a seleccionar primer fila, es decir

\[\begin{split}\begin{pmatrix} \fbox{4} & \fbox{5} & \fbox{3} \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}.\end{split}\]

Ahora vamos a calcular lo siguiente, \(sign(1,j)\cdot a_{1j}\cdot det(A_{1j})\), en donde \(sign(1,j)\) es el signo correspondiente a la entrada \(a_{1j}\) de la matriz \(A\) y \(A_{1j}\) es la matriz resultante de tapar la fila \(1\) y la columna \(j\) para \(j = 1,2,3\).

Calculemos las matrices \(A_{1j}.\)

\[\begin{align*} A_{11} &= \begin{pmatrix} \Box & \Box & \Box \\ \Box & 5 & 2 \\ \Box & 3 & 3 \\ \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 3 & 3 \\ \end{pmatrix} \\ & \\ A_{12} &= \begin{pmatrix} \Box & \Box & \Box \\ 5 & \Box & 2 \\ 3 & \Box & 3 \\ \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 3 & 3 \\ \end{pmatrix} \\ & \\ A_{13} &= \begin{pmatrix} \Box & \Box & \Box \\ 5 & 5 & \Box \\ 3 & 3 & \Box \\ \end{pmatrix} = \begin{pmatrix} 5 & 5 \\ 3 & 3 \\ \end{pmatrix} \\ \end{align*}\]

Entonces tendríamos que el determinante es

\[\begin{align*} det(A) &= +a_{11}\cdot det(A_{11}) - a_{12}\cdot det(A_{12}) + a_{13}\cdot det(A_{13}) \\ & \\ &= 4\begin{vmatrix} 5 & 2 \\ 3 & 3 \\ \end{vmatrix} - 5\begin{vmatrix} 5 & 2 \\ 3 & 3 \\ \end{vmatrix} + 3\begin{vmatrix} 5 & 5 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= 4(5\cdot 3 - 3\cdot 2) - 5(5\cdot 3 - 3\cdot 2) + 3(5\cdot 3 - 3\cdot 5) \\ & \\ & = 4(15 - 6) - 5(15 - 6) + 3(15 - 15) \\ & \\ & = 4\cdot 9 - 5\cdot 9 + 3\cdot 0 =36 - 45 = -9. \\ \end{align*}\]

Finalmente calculamos el valor módulo \(7\). Por lo tanto tenemos que \(det(A) = -9\equiv 5\pmod{7}.\)

Para encontrar la inversa de matrices de tamaño de \(n\times n\) en donde \(n > 2\), necesitamos los siguientes resultados de álgebra lineal.

Definición 58 (Matriz adjunta)

La matriz adjunta de una matriz \(A\) de tamaño \(n\times n\) es la matriz de tamaño \(n\times n\) con la \((i,j)\)-ésima entrada es \(C_{ji}\), en donde \(C_{ij} = (-1)^{i+j}\cdot det(A_{ij})\), donde \(A_{ij}\) es la matriz obtenida al eliminar la \(i\)-ésima fila y la \(j\)-ésima columna de \(A\). La matriz adjunta de una matriz \(A\) la vamos a denotar como \(adj(A)\).

Veamos un ejemplo para ilustrar como calcular la matriz adjunta.

Ejemplo 148

Calcula la matriz adjunta de \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) módulo \(7\).

Solución.

Primero necesitamos calcular los valores de \(C_{ij}\).

Vamos a calcular \(C_{11}\).
Para calcular \(A_{11}\) vamos a eliminar la fila \(1\) y la columna \(1\), es decir

\[\begin{split} A_{11} = \begin{pmatrix} \Box & \Box & \Box \\ \Box & 5 & 2 \\ \Box & 3 & 3 \\ \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 3 & 3 \\ \end{pmatrix}.\end{split}\]

Entonces tenemos que

\[\begin{align*} C_{11} &= (-1)^{1+1} \cdot det(A_{11}) \\ & \\ &\equiv (-1)^{1+1} \begin{vmatrix} 5 & 2 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= (-1)^2 \cdot (5\cdot 3 - 3\cdot 2) \\ & \\ &= 1\cdot (15 - 6) \\ & \\ &= 9. \end{align*}\]

Calculemos \(C_{12}\).
Para calcular \(A_{12}\), eliminamos la fila \(1\) y la columna \(2\), es decir

\[\begin{split}A_{12} = \begin{pmatrix} \Box & \Box & \Box \\ 5 & \Box & 2 \\ 3 & \Box & 3 \\ \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 3 & 3 \\ \end{pmatrix}.\end{split}\]

Entonces tenemos que

\[\begin{align*} C_{12} &= (-1)^{1+2}\cdot det(A_{12}) \\ & \\ &= (-1)^{1+2} \begin{vmatrix} 5 & 2 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= (-1)^3 \cdot (5\cdot 3 - 3\cdot 2) \\ & \\ &= (-1)\cdot (15 - 6) \\ & \\ &= -9. \end{align*}\]

Calculemos \(C_{13}\).
Para calcular \(A_{13}\), eliminamos la fila \(1\) y la columna \(3\), es decir

\[\begin{split}A_{13} = \begin{pmatrix} \Box & \Box & \Box \\ 5 & 5 & \Box \\ 3 & 3 & \Box \\ \end{pmatrix} = \begin{pmatrix} 5 & 5 \\ 3 & 3 \\ \end{pmatrix}.\end{split}\]

Entonces tenemos que

\[\begin{align*} C_{13} &= (-1)^{1+3} \cdot det(A_{13}) \\ & \\ &= (-1)^{1+3} \begin{vmatrix} 5 & 5 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= (-1)^4 \cdot (5\cdot 3 - 3\cdot 5) \\ & \\ &= 1\cdot (15 - 15) \\ & \\ &= 0. \end{align*}\]

Calculemos \(C_{21}\). Para calcular \(A_{21}\), eliminamos la fila \(2\) y la columna \(1\), es decir

\[\begin{split}A_{21} = \begin{pmatrix} \Box & 5 & 3 \\ \Box & \Box & \Box \\ \Box & 3 & 3 \\ \end{pmatrix} = \begin{pmatrix} 5 & 3 \\ 3 & 3 \\ \end{pmatrix}.\end{split}\]

\[\begin{align*} C_{21} &= (-1)^{2+1} \cdot det(A_{21}) \\ & \\ &= (-1)^{2+1} \begin{vmatrix} 5 & 3 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= (-1)^3 \cdot (5\cdot 3 - 3\cdot 3) \\ & \\ &= (-1)\cdot (15 - 9) \\ & \\ &= -6. \end{align*}\]

Calculemos \(C_{22}\). Para calcular \(A_{22}\), eliminamos la fila \(2\) y la columna \(2\), es decir

\[\begin{split}A_{22} = \begin{pmatrix} 4 & \Box & 3 \\ \Box & \Box & \Box \\ 3 & \Box & 3 \\ \end{pmatrix} = \begin{pmatrix} 4 & 3 \\ 3 & 3 \\ \end{pmatrix}.\end{split}\]

\[\begin{align*} C_{22} &= (-1)^{2+2} \cdot det(A_{22}) \\ & \\ &= (-1)^{2+2} \begin{vmatrix} 4 & 3 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= (-1)^4 \cdot (4\cdot 3 - 3\cdot 3) \\ & \\ &= 1\cdot (12 - 9) \\ & \\ &= 3. \end{align*}\]

Calculemos \(C_{23}\). Para calcular \(A_{23}\), eliminamos la fila \(2\) y la columna \(3\), es decir

\[\begin{split}A_{23} = \begin{pmatrix} 4 & 5 & \Box \\ \Box & \Box & \Box \\ 3 & 3 & \Box \\ \end{pmatrix} = \begin{pmatrix} 4 & 5 \\ 3 & 3 \\ \end{pmatrix}.\end{split}\]

\[\begin{align*} C_{23} &= (-1)^{2+3}\cdot det(A_{23}) \\ & \\ &= (-1)^{2+3} \begin{vmatrix} 4 & 5 \\ 3 & 3 \\ \end{vmatrix} \\ & \\ &= (-1)^5 \cdot (4\cdot 3 - 3\cdot 5) \\ & \\ &= (-1)\cdot (12 - 15) \\ & \\ &= 3. \end{align*}\]

Calculemos \(C_{31}\). Para calcular \(A_{31}\), eliminamos la fila \(3\) y la columna \(1\), es decir

\[\begin{split}A_{31} = \begin{pmatrix} \Box & 5 & 3 \\ \Box & 5 & 2 \\ \Box & \Box & \Box \\ \end{pmatrix} = \begin{pmatrix} 5 & 3 \\ 5 & 2 \\ \end{pmatrix}.\end{split}\]

\[\begin{align*} C_{31} &= (-1)^{3+1}\cdot det(A_{31}) \\ & \\ &= (-1)^{3+1} \begin{vmatrix} 5 & 3 \\ 5 & 2 \\ \end{vmatrix} \\ & \\ &= (-1)^4 \cdot (5\cdot 2 - 5\cdot 3) \\ & \\ &= 1\cdot (10 - 15) \\ & \\ &= -5. \end{align*}\]

Calculemos \(C_{32}\). Para calcular \(A_{32}\), eliminamos la fila \(3\) y la columna \(2\), es decir

\[\begin{split}A_{32} = \begin{pmatrix} 4 & \Box & 3 \\ 5 & \Box & 2 \\ \Box & \Box & \Box \\ \end{pmatrix} = \begin{pmatrix} 4 & 3 \\ 5 & 2 \\ \end{pmatrix}.\end{split}\]

\[\begin{align*} C_{32} &= (-1)^{3+2}\cdot det(A_{32}) \\ & \\ &= (-1)^{3+2} \begin{vmatrix} 4 & 3 \\ 5 & 2 \\ \end{vmatrix} \\ & \\ &= (-1)^5 \cdot (4\cdot 2 - 5\cdot 3) \\ & \\ &= (-1)\cdot (8 - 15) \\ & \\ &= 7. \end{align*}\]

Calculemos \(C_{33}\). Para calcular \(A_{33}\), eliminamos la fila \(3\) y la columna \(3\), es decir

\[\begin{split}A_{33} = \begin{pmatrix} 4 & 5 & \Box \\ 5 & 5 & \Box \\ \Box & \Box & \Box \\ \end{pmatrix} = \begin{pmatrix} 4 & 5 \\ 5 & 5 \\ \end{pmatrix}.\end{split}\]

\[\begin{align*} C_{33} &= (-1)^{3+3}\cdot det(A_{33}) \\ & \\ &= (-1)^{3+3} \begin{vmatrix} 4 & 5 \\ 5 & 5 \\ \end{vmatrix} \\ & \\ &= (-1)^6 \cdot (4\cdot 5 - 5\cdot 5) \\ & \\ &= 1\cdot (20 - 25) \\ & \\ &= -5. \end{align*}\]

Ahora, la \((i,j)\)-ésima entrada de la matriz adjunta es el valor \(C_{ji}\), entonces la matriz adjunta es

\[\begin{split}adj(A) = \begin{pmatrix} 9 & -6 & -5 \\ -9 & 3 & 7 \\ 0 & 3 & -5 \\ \end{pmatrix} \equiv \begin{pmatrix} 2 & 1 & 2 \\ 5 & 3 & 0 \\ 0 & 3 & 2 \\ \end{pmatrix} \pmod{7}.\end{split}\]

Teorema 62

Si \(A\) es una matriz de tamaño \(n\times n\) con \(det(A)\neq 0\), entonces se cumple que \(A\cdot adj(A) = det(A)\cdot I_n\), en donde \(adj(A)\) es la matriz adjunta de \(A\) y \(I_n\) es la matriz identidad de tamaño \(n\times n\).

Vamos a usar los valores calculados en los ejemplos Ejemplo 147 y Ejemplo 148 para ver que se cumple el teorema.

Ejemplo 149

Sea \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\), verifica que se cumple el Teorema 62.

Solución.

Ya calculamos que \(det(A) = 5\pmod{7}\) y que \(adj(A) = \begin{pmatrix} 2 & 1 & 2 \\ 5 & 3 & 0 \\ 0 & 3 & 2 \\ \end{pmatrix} \pmod{7}.\)

Entonces tendríamos que

\[\begin{align*} A\cdot adj(A) &\equiv \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \begin{pmatrix} 2 & 1 & 2 \\ 5 & 3 & 0 \\ 0 & 3 & 2 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 4\cdot 2 + 5\cdot 5 + 3\cdot 0 & 4\cdot 1 + 5\cdot 3 + 3\cdot 3 & 4\cdot 2 + 5\cdot 0 + 3\cdot 2 \\ 5\cdot 2 + 5\cdot 5 + 2\cdot 0 & 5\cdot 1 + 5\cdot 3 + 2\cdot 3 & 5\cdot 2 + 5\cdot 0 + 2\cdot 2 \\ 3\cdot 2 + 3\cdot 5 + 3\cdot 0 & 3\cdot 1 + 3\cdot 3 + 3\cdot 3 & 3\cdot 2 + 3\cdot 0 + 3\cdot 2 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 8 + 25 + 0 & 4 + 15 + 9 & 8 + 0 + 6 \\ 10 + 25 + 0 & 5 + 15 + 6 & 10 + 0 + 4 \\ 6 + 15 + 0 & 3 + 9 + 9 & 6 + 0 + 6 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 33 & 28 & 14 \\ 35 & 26 & 14 \\ 21 & 21 & 12 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 5 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 5 \\ \end{pmatrix} \\ & \\ &\equiv 5 \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \\ & \\ &\equiv det(A)\cdot I_3 \pmod{7}. \end{align*}\]

Teorema 63 (Matriz inversa módulo \(m\))

Si \(A\) es una matriz de tamaño \(n\times n\) con entradas enteras y \(m\) es un entero positivo tal que \((det(A),m) = 1\), entonces la matriz \(\bar{A} = \bar{\Delta} \cdot adj(A)\) es una matriz inversa de \(A\) módulo \(m\), en donde \(\bar{\Delta}\) es el inverso de \(\Delta = det(A)\) módulo \(m\).

Demostración. Como \((det(A),m) = 1\), sabemos que \(det(A) \neq 0\), luego por el Teorema 62 tendríamos que

\[A\cdot adj(A) = det(A)\cdot I_n = \Delta \cdot I_n.\]

Ya que \((\Delta,m)= 1\) entonces existe \(\bar{\Delta}\) que es el inverso de \(\Delta\) módulo \(m\).
Entonces vamos a ver que se cumple la Definición 57 para \(A\) y para \(\bar{A} = \bar{\Delta} \cdot adj(A)\).

• Primero revisemos que pasa con \(A\bar{A}\).

\[A\bar{A} \equiv A (\bar{\Delta} \cdot adj(A)) \equiv (A\cdot adj(A)) \cdot \bar{\Delta} \equiv \Delta \cdot I_n \cdot \bar{\Delta} \equiv I_n \pmod{m}.\]

• Ahora veamos que pasa con \(\bar{A} A\).

\[\bar{A} A \equiv (\bar{\Delta} \cdot adj(A)) A \equiv \bar{\Delta} \cdot (A\cdot adj(A)) \equiv \bar{\Delta} \cdot det(A)\cdot I_n \equiv I_n \pmod{m}.\]

Por lo tanto \(\bar{A} = \bar{ \Delta} \cdot adj(A)\) es la inversa de \(A\) módulo \(m\). \(\square\)

Con el Teorema 63 tenemos lo necesario para encontrar la matriz inversa de una matriz de tamaño \(n\times n\).

Ejemplo 150

Dada la matriz \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\), calcula su matriz inversa módulo \(7\).

Solución.

Vamos a usar Teorema 63 para encontrar la matriz inversa. Ya tenemos los cálculos del determinante y la matriz adjunta los cuales son

\[\begin{align*} det(A) &\equiv 5\pmod{7}, \\ & \\ adj(A) &\equiv \begin{pmatrix} 2 & 1 & 2 \\ 5 & 3 & 0 \\ 0 & 3 & 2 \\ \end{pmatrix} \pmod{7}. \end{align*}\]

Como \((5,7) = 1\), entonces tenemos que \(\bar{\Delta} = 3\),

Luego la matriz inversa sería

\[\begin{align*} \bar{A} &\equiv 3\cdot adj(A) \\ & \\ &\equiv 3\cdot \begin{pmatrix} 2 & 1 & 2 \\ 5 & 3 & 0 \\ 0 & 3 & 2 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 6 & 3 & 6 \\ 15 & 9 & 0 \\ 0 & 9 & 6 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \pmod{7} \\ \end{align*}\]

Por último vamos a comprobar que \(\bar{A}\) sí es una matriz inversa de \(A\).

\[\begin{align*} A \bar{A} &\equiv \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 4\cdot 6 + 5\cdot 1 + 3\cdot 0 & 4\cdot 3 + 5\cdot 2 + 3\cdot 2 & 4\cdot 6 + 5\cdot 0 + 3\cdot 6 \\ 5\cdot 6 + 5\cdot 1 + 2\cdot 0 & 5\cdot 3 + 5\cdot 2 + 2\cdot 2 & 5\cdot 6 + 5\cdot 0 + 2\cdot 6 \\ 3\cdot 6 + 3\cdot 1 + 3\cdot 0 & 3\cdot 3 + 3\cdot 2 + 3\cdot 2 & 3\cdot 6 + 3\cdot 0 + 3\cdot 6 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 24 + 5 + 0 & 12 + 10 + 6 & 24 + 0 + 18 \\ 30 + 5 + 0 & 15 + 10 + 4 & 30 + 0 + 12 \\ 18 + 3 + 0 & 9 + 6 + 6 & 18 + 0 + 18 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 29 & 28 & 42 \\ 35 & 29 & 42 \\ 21 & 21 & 36 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \pmod{7}. \\ & \\ \end{align*}\]

\[\begin{align*} \bar{A} A &\equiv \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 6\cdot 4 + 3\cdot 5 + 6\cdot 3 & 6\cdot 5 + 3\cdot 5 + 6\cdot 3 & 6\cdot 3 + 3\cdot 2 + 6\cdot 3 \\ 1\cdot 4 + 2\cdot 5 + 0\cdot 3 & 1\cdot 5 + 2\cdot 5 + 0\cdot 3 & 1\cdot 3 + 2\cdot 2 + 0\cdot 3 \\ 0\cdot 4 + 2\cdot 5 + 6\cdot 3 & 0\cdot 5 + 2\cdot 5 + 6\cdot 3 & 0\cdot 3 + 2\cdot 2 + 6\cdot 3 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 24 + 15 + 18 & 30 + 15 + 18 & 18 + 6 + 18 \\ 4 + 10 + 0 & 5 + 10 + 0 & 3 + 4 + 0 \\ 0 + 10 + 18 & 0 + 10 + 18 & 0 + 4 + 18 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 57 & 63 & 42 \\ 14 & 15 & 7 \\ 28 & 28 & 22 \\ \end{pmatrix} \\ & \\ &\equiv \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \pmod{7}. \\ & \\ \end{align*}\]

Por lo tanto se cumple que \(A\bar{A} \equiv \bar{A} A \equiv I_3 \pmod{7}\).

Observación 10

Con todo lo anterior desarrollado podemos utilizar la matriz inversa de \(A\) módulo \(m\) para resolver el sistema

\[AX \equiv B\pmod{m},\]

en donde \((det(A),m) = 1\). Si multiplicamos la matriz inversa de \(A\) por ambos lados tendríamos que

\[\begin{align*} \bar{A}\left(AX \right) &\equiv \bar{A}B\pmod{m} \\ & \\ ( \bar{A} A )X &\equiv \bar{A}B\pmod{m} \\ & \\ X &\equiv \bar{A}B\pmod{m}. \end{align*}\]

Por lo tanto encontramos la solución \(X\) que es \(\bar{A}B \pmod{m}.\)

Para terminar esta sección, veamos un ejemplo de un sistema de congruencias de \(3\) congruencias con \(3\) variables.

Ejemplo 151

Resuelve el sistema de congruencias lineales

\[\begin{align*} 4x_1 + 5x_2 + 3x_3 &\equiv 4\pmod{7}, \\ & \\ 5x_1 + 5x_2 + 2x_3 &\equiv 5\pmod{7}, \\ & \\ 3x_1 + 3x_2 + 3x_3 &\equiv 1\pmod{7}. \\ \end{align*}\]

Solución.

El sistema anterior lo podemos escribir en notación matricial y es equivalente a

\[\begin{split}\begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \end{pmatrix} \equiv \begin{pmatrix} 4 \\ 5 \\ 1 \\ \end{pmatrix} \pmod{7}.\end{split}\]

Por la observación Observación 10 para resolver el sistema tendríamos que multiplicar la matriz inversa, recordemos que en el Ejemplo 150 calculamos la matriz inversa de \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) la cual es \(\bar{A} = \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix}\), entonces tendríamos lo siguiente

\[\begin{align*} \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \end{pmatrix} &\equiv \begin{pmatrix} 4 \\ 5 \\ 1 \\ \end{pmatrix} \pmod{7} \\ & \\ \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \end{pmatrix} &\equiv \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix} \begin{pmatrix} 4 \\ 5 \\ 1 \\ \end{pmatrix} \pmod{7} \\ & \\ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \end{pmatrix} &\equiv \begin{pmatrix} 6\cdot 4 + 3\cdot 5 + 6\cdot 1 \\ 1\cdot 4 + 2\cdot 5 + 0\cdot 1 \\ 0\cdot 4 + 2\cdot 5 + 6\cdot 1 \\ \end{pmatrix} \pmod{7} \\ & \\ \begin{pmatrix} 1x_1 + 0x_2 + 0x_3 \\ 0x_1 + 1x_2 + 0x_3 \\ 0x_1 + 0x_2 + 1x_3 \\ \end{pmatrix} &\equiv \begin{pmatrix} 24 + 15 + 6 \\ 4 + 10 + 0 \\ 0 + 10 + 6 \\ \end{pmatrix} \pmod{7} \\ & \\ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \end{pmatrix} &\equiv \begin{pmatrix} 45 \\ 14 \\ 16 \\ \end{pmatrix} \pmod{7} \\ & \\ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \end{pmatrix} &\equiv \begin{pmatrix} 3 \\ 0 \\ 2 \\ \end{pmatrix} \pmod{7}. \\ & \\ \end{align*}\]

Por lo tanto tendríamos que \(x_1\equiv 3\pmod{7}\), \(x_2\equiv 0\pmod{7}\) y \(x_3\equiv 2\pmod{7}.\)

Comprobemos estas soluciones.

\[\begin{align*} 4\cdot 3 + 5\cdot 0 + 3\cdot 2 &\equiv 12 + 0 + 6 \equiv 18\equiv 4\pmod{7} \\ & \\ 5\cdot 3 + 5\cdot 0 + 2\cdot 2 &\equiv 15 + 0 + 4 \equiv 19\equiv 5\pmod{7} \\ & \\ 3\cdot 3 + 3\cdot 0 + 3\cdot 2 &\equiv 9 + 0 + 6 \equiv 15\equiv 1\pmod{7}. \\ \end{align*}\]

El método que mostramos para resolver los sistemas de congruencias no es el único, puedes adaptar métodos de Álgebra lineal para resolver este tipo de sistemas, en donde la división es siempre reemplazada por el inverso módulo \(m\).

Código para resolver un sistema de congruencias

El siguiente código nos servirá para resolver sistemas de congruencias lineales con \(n\) variables y \(n\) congruencias, para ellos vamos a utilizar el método mostrado en esta sección.
Primero vamos a crear las funciones necesarias para calcular el producto de matrices, el determinante y la matriz adjunta.
Como ejemplo, para estos códigos vamos a usar la matriz del Ejemplo 151

\[\begin{split}A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}.\end{split}\]

Además, vamos a utilizar listas para representar las matrices, es decir, si tenemos la matriz

\[\begin{split}A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{pmatrix},\end{split}\]

representada en código se vería como

A = [[a,b,c], [d,e,f], [g,h,i]]

La siguiente función nos ayuda a calcular el producto entre matrices módulo \(m\).

def matrices_producto(matriz_A,matriz_B,m):
    col_A = len(matriz_A[0])
    fil_A = len(matriz_A)
    col_B = len(matriz_B[0])
    fil_B = len(matriz_B)
    producto = [[0 for a in range(col_B)] for b in range(fil_A)]
    if col_A != fil_B:
        return print(f"Las matrices no se pueden multiplicar ya que las columnas de A son diferentes a las filas de B")

    else:
        for i in range(fil_A):
            for j in range(col_B):
                for k in range(fil_B):
                    producto[i][j] += matriz_A[i][k]*matriz_B[k][j]
                    producto[i][j] %= m
    return producto 

matriz_A = [[4,5,3],[5,5,2],[3,3,3]]
matriz_B = [[6,3,6],[1,2,0],[0,2,6]]

matrices_producto(matriz_A, matriz_B,7)

[[1, 0, 0], [0, 1, 0], [0, 0, 1]]

La siguiente función nos ayuda a calcular el determinante de una matriz de tamaño de \(n\times n\).

def calcular_determinante(matriz,m):
    if len(matriz) != len(matriz[0]):
        return print("La matriz no es cuadrada")
    
    if len(matriz) == 2:
        return matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0]
    
    determinante = 0

    for columna in range(len(matriz)):
        submatriz = [fila[:columna] + fila[columna + 1:] for fila in matriz[1:]]
        sign = (-1)**columna
        cofactor = sign * matriz[0][columna] * calcular_determinante(submatriz,m)
        determinante += cofactor 
    return determinante % m 

matriz_A = [[4,5,3],[5,5,2],[3,3,3]]

calcular_determinante(matriz_A,7)

5

La siguiente función nos ayuda a calcular la matriz adjunta de una matriz de tamaño de \(n\times n\).

def calcular_adjunta(matriz,m):
    n = len(matriz)
    adjunta = []

    for i in range(n):
        adjunta_fila = []
        for j in range(n):
            submatriz = [fila[:j] + fila[j+1:] for fila in (matriz[:i] + matriz[i+1:])]
            signo = (-1)**(i+j)
            cofactor = signo * calcular_determinante(submatriz,m)
            cofactor %= m
            adjunta_fila.append(cofactor)
        adjunta.append(adjunta_fila)
    
    adjunta = [list(fila) for fila in zip(*adjunta)]
    return adjunta

matriz_A = [[4,5,3],[5,5,2],[3,3,3]]

calcular_adjunta(matriz_A,7)

[[2, 1, 2], [5, 3, 0], [0, 3, 2]]

Las siguientes funciones nos ayudarán a calcular el máximo común divisor y a encontrar el inverso del determinante módulo \(m\).

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return b

def inverso_modn(a,m):  
    if a >= m or a < 0:
        a = a%m
    d = algoritmo_euclides(a,m)    
    if d == 1:
        for i in range(1,m):
            if (a*i)%m == 1:
                return i 

La siguiente función nos ayudara a resolver un sistema de congruencias lineales de tamaño \(n\times n\).

def resolver_sis_congr (A,b,m):
    determinante = calcular_determinante(A,m) 
    
    if algoritmo_euclides(determinante,m) == 1:
        det_inverso = inverso_modn(determinante,m) 
        adjunta_A = calcular_adjunta(A,m)
        inversa_A = [[(det_inverso * a_ij)%m for a_ij in fila] for fila in adjunta_A]
        resultado = matrices_producto(inversa_A,b,m)
        return resultado
    else:
        return print(f"El determinante {determinante} no tiene inverso módulo {m}")

Vamos a resolver el siguiente sistema de congruencias con el código realizado.

\[\begin{align*} 4x_1 + 5x_2 + 3x_3 &\equiv 4\pmod{7}, \\ & \\ 5x_1 + 5x_2 + 2x_3 &\equiv 5\pmod{7}, \\ & \\ 3x_1 + 3x_2 + 3x_3 &\equiv 1\pmod{7}. \\ \end{align*}\]

A = [[4,5,3],[5,5,2],[3,3,3]]
b = [[4], [5], [1]]

resolver_sis_congr(A,b,7)

[[3], [0], [2]]

Ahora resolvamos el siguiente sistema de congruencias con el código realizado.

\[\begin{align*} 2x_1 + 5x_2 + 6x_3 &\equiv 3\pmod{7}, \\ & \\ 2x_1 + x_3 &\equiv 4\pmod{7}, \\ & \\ x_1 + 2x_2 + 3x_3 &\equiv 1\pmod{7}. \\ \end{align*}\]

A = [[2,5,6],[2,0,1],[1,2,3]]
b = [[3], [4], [1]]

resolver_sis_congr(A,b,7)

[[4], [1], [3]]

Hay que notar que aunque el algoritmo utilizado para resolver los sistemas de congruencias funciona, no es óptimo cuando se trata de matrices grandes, lo que significa que el tiempo de cálculo crece muy rápidamente a medida que aumenta el tamaño de la matriz. Para matrices de tamaño \(2\times 2\) y \(3\times 3\), el código se realiza en un tiempo aceptable, pero para matrices de tamaño más grande que \(10\times 10\), el tiempo de ejecución se vuelve muy grande.

Explicación del código

En este capítulo vimos que podemos crear una lista de listas usando la comprensión de listas dentro de una comprensión de lista, esto nos funcionó para crear una matriz en donde todas sus entradas son ceros.

matriz = [[0 for a in range(n)] for b in range(m)]

Lo que hace el código es ejecutar primero la comprensión de listas interior creando una lista que contiene \(n\) elementos, luego esta lista se genera \(m\) veces lo que da como resultado una lista que contiene \(m\) listas, es decir una matriz de \(n\times m\) en donde todas las entradas son cero.

Vimos una nueva forma de seleccionar elementos en una lista.

lista = [1,2,3,4,5,6,7,8]
lista_1 = lista[:4]
lista_2 = lista[4:]

La variable «lista_1» nos regresaría la lista \([1,2,3,4]\), utilizamos el símbolo : para indicar que queremos seleccionar desde el primer elemento con índice \(0\) hasta el elemento con índice \(3\), recordemos que python toma una elemento anterior por la derecha al que le indiquemos.

La variable «lista_2» nos regresaría la lista \([5,6,7,8]\), en este caso utilizamos el símbolo : para indicarle a python que queremos seleccionar desde el elemento con índice \(4\) hasta el último de la lista.

El uso que le dimos a esta forma de selección fue para quitar elementos intermedios de una lista.

lista = [1,2,3,4,5,6,7,8]
lista_1 = lista[:4]
lista_2 = lista[5:]
lista_3 = lista_1 + lista_2

El valor de la variable «lista_3» sería una lista sin el elemento con el índice \(4\) de la lista original, es decir que tendríamos la lista \([1,2,3,4,6,7,8]\).

También vimos la función zip() el cual nos ayuda a desempaquetar, lo que hace es combinar las listas de una lista de listas, es decir que transpone la matriz. Veamos el siguiente ejemplo que nos ayudara a comprender que sucede al aplicar esta función a una lista de listas.

matriz = [[a1, a2, a3],[b1, b2, b3], [c1, c2, c3]]
transponer  = zip(*matriz)

El resultado de la variable «transponer» sería una lista de tuplas es decir \([(a_1, b_1, c_1), (a_2, b_2, c_2), (a_3, b_3,c_3)]\).
Representado con matrices tendríamos que la matriz

\[\begin{split}A = \begin{pmatrix} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \\ \end{pmatrix}.\end{split}\]

Se convierte en la matriz

\[\begin{split}A_T = \begin{pmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \\ a_3 & b_3 & c_3 \\ \end{pmatrix}.\end{split}\]

Veamos como funciona el código para hacer el producto de matrices.

def matrices_producto(matriz_A,matriz_B,m):
    col_A = len(matriz_A[0])
    fil_A = len(matriz_A)
    col_B = len(matriz_B[0])
    fil_B = len(matriz_B)
    producto = [[0 for a in range(col_B)] for b in range(fil_A)]
    if col_A != fil_B:
        return print(f"Las matrices no se pueden multiplicar ya que las columnas de A son diferentes a las filas de B")

    else:
        for i in range(fil_A):
            for j in range(col_B):
                for k in range(fil_B):
                    producto[i][j] += matriz_A[i][k]*matriz_B[k][j]
                    producto[i][j] %= m
    return producto

1. Definimos una función llamada «matrices_producto» la cual recibe \(3\) argumentos, los dos primeros son matrices que deben estar escritas en forma de listas de listas y el tercero es un valor entero el cual es el módulo.
   Enseguida creamos \(4\) variables «col_A», «fil_A», «col_b» y «fil_B» las cuales con ayuda de la función len() nos sirven para saber cuántas filas y columnas tienen las matrices que se introducen en la función.

def matrices_producto(matriz_A,matriz_B,m):
    col_A = len(matriz_A[0])
    fil_A = len(matriz_A)
    col_B = len(matriz_B[0])
    fil_B = len(matriz_B)

2. Creamos la variable «producto» la cual es una lista de comprensión dentro de otra lista de comprensión y genera una matriz la cual contiene puros ceros en sus entradas.

    producto = [[0 for a in range(col_B)] for b in range(fil_A)]

3. Luego creamos un condicional if en el cual la condición es, si las columnas de la primer matriz no son iguales a las filas de la segunda matriz, el código nos imprime la leyenda de que las matrices no se pueden multiplicar. En el caso en que las columnas y fila si tengan la misma cantidad, pasamos al condicional else, el cual contiene tres ciclos for. El primer ciclo recorre los índices de las filas de la primer matriz, el segundo ciclo recorre los índices de las columnas de la segunda matriz y el tercer ciclo recorre las filas de la segunda matriz. Luego en la variable «producto[ i ][ j ]» se va guardando la suma del producto entre el elemento de la fila \(i\) y columna \(k\) de la primer matriz por el elemento de la fila \(k\) y columna \(j\) de la segunda matriz en cada iteración al resultado se le aplica módulo \(m\). Finalmente la función nos regresa como resultado la matriz «producto».

    if col_A != fil_B:
        return print(f"Las matrices no se pueden multiplicar ya que las columnas de A son diferentes a las filas de B")

    else:
        for i in range(fil_A):
            for j in range(col_B):
                for k in range(fil_B):
                    producto[i][j] += matriz_A[i][k]*matriz_B[k][j]
                    producto[i][j] %= m
    return producto

Ahora veamos el código para calcular el determinante de una matriz.

def calcular_determinante(matriz,m):
    if len(matriz) != len(matriz[0]):
        return print("La matriz no es cuadrada")
    
    if len(matriz) == 2:
        return matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0]
    
    determinante = 0

    for columna in range(len(matriz)):
        submatriz = [fila[:columna] + fila[columna + 1:] for fila in matriz[1:]]
        sign = (-1)**columna
        cofactor = sign * matriz[0][columna] * calcular_determinante(submatriz,m)
        determinante += cofactor 
    return determinante % m 

1. Definimos una función llamada «calcular_determinante» la cual recibe como argumento una matriz, que es una lista de listas y un entero \(m\) el cual es el módulo. Como el determinante es para matrices cuadradas, primero con un condicional if revisamos que el número de columnas de la matriz coincida con el número de filas, si no son iguales, el código nos imprime que la matriz no es cuadrada.

def calcular_determinante(matriz,m):
    if len(matriz) != len(matriz[0]):
        return print("La matriz no es cuadrada")

2. Si la matriz es cuadrada el código pasa al siguiente bloque, el cual es otro condicional if, en que se verifica si el tamaño de la matriz es de \(2\times 2\). Si la condición es cierta entonces el código no regresa el determinante calculado con la fórmula \(\Delta = ad - bc\) y ese es el valor que nos regresa la función.

    if len(matriz) == 2:
        return matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0]

3. Creamos la variable «determinante» con un valor inicial de \(0\), es donde se va a guardar el valor final de la cuenta.
   Si el código pasa a este bloque quiere decir que la matriz es de tamaño mas grande que \(2 \times 2\). La idea detrás del código es usar le método de cofactores para calcular el determinante. Es decir, que si se introduce una matriz de tamaño \(4\times 4\),

   \[\begin{split}A = \begin{pmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \\ \end{pmatrix}.\end{split}\]
   En el ejemplo, lo que hará el código es intentar calcular el valor
   \[(-1)^{i+j}\cdot a_{11} \cdot det(A_{11}).\]
   Primero se crea la variable «submatriz», con la comprensión de listas, con la instrucción fila[:columna] + fila[columna + 1:] logramos quitar el elemento con índice \(i\) de todas las filas de la matriz original, es decir que quitamos una columna, luego como el índice solo corre dentro de matriz[1:], estamos ignorando la primer fila con índice \(0\) de la matriz original. Siguiendo con la idea del ejemplo, esto nos generaría la matriz de tamaño \(3\times 3\),
   \[\begin{split}A_{11} = \begin{pmatrix} a_{22} & a_{23} & a_{24} \\ a_{32} & a_{33} & a_{34} \\ a_{42} & a_{43} & a_{44} \\ \end{pmatrix}.\end{split}\]
   Luego con la variable «sign» calculamos el signo que lleva el cofactor. Como el determinante se calcula con los valores de la primera fila, sabemos que el primer elemento de la matriz se le asigna el un signo positivo y a partir de este va intercala con un signo negativo, podríamos pensar que los índices impares son positivos y los índices impares son negativos, es por ello que solo con calcular (-1)**columna logramos calcular el signo.
   Y finalmente en la variable «cofactor» calculamos lo que queríamos \((-1)^{i+j}\cdot a_{ij} \det(A_{11})\), pero nuestro código no sabe calcular el determinante de matrices de \(3\times 3\) directamente, es por ello que volvemos a llamar a la función «calcular_determinate», esto hace que el código aplique la función nuevamente a la matriz de \(3\times 3\). Como no es una matriz de \(2\times 2\), el código salta a la segunda parte, es decir va a calcular por cofactores. Siguiendo el ejemplo el código en la primera iteración del ciclo for haría lo siguiente, calcularía la submatriz eliminando la columna \(1\) y fila \(1\) dejando una matriz de \(2\times 2\), calcularía el valor de la variable «sign» y después terminaría haciendo la cuenta de la variable «cofactor», en donde nuevamente aplicamos la función «calcular_determinante», pero como ahora la submatriz es de tamaño de \(2\times 2\), entonces la función ya aplica la primera parte del código y puede empezar a hacer los cálculo hacia atrás, es decir, en la primera iteración del ciclo for tendríamos el siguiente cálculo,
   \[\begin{split}(-1)^0 \cdot a_{22}\cdot \begin{vmatrix} a_{33} & a_{34} \\ a_{43} & a_{44} \\ \end{vmatrix} = a_{22} (a_{33}a_{44} - a_{43}a_{34}),\end{split}\]
   una vez obtenido este valor se guarda en la variable «determinante», en la segunda iteración tendríamos ,
   \[\begin{split}(-1)^1\cdot a_{23}\cdot \begin{vmatrix} a_{32} & a_{34} \\ a_{42} & a_{44} \\ \end{vmatrix} = -a_{23} (a_{32}a_{44} - a_{42}a_{34}),\end{split}\]
   una vez obtenido este valor se guarda en la variable «determinante», por último en la tercera iteración tendríamos,
   \[\begin{split}(-1)^2\cdot a_{24}\cdot \begin{vmatrix} a_{32} & a_{33} \\ a_{42} & a_{43} \\ \end{vmatrix} = a_{24} (a_{32}a_{43} - a_{42}a_{33}),\end{split}\]
   Y esto sería la primera iteración del primer ciclo for que se inició con la matriz original. El código seguirá iterando hasta terminar todas la cuentas necesarias. Finalmente el valor se simplifica aplicando el respectivo módulo.

    determinante = 0

    for columna in range(len(matriz)):
        submatriz = [fila[:columna] + fila[columna + 1:] for fila in matriz[1:]]
        sign = (-1)**columna
        cofactor = sign * matriz[0][columna] * calcular_determinante(submatriz,m)
        determinante += cofactor 
    return determinante % m 

Veamos el código para calcular la matriz adjunta.

def calcular_adjunta(matriz,m):
    n = len(matriz)
    adjunta = []

    for i in range(n):
        adjunta_fila = []
        for j in range(n):
            submatriz = [fila[:j] + fila[j+1:] for fila in (matriz[:i] + matriz[i+1:])]
            signo = (-1)**(i+j)
            cofactor = signo * calcular_determinante(submatriz,m)
            cofactor %= m
            adjunta_fila.append(cofactor)
        adjunta.append(adjunta_fila)
    
    adjunta = [list(fila) for fila in zip(*adjunta)]
    return adjunta

1. Definimos una función llamada «calcular_adjunta», creamos dos variables «n» que nos dice el tamaño de la matriz y «adjunta» que es una lista vacía. Notemos que no se verifica que la matriz sea cuadrada ya que como mas adelante usamos la función «calcular determinante», si no fuera cuadrada nos lo diría esa parte del código.

def calcular_adjunta(matriz,m):
    n = len(matriz)
    adjunta = []

2. Comenzamos un ciclo for con el cual se recorren las filas de la matriz, se crea la variable «adjunta_fila» la cual es una lista vacía, en donde vamos a guardar las filas de la matriz adjunta.
   Luego empezamos otro ciclo for dentro del primer ciclo, con este segundo ciclo recorremos las columnas de la matriz. Como vimos en el Ejemplo 148 tenemos que calcular la matriz de cofactores eliminando la fila \(i\) y la columna \(j\), eso es lo que logramos con la variable «submatriz», con la instrucción fila[:j] + fila[j+1:] eliminamos la columna \(j\) y con la instrucción matriz[:i] + matriz[i+1:] quitamos la fila \(i\).
   Con la variable «signo» calculamos el signos del cofactor.
   En la variable «cofactor» calculamos el valor de las entradas de la matriz adjunta multiplicando el signo por el determinante de la submatriz, en este paso aplicamos la función «calcular_determinante», la cual ya vimos como funciona, entonces una vez calculado el valor se simplifica módulo \(m\). Este valor se agrega a la lista «adjunta_fila». Una vez que tenemos todos los cofactores de la primer fila, esta lista se guarda en la variable, «adjunta» la cual va a ser la lista de listas que forme la matriz.

    for i in range(n):
        adjunta_fila = []
        for j in range(n):
            submatriz = [fila[:j] + fila[j+1:] for fila in (matriz[:i] + matriz[i+1:])]
            signo = (-1)**(i+j)
            cofactor = signo * calcular_determinante(submatriz,m)
            cofactor %= m
            adjunta_fila.append(cofactor)
        adjunta.append(adjunta_fila)

3. finalmente cambiamos el valor de la variable «adjunta» con una comprensión de listas, con la instrucción list(fila) tomamos cada fila de la matriz creada con la función zip(*adjunta) y nos regresa la matriz adjunta.

    adjunta = [list(fila) for fila in zip(*adjunta)]
    return adjunta

Por último veamos el código para resolver un sistema de congruencias lineales.

def resolver_sis_congr (A,b,m):
    determinante = calcular_determinante(A,m) 
    
    if algoritmo_euclides(determinante,m) == 1:
        det_inverso = inverso_modn(determinante,m) 
        adjunta_A = calcular_adjunta(A,m)
        inversa_A = [[(det_inverso * a_ij)%m for a_ij in fila] for fila in adjunta_A]
        resultado = matrices_producto(inversa_A,b,m)
        return resultado
    else:
        return print(f"El determinante {determinante} no tiene inverso módulo {m}")

1. Definimos una función llamada «resolver_sis_congr», la cual recibe como argumentos, una lista de listas la cual representa una matriz cuadrada, una lista con listas de \(1\) solo elemento la cual representa la columna de valores independientes del sistema de congruencias y por último un entero positivo el cual es el módulo que se va a trabajar.
   Creamos la variable «determinante» en donde aplicamos la función «calcular_determinante» para obtener el determinante de la matriz ingresada en los argumentos.

def resolver_sis_congr (A,b,m):
    determinante = calcular_determinante(A,m) 

2. Luego comenzamos un condicional if en el cual la condición es que el máximo común divisor del determinante y el módulo \(m\) debe ser igual a \(1\), si la condición es verdadera el código continua. Primero calcula la variable «det_inverso» en la cual usamos la función «inverso_modn» para encontrar el inverso multiplicativo del determinante. Luego calcula la variable «adjunta_A» en la cual usamos la función «calcular_adjunta» para obtener la matriz adjunta. Después calcula la variable «inversa_A» la cual se calcula con el Teorema 63 el cual nos dice que la matriz inversa se obtiene multiplicando el inverso multiplicativo del determinante por la matriz adjunta. Como estamos multiplicando un número entero por una matriz, necesitamos multiplicar todos los elementos de la matriz, eso lo logramos con una comprensión de listas. Finalmente calcula la variable «resultado» que se obtiene de multiplicar la variable «inversa_A» por la variable \(b\) que es el segundo argumento que dimos a la función original y aplicamos módulo \(m\).

    if algoritmo_euclides(determinante,m) == 1:
        det_inverso = inverso_modn(determinante,m) 
        adjunta_A = calcular_adjunta(A,m)
        inversa_A = [[(det_inverso * a_ij)%m for a_ij in fila] for fila in adjunta_A]
        resultado = matrices_producto(inversa_A,b,m)
        return resultado

4. En caso de que el máximo común divisor entre el determinante y el módulo no sea \(1\), el código pasa al condicional else que nos arroja un mensaje diciendo que no se puede calcular el inverso del determinante módulo \(m\).

    else:
        return print(f"El determinante {determinante} no tiene inverso módulo {m}")

Ejercicios de práctica

1. Demuestra el Teorema 55.

2. Determina si los siguientes sistemas de congruencias lineales tienen solución.

   • \(x\equiv 2\pmod{10}\) y \(x\equiv 7\pmod{15}\).

   • \(x\equiv 4\pmod{9}\), \(x\equiv 10\pmod{12}\) y \(x\equiv -2\pmod{18}\).

   • \(x\equiv 7\pmod{8}\), \(x\equiv 3\pmod{10}\) y \(x\equiv 2\pmod{15}\).

3. Resuelve los siguientes sistemas de congruencias.

   • \(x\equiv 10\pmod{12}\) y \(x\equiv 4\pmod{15}\).

   • \(x\equiv 1\pmod{10}\), \(x\equiv 5\pmod{12}\) y \(x\equiv -4\pmod{15}\).

   • \(x\equiv 2\pmod{6}\), \(x\equiv 5\pmod{7}\), \(x\equiv 6\pmod{8}\) y \(x\equiv 8\pmod{9}\).

4. Resuelve los siguientes sistemas usando el método de eliminación.

   • \(5x + 6y\equiv 10\pmod{13}\) y \(6x - 7y\equiv 2\pmod{13}\).

   • \(7x + 8y\equiv 11\pmod{15}\) y \(5x - 9y\equiv 10\pmod{15}\).

   • \(x - 2y -z\equiv 6\pmod{11}\), \(2x + 3y + z\equiv 5\pmod{11}\) y \(3x + y + 2z\equiv 2\pmod{11}\).

5. Resuelve los siguientes sistemas de ecuaciones utilizando la notación matricial.

   • \(x + 2y + 3z \equiv 1\pmod{7}\), \(x + 2y + 5z \equiv 1\pmod{7}\) y \(x + 4y + 6z \equiv 1\pmod{7}\).

   • \(x + y + z \equiv 1\pmod{7}\), \(x + y + w \equiv 1\pmod{7}\), \(x + z + w \equiv 1\pmod{7}\) y \(y + z + w \equiv 1\pmod{7}\).