Congruencia
Sean \(a, b \in \mathbb{Z}\) y \(m \in \mathbb{Z}+\) decimos que \(a\) es congruente a \(b\) módulo \(m\)
\(a \equiv b \pmod{m} \iff m \mid (a - b)\). Equivalente a decir que \(a\) y \(b\) tienen el mismo resto al dividirlos por \(m\).
Propiedades básicas de la congruencia
Sean \(x, y, z \in \mathbb{Z} \; \land \; m \in \mathbb{Z}+\), entonces:
1) \(x \equiv 0 \pmod{m} \iff m \mid x\)
\[x \equiv 0 \pmod{m} \iff m \mid (x - 0) \iff m \mid x \]2) \(x \equiv y \pmod{m} \iff x - y \equiv 0 \pmod{m}\)
\[x \equiv y \pmod{m} \iff m \mid (x - y) \iff x - y \equiv 0 \pmod{m} \]D1) \(x \equiv x \pmod{m}\) (Reflexividad)
\[x - x = 0 = m \cdot 0 \implies m \mid (x - x) \]D2) \(x \equiv y \pmod{m} \implies y \equiv x \pmod{m}\) (Simetría)
\[x \equiv y \pmod{m} \implies m \mid (x - y) \implies m \mid -(x - y) \implies m \mid (y - x) \implies y \equiv x \pmod{m} \]D3) \(x \equiv y \pmod{m} \; \land \; y \equiv z \pmod{m} \implies x \equiv z \pmod{m}\) (Transitividad)
\[\begin{aligned} x \equiv y \pmod{m} \; \land \; y \equiv z \pmod{m} \implies m \mid (x - y) \; \land \; m \mid (y - z) \\ \implies m \mid (x - y + y - z) \implies m \mid (x - z) \implies x \equiv z \pmod{m} \end{aligned} \]Teorema - Operaciones con congruencias
\[x_1 \equiv x_2 \pmod{m} \; \land \; y_1 \equiv y_2 \pmod{m} \]La congruencia es una relación de equivalencia compatible con la suma y el producto.
Sean \(x_1, x_2, y_1, y_2 \in \mathbb{Z} \; \land \; m \in \mathbb{Z}+\), tal que:
1) \(x_1 + y_1 \equiv x_2 + y_2 \pmod{m}\)
2) \(x_1 \cdot y_1 \equiv x_2 \cdot y_2 \pmod{m}\)
3) Si \(x \equiv y \pmod{m} \; \land \; j \in \mathbb{N} \implies x^j \equiv y^j \pmod{m}\)
Ecuación lineal de congruencia
La ecuación lineal de congruencia es una ecuación de la forma \(ax \equiv b \pmod{m}\) donde debemos encontrar los \(x \in \mathbb{Z}\) que cumplan la congruencia.
Algunas ecuaciones lineales no tienen solución, otras tienen infinitas soluciones. Por ejemplo:
Teorema - mcd en congruencias
Sean \(a, b \in \mathbb{Z} \; \land \; m \in \mathbb{Z}+\), y denotamos \(d = \textnormal{mcd}(a, m)\),
entonces hay solución para la ecuación \(ax \equiv b \pmod{m} \iff d \mid b\).
En este caso dada una solución \(x_0\), todas las soluciones son de la forma \(x = x_0 + kn, \; k \in \mathbb{Z} \; \land \; n = \frac{m}{d}\)
Ejercicios resueltos - Ecuación lineal de congruencia
1.
Encontrar todos los \(x \in \mathbb{Z}\) que cumplan la congruencia:
\[2x \equiv 3 \pmod{2} \]No tiene solución, ya que \(2x\) siempre será par y \(3\) es impar.
2.
Encontrar todos los \(x \in \mathbb{Z}\) que cumplan la congruencia:
\[7^{12} \equiv x \pmod{11} \]Para resolver esta ecuación, veamos que:
\[\begin{align*} 7^2 &\equiv 5 \pmod{11} \\ 7^2 \cdot 7 &\equiv 5 \cdot 7 \pmod{11} \\ 7^3 &\equiv 2 \pmod{11} \\ \end{align*} \]Por lo que podemos usar propiedad de las potencias para:
\[\begin{align*} 7^{12} &= (7^3)^4 \\ 2^4 &\equiv 5 \pmod{11} \\ 7^{12} &\equiv 5 \pmod{11} \end{align*} \]Por lo que \(7^{12}\) es congruente a \(5\) módulo \(11\), y también congruente a los enteros de la forma \(11k + 5, \; k \in \mathbb{Z}\).
3.
Encontrar todos los \(x \in \mathbb{Z}\) que cumplan la congruencia:
\[3x \equiv 7 \pmod{11} \]Una forma de resolver este problema es encontrar soluciones con enteros no tan grandes:
\[\begin{aligned} &3 \cdot 0 \equiv 0 \pmod{11} \\ &3 \cdot 1 \equiv 3 \pmod{11} \\ &3 \cdot 2 \equiv 6 \pmod{11} \\ &3 \cdot 3 \equiv 9 \pmod{11} \\ &3 \cdot 4 \equiv 1 \pmod{11} \\ &3 \cdot 5 \equiv 4 \pmod{11} \\ &\color{green}{3 \cdot 6 \equiv 7 \pmod{11}} \\ &3 \cdot 7 \equiv 10 \pmod{11} \\ &3 \cdot 8 \equiv 2 \pmod{11} \\ &3 \cdot 9 \equiv 5 \pmod{11} \\ &3 \cdot 10 \equiv 8 \pmod{11} \\ &3 \cdot 11 \equiv 0 \pmod{11} \\ &... \end{aligned} \]La solución general es \(x = 6 + 11k, \; k \in \mathbb{Z}\). El patrón se repite cada \(11\).
Otra forma de resolver el problema, es mediante el \(\textnormal{mcd}(3, 11)\).
\[\begin{align*} 11 &= 3 \cdot 3 + 2 \\ 3 &= 2 \cdot 1 + 1 \; (*) \\ 2 &= 1 \cdot 2 + 0 \\ \textnormal{mcd}(3, 11) &= 1 \\ 1 &\mid 7 \end{align*} \]Con esto sabemos que hay solución para la ecuación. Expresando el mcd en términos de \(3\) y \(11\):
\[\begin{align*} 1 &= 11 \cdot (-1) + 3 \cdot 4 \\ 1 &\equiv 3 \cdot 4 \pmod{11} \\ 3 \cdot 4 &\equiv 1 \pmod{11} \\ 3 \cdot (4 \cdot 7) &\equiv 1 \cdot 7 \pmod{11} \\ 3 \cdot 28 &\equiv 7 \pmod{11} \; \land \; 28 \equiv 6 \pmod{11} \\ 3 \cdot 6 &\equiv 7 \pmod{11} \end{align*} \]En este caso, fue necesario reducir el \(28\) a \(6\) en módulo \(11\) para encontrar la solución \(x = 6\).
\[6 + k \cdot \frac{11}{1} = 6 + 11k, \; k \in \mathbb{Z} \]4.
Encontrar todos los \(x \in \mathbb{Z}\) que cumplan la congruencia tal que \(0 \leq x \leq 100\):
\[6x \equiv 3 \pmod{57} \]Para resolver este problema, primero encontramos el \(\textnormal{mcd}(6, 57)\) y comprobamos si divide a \(3\):
\[\begin{align*} 57 &= 6 \cdot 9 + 3 \\ 6 &= 3 \cdot 2 + 0 \\ \textnormal{mcd}(6, 57) &= 3 \\ 3 &\mid 3 \end{align*} \]Por lo que hay solución para la ecuación. Expresamos el mcd en términos de \(6\) y \(57\):
\[\begin{align*} 3 &= (-9) \cdot 6 + 57 \cdot 1 \\ 3 &\equiv (-9) \cdot 6 + 57 \cdot 1 \\ 3 &\equiv (-9) \cdot 6 \pmod{57} \\ 6 \cdot (-9) &\equiv 3 \pmod{57} \end{align*} \]Todas las soluciones son \((-9) + k \cdot \frac{57}{3} = -9 + 19k, \; k \in \mathbb{Z}\).
Sin embargo, necesitamos las soluciones que cumplan con \(0 \leq x \leq 100\):
Por lo que las soluciones son \(-9 + 19k, \; k \in \{1, 2, 3, 4, 5\}\) (fue necesario redondear a \(1\) y \(5\)).
5.
Hallar todos los \(x\) que satisfacen:
\[x^2 \equiv 1 \pmod{4} \]Si \(x\) es solución, entonces \(x + 4k\) también lo es:
\[\begin{align*} 4k &\equiv 0 \pmod{4} \\ x + 4k &\equiv x \pmod{4} \\ (x + 4k)^2 &\equiv x^2 \pmod{4} \\ x^2 &\equiv 1 \pmod{4} \end{align*} \]Por lo que debemos buscar las soluciones para \(x = 0, 1, 2, 3\):
\[\begin{align*} 0^2 &\equiv 0 \pmod{4} \\ 1^2 &\equiv 1 \pmod{4} \\ 2^2 &\equiv 0 \pmod{4} \\ 3^2 &\equiv 1 \pmod{4} \end{align*} \]Por lo que las soluciones son \(x = 1 \land x = 3\).
6.
Hallar la solución al sistema de congruencias:
\[\left\{ \begin{array}{ll} x \equiv 8 \pmod{13} \\ x \equiv 3 \pmod{11} \\ x \equiv 5 \pmod{8} \\ \end{array} \right. \]Primero debemos determinar si este sistema tiene solución. De acuerdo al Teorema chino del resto, si los módulos son coprimos entre sí, entonces el sistema tiene solución. En este caso si se cumple.
Viendo la primera ecuación, podemos determinar que:
\[x = 8 + 13k, \; k \in \mathbb{Z} \]Sustituyendo en la segunda ecuación:
\[\begin{align*} 8 + 13k &\equiv 3 \pmod{11} \\ 13k &\equiv -5 \pmod{11} \\ 11k + 2k &\equiv -5 \pmod{11} \\ 2k &\equiv -5 \pmod{11} \\ 2k + 11 &\equiv 6 \pmod{11} \\ 2k &\equiv 6 \pmod{11} \\ k &\equiv 3 \pmod{11} \end{align*} \]Por lo que \(k = 3 + 11t, \; t \in \mathbb{Z}\). Sustituyendo en el valor de \(x\):
\[x = 8 + 13(3 + 11t) = 8 + 39 + 143t = 47 + 143t \]Sustituyendo en la tercera ecuación:
\[\begin{align*} 47 + 143t &\equiv 5 \pmod{8} \\ 7 + 7t &\equiv 5 \pmod{8} \\ 7t &\equiv -2 \pmod{8} \\ 8t - t &\equiv -2 \pmod{8} \\ - t &\equiv -2 \pmod{8} \\ t &\equiv 2 \pmod{8} \\ \end{align*} \]Sabemos el valor de \(t\), por lo que podemos encontrar el valor de \(x\):
\[x = 47 + 143(2) = 47 + 286 = 333 \]Por lo que la solución al sistema de congruencias es \(x = 333\).
Teorema de Fermat
Si \(p\) es un número primo y \(a \in \mathbb{Z}\) entonces:
\(a^{p} \equiv a \pmod{p}\)
Si \(a, p\) coprimos entonces:
\(a^{p-1} \equiv 1 \pmod{p}\)
Teorema de Wilson
Si \(p\) es un número primo, entonces:
\((p - 1)! \equiv -1 \pmod{p}\)
Teorema chino del resto
\[\begin{align*} x &\equiv b_1 \pmod{m_1} \\ x &\equiv b_2 \pmod{m_2} \\ &... \\ x &\equiv b_k \pmod{m_k} \end{align*} \]Sean \(m_1, m_2, ..., m_k\) enteros positivos dos a dos coprimos, entonces el sistema de congruencias:
Tiene solución única módulo \(m_1 \cdot m_2 \cdot ... \cdot m_k\)