Resolución de congruencias lineales

Introducción

En este capítulo vamos a presentar las congruencias lineales, es decir, congruencias que tienen una variable \(x\) y son de la forma \(ax \equiv b \pmod{m}\). Veremos que éstas tienen similitud con las ecuaciones diofantinas de dos variables. Al igual que las ecuaciones diofantinas, podemos saber si tienen o no soluciones. Vamos a presentar algunos algoritmos que sirven para resolver algunos casos particulares de congruencias lineales y haremos ejercicios sobre cada uno de estos.

Definición de congruencia lineal

En la Definición 39 hablamos sobre los inversos. Dijimos que \(b\) era inverso de \(a\) si sucedía que \(ab \equiv 1 \pmod {m}\).
En el Teorema 34 vimos que un entero \(a\) tiene inverso si se cumple que \(a\) y \(m\) eran primos relativos.

Con lo anterior podemos pensar en resolver otras ecuaciones en congruencias que tengan variables tales como \(8x \equiv 3 \pmod{5}\), \(x^2 \equiv 1 \pmod{8}\) o \(x^2 + 2 \equiv 3x \pmod{7}\). Las congruencias que vamos a trabajar en esta sección son las congruencias lineales y son del tipo \(ax \equiv b \pmod{m}\).

Definición 41 (Congruencia lineal)

Sean \(a,b\) y \(m\) un entero positivo y \(x\) una incognita. Una congruencia lineal es una expresión de la forma

\[ax \equiv b \pmod{m}.\]

El objetivo es encontrar el valor de \(x\) que cumpla la congruencia.

Veamos algunos ejemplos de congruencias lineales y busquemos solución para ellos.

Ejemplo 109

Intentemos encontrar el valor de \(x\) para que sea válida la siguiente congruencia \(3x \equiv 5 \pmod{6}\).

Procedamos a buscar el valor de \(x\) probando todas las posibilidades con las siguientes cuentas.

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

Podemos observar que a medida que vamos multiplicando valores encontramos un ciclo de residuos \(0\) y \(3\). Nunca encontraremos el valor para \(x\) que cumpla con la congruencia, por lo tanto la congruencia no tiene solución.

Ejemplo 110

Veamos si podemos encontrar el valor de \(x\) en la siguiente congruencia \(5x \equiv 1 \pmod{7}\).

Por el Teorema 34 sabemos que como \(5\) y \(7\) son primos relativos, entonces existe un único valor de \(x\) en \(0,1, \ldots ,7\), que cumple con la congruencia. Hagamos las siguientes cuentas:

\[\begin{align*} 5 \cdot 0 = 0 \equiv 0 \pmod{7}, \\ & \\ 5 \cdot 1 = 5 \equiv 5 \pmod{7}, \\ & \\ 5 \cdot 2 = 10 \equiv 3 \pmod{7}, \\ & \\ 5 \cdot 3 = 15 \equiv 1 \pmod{7}, \\ & \\ 5 \cdot 4 = 20 \equiv 6 \pmod{7}. \\ & \\ \end{align*}\]

No es necesario terminar las cuentas, pues ya encontramos que \(x = 3\), ya que

\[5\cdot 3 = 15 \equiv 1 \pmod{7}.\]

Pero, ¿qué pasa si nos fijamos en la clase \([3]_7 = \{3,10,17,24, \ldots\}\)?
Notemos que

\[5 \cdot 10 = 50 \equiv 1 \pmod{7},\]

entonces tendríamos que \(x = 10\) también sería una solución de la congruencia.
De hecho, cualquier \(x \in [3]_7\) sería una solución de la congruencia, y tendríamos una infinidad de soluciones.

Ejemplo 111

Ahora, si cambiemos un poco la expresión e intentemos resolver la congruencia \(5x \equiv 3 \pmod{7}\).

Por las cuentas anteriores tendríamos que

\[5 \cdot 2 = 10 \equiv 3 \pmod{7}.\]

Es decir que la solución de la congruencia sería \(x = 2\), pero también podríamos ver que cualquier elemento de \([2]_7 = \{2,9,16,23, \ldots \}\) es solución.
Por ejemplo, tendríamos que

\[5 \cdot 9 = 45 \equiv 3 \pmod{7}.\]

Entonces tendríamos que cualquier \(x \in [2]_7\) sería una solución de la congruencia.

Lo anterior no siempre es una forma sencilla de resolver ese tipo de problemas. Lo que nos interesa desarrollar en esta sección son métodos para poder resolver este tipo de congruencias de manera más eficiente, ver si la solución es única o hay una infinidad de soluciones.

Conexión con ecuaciones diofantinas lineales

Para ver la conexión entre las congruencias lineales y las ecuaciones diofantinas lineales, consideremos la congruencia

\[ax \equiv b \pmod{m}.\]

Por el Teorema 28 podemos expresar la congruencia anterior como \(ax = b + my\) para algún entero \(y\). Entonces tendríamos la ecuación lineal diofantina de dos variables

\[ax - my = b.\]

Como ya aprendimos a resolver ecuaciones diofantinas, entonces podemos encontrar una solución y resolver la congruencia.

Ejemplo 112

Encuentra la solución de la congruencia \(9x \equiv 5 \pmod{25}\).

Solución.

Procedamos a trasformar la congruencia en una ecuación lineal diofantina.
Como \(9x \equiv 5 \pmod{25}\), tenemos que \(9x = 5 + 25y\) para algún entero \(y\). Entonces nuestra ecuación lineal diofantina es

\[9x - 25y = 5.\]

Sabemos que \((9,25) = 1\) y \(1|5\), entonces gracias al Teorema 10 la ecuación tiene solución. Utilicemos la Observación 2 del algoritmo de Euclides para encontrar una solución particular de la ecuación diofantina.

\[\begin{align*} 25 = 9\cdot 2 + 7, \\ & \\ 9 = 7\cdot 1 + 2, \\ & \\ 7 = 2\cdot 3 + 1, \\ & \\ 2 = 1 \cdot 2 + 0. \end{align*}\]

