3.3: Congruencias lineales
- Page ID
- 114971
Debido a que las congruencias son análogas a las ecuaciones, es natural preguntar por soluciones de ecuaciones lineales. En esta sección, vamos a discutir congruencias lineales de una variable y sus soluciones. Comenzamos definiendo congruencias lineales.
Una congruencia de la forma\(ax\equiv b(mod\ m)\) donde\(x\) es un entero desconocido se llama congruencia lineal en una variable.
Es importante saber que si\(x_0\) es una solución para una congruencia lineal, entonces todos los enteros\(x_i\) tales que\(x_i\equiv x_0 (mod \ m)\) son soluciones de la congruencia lineal. Observe también que\(ax\equiv b (mod\ m)\) es equivalente a una ecuación Diofantina lineal es decir, existe\(y\) tal que\(ax-my=b\). Ahora probamos teoremas sobre las soluciones de congruencias lineales.
Dejar\(a,b\) y\(m\) ser enteros tales que\(m>0\) y dejar\(c=(a,m)\). Si\(c\) no divide\(b\), entonces la congruencia no\(ax\equiv b(mod \ m)\) tiene soluciones. Si\(c\mid b\), entonces\[ax\equiv b(mod \ m)\] tiene exactamente\(c\) incongruentes soluciones modulo\(m\).
Como mencionamos anteriormente,\(ax\equiv b(mod \ m)\) es equivalente a\(ax-my=b\). Por el Teorema 19 sobre ecuaciones diofantinas, sabemos que si\(c\) no divide\(b\), entonces la ecuación, no\(ax-my=b\) tiene soluciones. Observe también que si\(c\mid b\), entonces hay infinitamente muchas soluciones cuya variable\(x\) viene dada por\[x=x_0+(m/c)t\] Así los valores anteriores de\(x\) son soluciones de la congruencia\(ax\equiv b(mod \ m)\). Ahora tenemos que determinar el número de soluciones incongruentes que tenemos. Supongamos que dos soluciones son congruentes, es decir\[x_0+(m/c)t_1\equiv x_0+(m/c)t_2(mod \ m).\] Así obtenemos\[(m/c)t_1\equiv (m/c)t_2(mod \ m).\] Ahora notamos eso\((m,m/c)=m/c\) y\[t_1\equiv t_2(mod \ c).\] así obtenemos un conjunto de soluciones incongruentes dadas por\(x=x_0+(m/c)t\), donde\(t\) se toma modulo\(c\).
Observe que si\(c=(a,m)=1\), entonces hay una solución única módulo m para la ecuación\(ax\equiv b(mod \ m)\).
Encontremos todas las soluciones de la congruencia\(3x\equiv 12 (mod \ 6)\). Observe que\((3,6)=3\) y\(3\mid 12\). Así hay tres soluciones incongruentes módulo\(6\). Utilizamos el algoritmo euclidiano para encontrar la solución de la ecuación\(3x-6y=12\) como se describe en el capítulo 2. Como resultado, obtenemos\(x_0=6\). Así las tres soluciones incongruentes están dadas por\(x_1=6(mod \ 6)\),\(x_1=6+2=2(mod \ 6)\) y\(x_2=6+4=4(mod \ 6)\).
Como mencionamos anteriormente en la observación 2, la congruencia\(ax\equiv b(mod \ m)\) tiene una solución única si\((a,m)=1\). Esto nos permitirá hablar de inversos modulares.
Una solución para la congruencia\(ax\equiv 1 (mod\ m)\) para\((a,m)=1\) se llama el inverso modular de\(a\) módulo m. Denotamos tal solución por\(\bar{a}\).
El inverso modular de 7 módulo 48 es 7. Observe que una solución para\(7x\equiv 1(mod \ 48)\) es\(x\equiv 7 (mod \ 48)\).
Ejercicios
- Encuentra todas las soluciones de\(3x\equiv 6(mod \ 9)\).
- Encuentra todas las soluciones de\(3x\equiv 2(mod \ 7)\).
- Encuentra un módulo inverso 13 de 2 y de 11.
- Mostrar que si\(\bar{a}\) es la inversa de\(a\) módulo\(m\) y\(\bar{b}\) es la inversa de\(b\) módulo\(m\), entonces\(\bar{a}\bar{b}\) es la inversa de\(ab\) módulo\(m\).