[skip-to-content]

Sección 3.7 Ecuaciones Lineales de Congruencia

Definición 3.7.1.
Sean \(a,b \in \mathbb{Z}\text{;}\) no nulos y \(n\in \mathbb{N}\text{.}\) Se denomina Ecuación Lineal de Congruencia a la expresión
\begin{equation*} ax \equiv b \ (\text{mod } n)\text{.} \end{equation*}
El número entero \(x\)corresponde a la solución de la ecuación.

Las soluciones de una Ecuación Lineal de Congruencia deben ser números enteros. ¿Existe algún criterio para determinar cuando una Ecuación Lineal de Congruencia tiene soluciones enteras? La respuesta es afirmativa.

La ecuación tiene solución si y sólo si \(n|(ax-b)\text{.}\) Es decir, si existe un único entero \(y\)tal que \(ny=ax-b\text{.}\) Reordenando, se logra \(b=ax+nt\) con \(t=-y\text{.}\) Por Proposición 2.5.4, la ecuación diofántica \(ax+nt=b\) tiene solución si y sólo si \((a,n)|b.\)
La ecuación \(3x \equiv 6 \ (\text{mod } 9)\) sí posee solución, pues \((3,9)=3\) y \(3|6.\)
La ecuación \(5x \equiv 4 \ (\text{mod } 10)\) no posee solución, pues \((5,10)=5\) y \(5\not\mid 4.\)

Sin embargo (y nuevamente, al igual que en las Ecuaciones Diofánticas Lineales), una Ecuación Lineal de Congruencia puede poseer más de una solución. Por lo tanto, consideremos el siguiente resultado (Proposición 3.7.5).

Los siguientes resultados permitirán resolver de manera más expedita una Ecuación Lineal de Congruencia (Proposiciones 3.7.6 y 3.7.7).

Por definición, existe un único entero \(t\) tal que \(ndt=d(a-b)\text{.}\) Reordenando y factorizando, se logra \(d\left[nt-(a-b) \right]=0\text{.}\) Como \(d\neq 0\) y \(\mathbb{Z}\) no tiene divisores de cero, entonces \(nt-(a-b)=0\text{.}\) Así, \(nt=a-b\text{;}\) por lo que \(a \equiv b\) (mod \(n\)).
Por definición, \(n|d(a-b)\text{.}\) Como \((n,d)=1\) entonces \(n \not\mid d\text{.}\) Por lo tanto, \(n|(a-b)\text{.}\) Así, \(a \equiv b\) (mod \(n\)).
La ecuación \(32x \equiv 28 \ (\text{mod } 36)\) tiene cuatro soluciones, pues \((32,36)=4\) y \(4|28\text{.}\) Por Proposición 3.7.6, se sigue que \(32x \equiv 28 \ (\text{mod } 36)\) implica \(8x \equiv 7 \ (\text{mod } 9)\text{.}\) Entonces \(x\equiv 2 \ (\text{mod } 9)\text{.}\)

¿Cómo relacionar \(x\equiv 2 \ (\text{mod } 9)\) con la ecuación original

\begin{equation*} 32x \equiv 28 \ (\text{mod } 36). \end{equation*}

Por definición, \(x\equiv 2 \ (\text{mod } 9)\) puede reescribirse como \(x= 2 + 9t\) con \(t\) entero. Pero... ¡sólo basta trabajar con \(x\) en módulo 36 para encontrar las cuatro soluciones correspondientes! y fijar \(t=0,1,2,3\) (por Proposición 3.7.5). Así

\begin{align*} t=0 \Rightarrow \ \amp x\equiv 2 \ (\text{mod } 36)\\ t=1 \Rightarrow \ \amp x\equiv 11\ (\text{mod } 36)\\ t=2 \Rightarrow \ \amp x\equiv 20 \ (\text{mod } 36)\\ t=3 \Rightarrow \ \amp x\equiv 29 \ (\text{mod } 36) \end{align*}

¿Por qué los valores de \(t\) son \(0,1,2,3\) y no \(4,5,6,7\text{?}\) Si \(t=4\text{,}\) se consigue \(x\equiv 38 \ (\text{mod } 36)\text{.}\) Pero \(38\equiv 2\ (\text{mod } 36),\) por lo que \(x\equiv 2 \ (\text{mod } 36)\text{.}\) En efecto, las soluciones (obtenidas con distintos valores para \(t\)) siempre serán \(2,11,20\) y \(29\) al trabajar en módulo \(36\text{.}\)

De esta manera, las soluciones buscadas son

\begin{equation*} \left[ 2\right]_{36}, \left[11 \right]_{36}, \left[20 \right]_{36}, \left[ 29\right]_{36}. \end{equation*}
La ecuación \(42x \equiv 252 \ (\text{mod } 335)\) tiene solución única, pues \((42,335)=1\) y \(1|252\text{.}\) Por Proposición 3.5.8, se sigue que \(x \equiv 6 \ (\text{mod } 335)\text{.}\) Por lo tanto, la solución buscada es \(\left[ 6\right]_{335}\text{.}\)

Nuevamente Sage nos proporciona una herramienta que permite calcular las soluciones de una Ecuación Lineal de Congruencia.

¿Es posible relacionar la función \(\varphi\) de Euler con las Ecuaciones Lineales de Congruencia? La Proposición 3.7.10 tiene la respuesta.

Por Proposición 3.7.5, la ecuación tiene solución única. Por consiguiente, basta probar que \(x\equiv a^{\varphi(n)-1}\cdot b \ (\text{mod } n)\) es solución. Sin embargo, esto es inmediato; pues
\begin{equation*} a(a^{\varphi(n)-1}\cdot b)\equiv a^{\varphi(n)}\cdot b \equiv b\ (\text{mod } n), \end{equation*}
ya que \((a,n)=1\text{,}\) por lo que el Teorema de Euler - Fermat establece que \(a^{\varphi(n)} \equiv 1 \ (\text{mod } n).\)
La ecuación \(7x\equiv 8\) (mod \(15\)) tiene solución única, pues \((7,15)=1|8\text{.}\) Como \(\varphi(15)=8\text{,}\) por Proposición 3.7.10,
\begin{equation*} x\equiv 7^{7}\cdot 8 =104 \equiv 14\ (\text{mod } 15). \end{equation*}
Así, la única solución es \(\left[ 14\right]_{15}\text{.}\)

Sin embargo, que ocurre si queremos determinar las soluciones de la ecuación \(119x \equiv 35\) (mod \(1001\)).

Esto puede resultar una tarea complicada. Sin embargo, puede facilitarse si se trabaja con la descomposición en factores primos de \(1001\text{.}\) Esto es una motivación para introducir la sección siguiente: Teorema Chino del Resto.