Ahora, si escribimos la combinación lineal tendríamos lo siguiente.

\[\begin{align*} 1 &= 7 - 2\cdot 3 \\ & \\ &= 7 - (9 - 7\cdot 1) \cdot 3 \\ & \\ &= 7 - 9\cdot 3 + 7 \cdot 3 \\ & \\ &= 7 \cdot 4 - 9\cdot 3 \\ & \\ &= (25 - 9\cdot 2)\cdot 4 - 9\cdot 3 \\ & \\ &= 25\cdot 4 - 9 \cdot 8 - 9\cdot 3 \\ & \\ &= 25\cdot 4 - 9\cdot 11. \end{align*}\]

Por lo tanto, tenemos que \(9\cdot (-11) - 25\cdot (-4) = 1\). Ahora basta con multiplicar la ecuación por \(5\) y obtendríamos que

\[\begin{align*} & 9\cdot (-55) - 25\cdot (-20) = 5, \\ & \\ & 9\cdot (-55) = 5 + 25\cdot (-20). \\ \end{align*}\]

Lo anterior quiere decir que

\[9 \cdot (-55) \equiv 5 \pmod{25}.\]

Podemos obtener otra solución haciendo la siguiente congruencia, \(-55 \equiv 20 \pmod{25}\) ya que \(-55 = 25\cdot (-3) + 20\).

Entonces tendríamos que \(9 \cdot 20 \equiv 5 \pmod{25}\). Verificando, en efecto tenemos que \(9\cdot 20 = 180 = 25\cdot 7 + 5 = 175 + 5\).

Gracias al Teorema 10 tenemos que la solución general de la ecuación es \(x = x_0 + \left( \frac{b}{d} \right) t\) en donde \(t\) es un entero arbitrario.
Entonces la solución general de la ecuación lineal diofantina es

\[x = 20 + 25t.\]

Con \(t = -3\) obtenemos \(x = -55\) y con \(t = 0\) obtenemos \(x = 20\).

Veamos que si tomamos la solución general y la sustituimos en la congruencia obtenemos lo siguiente:

\[\begin{align*} 9(20 + 25t) &= 9\cdot 20 + 9\cdot 25t \\ & \\ &\equiv 5 + 0 \pmod{25} \\ & \\ &\equiv 5 \pmod{25}. \end{align*}\]

Por lo tanto, todos los valores de \(x \in [20]_{25}\) son soluciones y la congruencia tiene una infinidad de soluciones.

Ya vimos que podemos encontrar soluciones de las congruencias lineales de la forma \(ax \equiv b \pmod{m}\) convirtiendo el problema en una ecuación diofantina. Ahora, nos interesa es encontrar todas las soluciones que no sean congruentes entre ellas. Veamos el siguiente ejemplo que aclara la idea de lo que buscamos.

Ejemplo 113

Encuentra las soluciones incongruentes de la congruencia lineal \(2x \equiv 4 \pmod{6}\).

Solución.

Como estamos trabajando módulo \(6\) podemos desarrollar las siguientes cuentas,

\[\begin{align*} 2 \cdot 0 = 0 \equiv 0 \pmod{6}, \\ & \\ 2 \cdot 1 = 2 \equiv 2 \pmod{6}, \\ & \\ 2 \cdot 2 = 4 \equiv 4 \pmod{6}, \\ & \\ 2 \cdot 3 = 6 \equiv 0 \pmod{6}, \\ & \\ 2 \cdot 4 = 8 \equiv 2 \pmod{6}, \\ & \\ 2 \cdot 5 = 10 \equiv 4 \pmod{6}. \end{align*}\]

Por lo tanto tendríamos dos soluciones \(x = 2\) y \(x = 5\), las cuales cumplen que \(2 \not\equiv 5 \pmod{6}\).

Veamos un teorema general que nos da el número de soluciones incongruentes.

Teorema 43

Sean \(a,b\) y \(m\) enteros tales que \(m>0\) y \((a,m) = d\). Si \(d\nmid b\), entonces la congruencia \(ax \equiv b \pmod{m}\) no tiene solución. Si \(d|b\), entonces la congruencia \(ax \equiv b \pmod{m}\) tiene exactamente \(d\) soluciones que son incongruentes módulo \(m\).

Demostración. Gracias al Teorema 28 tenemos que la congruencia \(ax \equiv b \pmod{m}\) es equivalente a la ecuación lineal diofantina \(ax - my = b\).
El entero \(x\) es una solución de la congruencia \(ax \equiv b \pmod{m}\) si y sólo si existe un entero \(y\) tal que satisface la ecuación \(ax - my = b\). En otras palabras, la congruencia tiene solución si y sólo si la ecuación lineal diofantina tiene solución.

Por el Teorema 10 tenemos que si \(d \nmid b\), la ecuación lineal diofantina no tiene solución. Por lo tanto la congruencia tampoco tendría solución. Por otro lado si \(d|b\), la ecuación \(ax - my = b\) tiene un infinidad de soluciones las cuales están dadas por

\[x = x_0 + \left( \frac{m}{d} \right)t, \quad y = y_0 + \left( \frac{a}{d} \right)t,\]

en donde \(x_0\) y \(y_0\) es una solución particular de la ecuación.

Los valores de \(x\) dados por la expresión

\[x = x_0 + \left( \frac{m}{d} \right)t,\]

son las soluciones de la congruencia lineal y hay una infinidad de ellas que se obtienen variando el valor de \(t\in \mathbb{Z}\).

Para determinar cuántas soluciones incongruentes módulo \(m\) hay, nos fijaremos en las condiciones que hacen que dos soluciones sean congruentes.

Supongamos que tenemos dos soluciones \(x_1 = x_0 + \left( \frac{m}{d} \right)t_1\) y \(x_2 = x_0 + \left( \frac{m}{d} \right)t_2\) las cuales son congruentes módulo \(m\), es decir que

\[x_0 + \left( \frac{m}{d} \right)t_1 \equiv x_0 + \left( \frac{m}{d} \right)t_2 \pmod{m}.\]

Luego, por el inciso \(2\) del Teorema 30 podemos restar \(x_0\) en ambos lados

\[\left( \frac{m}{d} \right)t_1 \equiv \left( \frac{m}{d} \right)t_2 \pmod{m}.\]

Ahora, como \((m,\frac{m}{d}) = \frac{m}{d}\) y además como \(\frac{m}{d}|m \) tendríamos que \(m \div \frac{m}{d} = d\). Finalmente, por el Teorema 31 tenemos que

\[t_1 \equiv t_2 \pmod{d}.\]

Esto demuestra que un conjunto completo de soluciones incongruentes son obtenidas tomando \(x = x_0 + \left( \frac{m}{d} \right)t\), en donde \(t\) toma los valores del sistema completo de residuos módulo \(d\), es decir, los valores \(t = 0,1,2, \ldots , d-1\). \(\square\)

Ejemplo 114

Encuentra las soluciones incongruentes de la siguiente congruencia lineal \(21x \equiv -14 \pmod{49}\).

Solución.

Primero veamos si la congruencia tiene solución. Para ello vemos que \((21,49) = 7\). Además como \(7|(-14)\) la congruencia lineal es soluble y tiene \(7\) soluciones incongruentes módulo \(49\).

Como \(21x \equiv -14 \pmod{49}\) entonces tenemos que \(21x - 49y = -14\).

Ahora obtengamos una solución particular de la congruencia. Utilizando el algoritmo de Euclides tenemos que

\[\begin{align*} -49 &= 21\cdot (-3) + 14, \\ & \\ 21 &= 14 \cdot 1 + 7, \\ & \\ 14 &= 7\cdot 2 + 0. \end{align*}\]

Entonces, tenemos que

\[\begin{align*} 7 &= 21\cdot 1 - 14\cdot 1 \\ & \\ &= 21 \cdot 1 - (-49\cdot 1 - 21\cdot (-3))\cdot 1 \\ & \\ &= 21 \cdot 1 + 49\cdot 1 + 21\cdot (-3) \\ & \\ &= -21\cdot 2 + 49\cdot 1. \end{align*}\]

Por lo tanto, tenemos que

\[7 = -21\cdot 2 + 49\cdot 1.\]

Luego multiplicamos esta ecuación por \(-2\) y obtenemos que

\[-14 = 21 \cdot (4) - 49 \cdot (2).\]

Por lo tanto, tenemos que

\[x_0 = 4 \quad \text{ y } \quad y_0 = 2.\]

Entonces tendríamos que las soluciones de la congruencia son de la forma,

\[x = x_0 + \left( \frac{m}{d} \right)t = 4 + \left( \frac{49}{7} \right)t = 4 + 7t,\]

en donde \(0 \le t \le 6\).

Por lo tanto, las \(7\) soluciones incongruentes son

\[\begin{align*} \text{Si } t&=0, \quad \quad x = 4 + 7\cdot 0 = 4, \\ & \\ \text{Si } t&=1, \quad \quad x = 4 + 7\cdot 1 = 4 + 7 = 11, \\ & \\ \text{Si } t&=2, \quad \quad x = 4 + 7\cdot 2 = 4 + 14 = 18, \\ & \\ \text{Si } t&=3, \quad \quad x = 4 + 7\cdot 3 = 4 + 21 = 25, \\ & \\ \text{Si } t&=4, \quad \quad x = 4 + 7\cdot 4 = 4 + 28 = 32, \\ & \\ \text{Si } t&=5, \quad \quad x = 4 + 7\cdot 5 = 4 + 35 = 39, \\ & \\ \text{Si } t&=6, \quad \quad x = 4 + 7\cdot 6 = 4 + 42 = 46.\\ \end{align*}\]

Entonces tenemos el conjunto de soluciones incongruentes \(\{4, 11, 18, 25, 32, 39, 46 \}\).

Del Teorema 43 podemos obtener el siguiente corolario.

Corolario 10

La congruencia lineal \(ax \equiv b \pmod{m}\) tiene una única solución si y sólo si \((a,m) = 1\).

Solución a congruencias lineales

En esta sección vamos a presentar algunas técnicas o métodos para resolver congruencias lineales. También veremos ejemplos de cada una de estas técnicas.

Anteriormente vimos en la Definición 39 que un entero \(a\) es invertible módulo \(m\) si existe \(x\) tal que \(ax \equiv 1 \pmod{m}\). Además, vimos en el Teorema 34 que un número entero \(a\) tiene inverso módulo \(m\) si y sólo si \((a,m) = 1\), es decir, cuando \(a\) y \(m\) son primos relativos.
Los inversos son útiles en la búsqueda de resolver congruencias lineales. Veamos el siguiente teorema.

Teorema 44

La única solución de la congruencia lineal \(ax \equiv b \pmod{m}\), en donde \((a,m) = 1\), es el residuo mínimo de \(a^{-1}b \pmod{m}\)

Demostración. Por hipótesis tenemos la congruencia \(ax \equiv b \pmod{m}\) y que \((a,m) = 1\). Por el Teorema 34 sabemos que \(a\) tiene inverso módulo \(m\) es decir que existe \(a^{-1}\) tal que \(aa^{-1} = 1 \pmod {m}\). Entonces si multiplicamos la congruencia por \(a^{-1}\) obtendríamos lo siguiente:

\[\begin{align*} ax \equiv b \pmod{m}, \\ & \\ a^{-1}ax \equiv a^{-1}b \pmod{m}, \\ & \\ 1x \equiv a^{-1}b \pmod{m}. \end{align*}\]

Esto es que \(x \equiv a^{-1}b \pmod{m}\), y por lo tanto la solución a la congruencia lineal es \(a^{-1}b \pmod{m}\). \(\square\)

Ejemplo 115

Resuelve la congruencia lineal \(4x \equiv 11 \pmod{13}\), usando el Teorema 44 sobre inversos.

Solución.

Primero notemos que \((4,13) = 1\), es decir que \(4\) tiene inverso módulo \(13\). Entonces, tenemos que resolver \(4x \equiv 1 \pmod{13}\). Si usamos la Observación 2 del algoritmo de Euclides tendríamos que

\[\begin{align*} 13 &= 4\cdot 3 + 1, \\ & \\ 4 &= 1 \cdot 4. \end{align*}\]

Luego, por el Teorema 28 tenemos que \(4\cdot (-3) = 1 + 13\cdot 1\), es decir que \(4\cdot (-3) \equiv 1 \pmod{13}\). Así, obtenemos que el inverso de \(4\) módulo \(13\) es \(-3\). Entonces multiplicamos la congruencia lineal por \(-3\) y simplificamos para obtener el valor de \(x\), como sigue:

\[\begin{align*} 4x &\equiv 11 \pmod{13}, \\ & \\ (-3)\cdot 4x &\equiv (-3)\cdot 11\pmod{13}, \\ & \\ 1\cdot x &\equiv -33 \pmod{13}, \\ & \\ x &\equiv 6 \pmod{13}. \end{align*}\]

Por lo tanto, el valor de \(x = 6\) es solución, y además es única.

Veamos un caso particular para resolver congruencias del tipo \(ax\equiv b\pmod{p}\), en donde \(p\) es un número primo y \(a\) es un entero tal que \(p\nmid a\).

Teorema 45

Sea \(p\) un número primo y \(a\) un número entero tal que \(p\nmid a\). Entonces la solución de la congruencia lineal \(ax\equiv b\pmod{p}\) está dada por \(x\equiv a^{p-2}b\pmod{p}\).

Demostración. Por hipótesis tenemos que \(p\nmid a\), entonces \((a,p) = 1\) y por el Corolario 10 sabemos que la congruencia \(ax\equiv b\pmod{p}\) tiene una única solución. Además, por el Teorema 36 sabemos que \(a^{p-2}\) es el inverso de \(a\) módulo \(p\). Entonces si multiplicamos \(a^{p-2}\) en ambos lados de la congruencia, obtenemos que

\[\begin{align*} ax &\equiv b\pmod{p}, \\ & \\ a^{p-2}(ax)&\equiv a^{p-2}b\pmod{p}, \\ & \\ (a^{p-2}a)x&\equiv a^{p-2}b\pmod{p}. \end{align*}\]

Por lo tanto, tenemos que \(x\equiv a^{p-2}b\pmod{p}\). \(\square\)

Ejemplo 116

Resuelve la congruencia lineal \(24x\equiv 11\pmod{17}\).

Solución.

Primero veamos que \((24,17) = 1\). Entonces la congruencia sólo tiene una única solución. Podemos usar el Teorema 36 para encontrar la solución. Tenemos que

\[x\equiv 24^{15}\cdot 11\pmod{17}.\]

Ahora sólo bastaría con encontrar el residuo mínimo de \(24^{15}\cdot 11\) módulo \(17\). Primero, observemos que \(24\equiv 7\pmod{17}\). Entonces, tenemos que \(24^{15}\cdot 11\equiv 7^{15}\cdot 11\pmod{17}\).

Luego, veamos que

\[\begin{align*} 7^2 &= 49 \equiv -2\pmod{17}, \\ & \\ 7^4 &= 7^2\cdot 7^2 \equiv (-2)\cdot (-2) \equiv 4\pmod{17}, \\ & \\ 7^8 &= 7^4\cdot 7^4 \equiv 4\cdot 4\equiv 16 \equiv -1 \pmod{17}. \end{align*}\]

Aprovechando los cálculos anteriores, tenemos que

\[7^{15} = 7^8\cdot 7^4\cdot 7^2\cdot 7 \equiv (-1)\cdot 4\cdot (-2)\cdot 7 \equiv 56 \equiv 5\pmod{17}.\]

Por lo tanto, tenemos que

\[x\equiv 5\cdot 11 \equiv 4 \pmod{17}.\]

Veamos que el resultado anterior se puede generalizar utilizando el Teorema 39 de Euler.

Teorema 46

Sea \(m\) un número entero positivo y \(a\) cualquier número entero tal que \((a,m) = 1\). Entonces la solución de la congruencia lineal \(ax\equiv b\pmod{m}\) está dada por \(x \equiv a^{\varphi(m) - 1}b \pmod{m}\).

Demostración. Por hipótesis tenemos que \((a,m) = 1\) y por el Corolario 10 sabemos que la congruencia \(ax\equiv b\pmod{m}\) tiene una única solución. Además, por el Teorema 40 sabemos que \(a^{\varphi(m) - 1}\) es el inverso de \(a\) módulo \(m\). Entonces si multiplicamos \(a^{\varphi(m) - 1}\) en ambos lados de la congruencia, obtenemos que

\[\begin{align*} ax&\equiv b\pmod{m}, \\ & \\ a^{\varphi(m) - 1}(ax)&\equiv a^{\varphi(m) - 1}b\pmod{m}, \\ & \\ (a^{\varphi(m) - 1}a)x&\equiv a^{\varphi(m) - 1}b\pmod{m}. \end{align*}\]

Por lo tanto, tenemos que \(x\equiv a^{\varphi(m) - 1}b\pmod{m}\). \(\square\)

Ejemplo 117

Resuelve la siguiente congruencia \(17x\equiv 20\mod{24}\).

Solución.

Notemos que, como \((17,24) = 1\), entonces la congruencia tiene una solución única. Entonces podemos aplicar el Teorema 39 de Euler. Sabemos que \(\varphi(24) = 8\) y ademas qué \(17^2 = 289 \equiv 1\pmod{24}\). Entonces tendríamos lo siguiente

\[\begin{align*} x &\equiv 17^{\varphi(24) - 1} \cdot 20\pmod{24} \\ & \\ &\equiv 17^{8 - 1} \cdot 20\pmod{24} \\ & \\ &\equiv 17^7 \cdot 20\pmod{24} \\ & \\ &\equiv 17^2\cdot 17^2\cdot 17^2\cdot 17 \cdot 20\pmod{24} \\ & \\ &\equiv 1\cdot 1\cdot 1\cdot 17 \cdot 20\pmod{24} \\ & \\ &\equiv 340\pmod{24} \\ & \\ &\equiv 4\pmod{24}. \end{align*}\]

Por lo tanto \(x = 4\).

Lo siguiente es un algoritmo que podemos seguir cuando resolvemos ecuaciones del tipo \(ax \equiv b \pmod{m}\):

1. Cuando el valor de \(m\) es pequeño, podemos buscar la solución por fuerza bruta, es decir, multiplicando \(a\) por los valores del sistema de residuos módulo \(m\) hasta encontrar que \(ax\) sea congruente con \(b\) módulo \(m\).

2. Cuando \(m\) empieza a ser grande, lo anterior ya no es tan sencillo de realizar. Entonces presentaremos un algoritmo a seguir para resolver una congruencia lineal.
   Para ello vamos a necesitar unos resultados preliminares.

Lema 12

Sean \(a,b\) enteros. Sea \(m >0\) entero. Sea \(c\) un entero tal que \(c|a\), \(c|b\) y \(c|m\), además \(a' = \frac{a}{c}\), \(b' = \frac{b}{c}\) y \(m' = \frac{m}{c}\) entonces,

\[ax \equiv b\pmod{m} \quad \text{ si y solo si } \quad a'x \equiv b'\pmod{m'}.\]

Demostración. Probaremos la ida de la demostración, ya que el regreso es muy parecido, simplemente hay que multiplicar por \(m\) en lugar de dividir.

Como \(ax\equiv b\pmod{m}\), por definición tenemos que \(m|(ax-b)\), es decir que \(ax - b = qm\) para algún entero \(q\). Luego, esta ecuación la podemos dividir entre \(c\), y obtenemos lo siguiente

\[\begin{align*} ax - b &= qm, \\ & \\ \frac{a}{c}x - \frac{b}{c} &= q\frac{m}{c}, \\ & \\ a'x - b' &= qm'. \end{align*}\]

Es decir que \(m'|(a'x - b')\) y por lo tanto \(a'x\equiv b'\pmod{m'}\). \(\square\)

Lema 13

Sean \(a\) y \(m\) números enteros con \(m > 0\) tales que \((a,m) = 1\). Sea \(c\) un entero tal que \(c|a\) y \(c|b\) y además \(a' = \frac{a}{c}\) y \(b' = \frac{b}{c}\). Entonces,

\[ax\equiv b\pmod{m} \quad \text{ si y sólo si } \quad a'x\equiv b'\pmod{m}.\]

Demostración. Demostremos las dos implicaciones.

• \(ax\equiv b\pmod{m}\) entonces \(a'x\equiv b'\pmod{m}\).

Como \(ax\equiv b\pmod{m}\), por definición tenemos que \(m|(ax-b)\), es decir que \(ax - b = qm\) para algún entero \(q\). Podemos dividir esta ecuación entre \(c\) teniendo que

\[\begin{align*} ax - b &= qm, \\ & \\ \frac{a}{c}x - \frac{b}{c} &= \frac{qm}{c}, \\ & \\ a'x - b' &= \frac{qm}{c}. \end{align*}\]

Observemos lo siguiente. Sabemos que \(c|a\) y \((a,m) = 1\), es decir que \(a\) y \(m\) no tienen factores en común y por lo tanto tendríamos que \((c,m) = 1\) ya que \(c\) es un factor de \(a\). Entonces por el Corolario 2 tenemos que \(c|q\).
Entonces la expresión \(a'x - b' = \frac{q}{c}m\) nos dice que \(m|(a'x - b)\) y por lo tanto \(a'x\equiv b' \pmod{m}\).

• \(a'x\equiv b'\pmod{m}\) entonces \(ax\equiv b\pmod{m}\).

Ahora, como \(a'x\equiv b'\pmod{m}\), tenemos que \(a'x - b' = q'm\) para algún entero \(q'\). Entonces, vamos a multiplicar esta ecuación por \(c\) y sustituir \(a' = \frac{a}{c}, b' = \frac{b}{c}\)

\[\begin{align*} a'x - b' &= q'm, \\ & \\ ca'x - cb' &= cq'm, \\ & \\ c\cdot \frac{a}{c}x - c\cdot \frac{b}{c} &= cq'm, \\ & \\ ax - b &= cq'm. \end{align*}\]

Como \(cq'\) es un entero, tenemos que \(m|(ax - b)\), y por lo tanto \(ax\equiv b\pmod{m}\). \(\square\)

Veamos el algoritmo para resolver la congruencia lineal \(ax\equiv b\pmod{m}\).

Observación 15 (Algoritmo para resolver la congruencia lineal \(ax\equiv b\pmod{m}\))

El Teorema 43 nos provee de una solución general dada una solución particular \(x_0\), entonces nos concentraremos en un método para encontrar \(x_0\). En general, la estrategia es reducir el valor de \(a\) hasta que sea \(1\) ó \(-1\) ya que en ese caso la solución será \(x_0 = \pm b\).

• Paso \(1\).

Calculamos \((a,m) = d\) y verificamos si \(d|b\). Si \(d\nmid b\), entonces no hay soluciones y nos detenemos. Si \(d|b\), seguimos con el paso \(2\).

• Paso \(2\).

Ya que \(d\) divide a \(a,b\) y \(m\), por el Lema 12 podemos reemplazar los valores de la congruencia original con

\[a'x\equiv b'\pmod{m'},\]

donde \(a' = \frac{a}{d}\), \(b' = \frac{b}{d}\) y \(m' = \frac{m}{d}\).

Observemos que como \((a,m) = d\), por el inciso \(1\) de la Proposición 8 tenemos que \((\frac{a}{d} ,\frac{m}{d}) = (a',m') = 1\). Es decir, \(a'\) y \(m'\) son primos relativos.

• Paso \(3\).

En este punto, tenemos que verificar si se puede aplicar el Lema 13.
Ya se cumple que \((a',m') = 1\), entonces calculamos \((a',b') = e\). Si \(e > 1\), podemos reemplazar los valores de la congruencia original con

\[a''x\equiv b''\pmod{m'},\]

donde \(a'' = \frac{a'}{e}\) y \(b'' = \frac{b'}{e}\). Entonces si \(a'' = \pm 1\) tendremos que \(x_0 = \pm b''\) es la solución de la congruencia lineal. Si \(a'' \neq \pm 1\) o si \(e = 1\) saltamos al paso \(4\).

• Paso \(4\).

Observemos que

\[b'' = b'' \pm m' = b'' \pm 2m' = \ldots \pmod{m'}.\]

Debemos buscar qué valor de los anteriores nos conviene tomar para que se cumpla que \((a'',b''')>1\) donde \(b''' = b'' + km'\). Una vez elegido el valor, aplicamos nuevamente el paso \(3\) a la congruencia \(a''\equiv b'''\pmod{m'}\) y buscamos si el valor de \(a\) se reduce a \(1\) o \(-1\). Eventualmente aplicando el paso \(3\) y paso \(4\) se reducirá el valor de \(a\).

Una alternativa en este paso es multiplicar ambos lados de la congruencia por una constante \(s\) elegida adecuadamente, obteniendo que \(sa''x\equiv sb''\pmod{m'}\). Este valor \(s\) nos debería ayudar para que cuando hagamos \(a''' = sa''\) módulo \(m'\) obtengamos que \(|a'''| < |a''|\). Entonces, habremos reducido el valor de \(a''\) obteniendo la congruencia \(a'''x\equiv b'''\pmod{m'}\), en donde \(b''' = sb''\).

Ejemplo 118

Resuelve la siguiente congruencia con el algoritmo de la Observación 15.

\[18x\equiv 42\pmod{50}.\]

Solución.

• Paso \(1\).

Calculamos \((18,50) = 2\), además \(2|42\) entonces la congruencia sí tiene solución.

• Paso \(2\).

Por el Lema 12, dividimos los términos de la congruencia entre \(2\) y obtenemos que

\[9x\equiv 21\pmod{25}.\]

• Paso \(3\).

Ahora verificamos si se puede aplicar el Lema 13.
Como \((9,25) = 1\) y \((9,21) = 3\) sí podemos aplicar el lema. Entonces vamos a dividir entre \(3\) los términos \(a'\) y \(b'\), obteniendo que

\[3x\equiv 7\pmod{25}.\]

Como \((3,7) = 1\), necesitamos aplicar el siguiente paso.

• Paso \(4\).

El algoritmo nos sugiere que busquemos un valor \(b'''\) tal que \((3,b''') > 1\). En realidad, quisiéramos que ese \(b'''\) tuviera en su factorización un \(3\) para poder terminar el algoritmo. Entonces tenemos los siguientes valores

\[\begin{align*} \ldots \equiv 7 - 3\cdot 25\equiv 7 - 2\cdot 25\equiv 7 - 25\equiv &b''' = 7\equiv 7 + 25\equiv 7 + 2\cdot 25\equiv 7 + 3\cdot 25\equiv \ldots \pmod{25}, \\ & \\ \ldots \equiv 7 - 75\equiv 7 - 50\equiv 7 - 25\equiv &b''' = 7\equiv 7 + 25\equiv 7 + 50\equiv 7 + 75\equiv \ldots \pmod{25}, \\ & \\ \ldots \equiv -68\equiv -43\equiv -18 \equiv &b''' = 7 \equiv 32 \equiv 57\equiv 82\equiv \ldots \pmod{25}. \end{align*}\]

De lo anterior vemos que \(b''' = -18\). Entonces lo reemplazamos en la congruencia y tenemos que

\[3x\equiv -18\pmod{25}.\]

Ahora tenemos que \((3,25) = 1\) y \((3,-18) = 3\). Entonces aplicamos nuevamente el Lema 13 y dividimos entre \(3\) los términos obteniendo que

\[x\equiv -6 \pmod{25}.\]

Por lo tanto, tenemos que \(x_0 = -6 \equiv 44\pmod{50}\). La solución general es

\[x = x_0 + \left( \frac{m}{d} \right)t= -6 + \left( \frac{50}{2} \right)t = -6 + 25t,\]

donde \(t = 0,1\).

Entonces, las dos soluciones incongruentes son: \(x_0 = 44, 19\).

Ahora, vamos a ver un algoritmo que nos ayuda para resolver congruencias en donde el módulo es un número primo \(p\).

Observación 16 (Algoritmo para resolver la congruencia lineal \(ax\equiv b\pmod{p}\))

Sea \(p\) un número primo y \(a, b\) enteros positivos tales que \((a,p) = 1\). El siguiente algoritmo puede ser usado para resolver congruencias lineales del tipo \(ax\equiv b\pmod{p}\).

• Paso \(1\).

Vamos a crear la variable \(a_1\) que es el residuo al dividir el valor de \(p\) entre \(a\). Es decir que \(a_1\equiv p\pmod{a}\).

Luego, creamos la congruencia

\[a_1x\equiv -b\left[\frac{p}{a} \right] \pmod{p}.\]

En donde \(\left[ \frac{p}{a}\right]\) es la parte entera de dividir \(p\) entre \(a\).

Tenemos que simplificar la expresión \(-b\left[ \frac{p}{a} \right] = b_1\) módulo \(p\) para obtener una ecuación del mismo tipo que la original \(a_1x\equiv b_1\pmod{p}\), pero con un valor de \(a_1 < a\).

• Paso \(2\).

Vamos a repetir el paso \(1\), creamos la variable \(a_2\) la cual es el residuo de dividir \(p\) entre \(a_1\). Es decir que \(a_2\equiv p\pmod{a_1}\).

Luego creamos la congruencia

\[a_2x\equiv -b_1\left[ \frac{p}{a_1} \right] \pmod{p}.\]

Simplificamos la expresión \(-b_1\left[ \frac{p}{a_1} \right] = b_2\) módulo \(p\) para obtener una ecuación del mismo tipo que la original \(a_2x\equiv b_2\pmod{p}\), pero con un valor de \(a_2 < a_1\).

• Paso \(3\).

Continuamos repitiendo el algoritmo. Creamos la variable \(a_i\) la cual es el residuo de dividir \(p\) entre \(a_{i-1}\). Es decir que \(a_i\equiv p\pmod{a_{i-1}}\).

Luego creamos la congruencia

\[a_ix\equiv -b_{i-1} \left[ \frac{p}{a_{i-1}} \right] \pmod{p}.\]

Teniendo la secuencia \(a > a_1 > a_2 > \ldots > a_i\), en algún momento el algoritmo termina, ya que el valor de \(a_i = 1\) y \(B = -b_{i-1} \left[ \frac{p}{a_{i-1}} \right]\) módulo \(p\).

Así, finalmente obtendríamos la congruencia

\[x\equiv B \pmod{p}.\]

Y la solución de la congruencia \(ax\equiv b\pmod{p}\) sería \(x = B\).

Veamos un ejemplo para comprender mejor este algoritmo.

Ejemplo 119

Resuelve la congruencia \(6x\equiv 7\pmod{23}\).

• Iteración \(1\).

Calculamos la variable \(a_1\).

\[a_1 \equiv 23 \equiv 5 \pmod{6}.\]

Construimos la congruencia y simplificamos

\[\begin{align*} 5x &\equiv -7\cdot \left[ \frac{23}{6} \right] \pmod{23}, \\ & \\ 5x &\equiv -7\cdot 3\pmod{23}, \\ & \\ 5x &\equiv -21\pmod{23}, \\ & \\ 5x &\equiv 2\pmod{23}. \\ \end{align*}\]

• Iteración \(2\).

Calculamos la variable \(a_2\).

\[a_2 \equiv 23 \equiv 3 \pmod{5}.\]

Construimos la congruencia y simplificamos

\[\begin{align*} 3x &\equiv -2\cdot \left[ \frac{23}{5} \right] \pmod{23}, \\ & \\ 3x &\equiv -2\cdot 4\pmod{23}, \\ & \\ 3x &\equiv -8\pmod{23}, \\ & \\ 3x &\equiv 15\pmod{23}. \\ \end{align*}\]

• Iteración \(3\).

Calculamos la variable \(a_3\).

\[a_3 \equiv 23 \equiv 2 \pmod{3}.\]

Construimos la congruencia y simplificamos

\[\begin{align*} 2x &\equiv -15\cdot \left[ \frac{23}{3} \right] \pmod{23}, \\ & \\ 2x &\equiv -15\cdot 7\pmod{23}, \\ & \\ 2x &\equiv -105\pmod{23}, \\ & \\ 2x &\equiv 10\pmod{23}. \\ \end{align*}\]

• Iteración \(4\).

Calculamos la variable \(a_4\).

\[a_4 \equiv 23 \equiv 1 \pmod{2}.\]

Construimos la congruencia y simplificamos

\[\begin{align*} x &\equiv -10\cdot \left[ \frac{23}{2} \right] \pmod{23}, \\ & \\ x &\equiv -10\cdot 11\pmod{23}, \\ & \\ x &\equiv -110\pmod{23}, \\ & \\ x &\equiv 5\pmod{23}. \\ \end{align*}\]

Por lo tanto, tenemos que la solución es \(x\equiv 5\pmod{23}\).

Código para resolver congruencia lineal

El siguiente código nos ayudará a encontrar las soluciones de una congruencia lineal de la forma \(ax\equiv b\pmod{m}\).

Usaremos la función construida en la sección del algoritmo de Euclides, la cual nos ayuda a escribir el máximo común divisor como combinación lineal.

def euclides_extendido_ciclos(a,b):
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return s[-2],t[-2],a

El siguiente código resuelve congruencias lineales.

def congr_lin_sol (a,b,m):
    if a >= m or a < 0:
        a = a%m
    if b >= m or b < 0:
        b = b%m 
    s,t,d = euclides_extendido_ciclos(a,m)
    if b%d == 0:
        x_0 = (s * (b // d))%m
        if d == 1:
            print(f"La única solución incongruente de la congruencia  {a}x ≡ {b} (mod {m}) es x = {x_0%m} ")
        else: 
            print(f"La congruencia  {a}x ≡ {b} (mod {m}) tiene {d} soluciones incongruentes")
            print("Las soluciones son:")
            for i in range(0,d):
                print(f"x_{i} = {(x_0 + (m//d)*i)%m}")
    else:
        print(f"La congruencia {a}x ≡ {b} (mod {m}) no tiene solución ")

congr_lin_sol(6,7,23)

La única solución incongruente de la cogruencia  6x ≡ 7 (mod 23) es x = 5 

congr_lin_sol(9,5,25)

La única solución incongruente de la cogruencia  9x ≡ 5 (mod 25) es x = 20 

congr_lin_sol(2,4,6)

La cogruencia  2x ≡ 4 (mod 6) tiene 2 soluciones incongruentes
Las soluciones son:
x_0 = 2
x_1 = 5

congr_lin_sol(21,-14,49)

La cogruencia  21x ≡ 35 (mod 49) tiene 7 soluciones incongruentes
Las soluciones son:
x_0 = 39
x_1 = 46
x_2 = 4
x_3 = 11
x_4 = 18
x_5 = 25
x_6 = 32

congr_lin_sol(21,4,21)

La congruencia 0x ≡ 4 (mod 21) no tiene solución 

congr_lin_sol(3,5,6)

La congruencia 3x ≡ 5 (mod 6) no tiene solución 

Explicación del código.

En este capítulo hicimos un código para resolver congruencias lineales. Utilizamos la idea de la demostración del Teorema 43 para realizar el código, es decir, trasformar la congruencia en una ecuación lineal diofantina y encontrar una solución particular. Antes de resolver la congruencia, lo que hacemos es simplificar los coeficientes de esta.

Veamos cómo funciona el código.

def congr_lin_sol (a,b,m):
    if a >= m or a < 0:
        a = a%m
    if b >= m or b < 0:
        b = b%m 
    s,t,d = euclides_extendido_ciclos(a,m)
    if b%d == 0:
        x_0 = (s * (b // d))%m
        if d == 1:
            print(f"La única solución incongruente de la congruencia  {a}x ≡ {b} (mod {m}) es x = {x_0%m} ")
        else: 
            print(f"La congruencia  {a}x ≡ {b} (mod {m}) tiene {d} soluciones incongruentes")
            print("Las soluciones son:")
            for i in range(0,d):
                print(f"x_{i} = {(x_0 + (m//d)*i)%m}")
    else:
        print(f"La congruencia {a}x ≡ {b} (mod {m}) no tiene solución ")

1. Definimos una función llamada «congr_lin_sol» la cual recibe como argumento tres valores \(a, b\) y \(m\) que son los coeficientes de la congruencia lineal \(ax\equiv b\pmod{m}\).

def congr_lin_sol (a,b,m):

2. Ponemos un condicional if, el cual tiene como condición verificar si el valor de \(a\ge m\) o \(a < 0\), de ser cierta la condición actualizamos el valor de \(a\) simplificándolo módulo \(m\). Esto sirve porque si \(a\ge m\) o \(a<0\) reducimos el valor de \(a\) y trabajamos con números más pequeños y positivos.
   Hacemos lo mismo para el valor de \(b\).

    if a >= m or a < 0:
        a = a%m
    if b >= m or b < 0:
        b = b%m 

3. Utilizamos la función que creamos en el algoritmo de Euclides para obtener la combinación lineal del máximo común divisor de \(a\) y \(m\), es decir que obtenemos \((a,m) = d = sa + tm\), en donde el valor de \(x\) está en la variable «s».

    s,t,d = euclides_extendido_ciclos(a,m)

4. Luego, creamos un condicional if el cual verifica si \((a,m) = d\) divide a \(b\). De ser cierta la condición, se reproduce el código dentro del condicionalif.
   Como ya se calcularon los valores de la combinación lineal y sólo necesitamos el valor de la variable \(x\), lo que vamos a obtener es la solución particular \(x_0\). Como \(d|b\) y como ya tenemos que \(d = as + tm\), sólo falta multiplicar por \(\frac{b}{d}\) la ecuación para obtener \(b = a s\left(\frac{b}{d} \right) + m t\left(\frac{b}{d} \right)\). Y así obtenemos que \(x_0 = s\left(\frac{b}{d} \right)\). Lo que hacemos con ese valor es simplificarlo módulo \(m\).

    if b%d == 0:
        x_0 = (s * (b // d))%m

5. Después de obtener la solución particular, el código nos imprimirá las soluciones las cuales se dividen en dos casos con un condicional if. Si el valor de \(d=1\), la congruencia sólo tendrá una solución, entonces el código nos imprime esa única solución. Si el valor de \(d>1\), el código nos dice cuántas soluciones incongruentes tiene la congruencia y nos imprime el valor de todas las soluciones incongruentes.
   Dentro de un ciclo for recorremos el rango de \(0\) a \(d-1\) con la variable \(i\) y vamos sustituyendo los valores de \(i\) como \(t\) en la fórmula \(x = x_0 + \left( \frac{m}{d} \right)t\) para obtener todas las soluciones incongruentes. Las soluciones son simplificadas módulo \(m\) para que estén dentro del conjunto de residuos mínimos módulo \(m\).

        if d == 1:
            print(f"La única solución incongruente de la congruencia  {a}x ≡ {b} (mod {m}) es x = {x_0%m} ")
        else: 
            print(f"La congruencia  {a}x ≡ {b} (mod {m}) tiene {d} soluciones incongruentes")
            print("Las soluciones son:")
            for i in range(0,d):
                print(f"x_{i} = {(x_0 + (m//d)*i)%m}")

6. Finalmente, si \(d\) no divide a \(b\), el código nos arroja que la congruencia no tiene solución.

    else:
        print(f"La congruencia {a}x ≡ {b} (mod {m}) no tiene solución ")

Ejercicios de práctica

1. Resuelve las siguientes congruencias lineales con ayuda de las ecuaciones diofantinas. Di si son solubles y de tener solución encuentra todas las soluciones incongruentes

   • \(4x \equiv 9 \pmod{11}\).

   • \(12x \equiv 3 \pmod{45}\).

   • \(28x \equiv 35 \pmod{42}\).

2. Resuelve la siguientes congruencias lineales con ayuda de los inversos.

   • \(5x \equiv 3 \pmod{6}\).

   • \(19x \equiv 29 \pmod{16}\).

   • \(48x \equiv 39 \pmod{17}\).

3. ¿Para que enteros \(c\), en donde \(0\le c \le 30\) la congruencia \(12x\equiv c\pmod{30}\) tiene soluciones?
   Cuando tiene soluciones, ¿Cuántas soluciones incongruentes hay?

4. En el segundo algoritmo visto en donde \(p\) es un número primo y \(a, b\) son enteros tales que \((a,p) = 1\). Demuestra lo siguiente:

   • Muestra que si \(x\) es solución de la congruencia \(ax\equiv b\pmod{p}\), entonces \(x\) también es solución de la congruencia

     \[a_1x \equiv -b \left[ \frac{p}{a} \right] \pmod{p},\]
     en donde \(a_1\) es el residuo al dividir \(p\) entre \(a\).

   • Cuando hacemos las iteraciones obtenemos una secuencia de los coeficientes de \(x\), \(a > a_1 > a_3 > \ldots\). Demuestra que existe un entero positivo \(n\) con \(a_n = 1\), tal que en la n-ésima iteración obtenemos la congruencia lineal \(x\equiv B \pmod{p}\).

5. Resuelve las siguientes congruencias usando los algoritmos vistos en la Observación 15 y Observación 16.

   • \(14\equiv 11\pmod{5}\).

   • \(12\equiv 98\pmod{20}\).

   • \(23\equiv 8\pmod{17}\).

   • \(25\equiv 13\pmod{60}\).