Teorema de congruencia lineal

En aritmética modular, la cuestión de cuándo una congruencia lineal puede ser resuelta se describe mediante el teorema de congruencia lineal. Si a y b dos números enteros cualesquiera y n es un número entero positivo, entonces la congruencia

(1)$ax\equiv b{\pmod {n}}$

tiene una solución para x si y solo si b es divisible por el máximo común divisor de a y n (denotado mediante mcd(a,n)). Cuando éste es el caso, y x₀ es una solución de (1) , entonces el conjunto de todas las soluciones está dado por

$\{x_{0}+k{\frac {n}{d}}\mid k\in \mathbb {Z} \}.$

En particular, existirán exactamente d = mcd(a,n) soluciones en el conjunto de residuos {0,1,2,...,n-1}.

Ejemplo

Por ejemplo, se puede examinar la ecuación ax ≡ 2 (mod 6) con diferentes valores de a para ver lo que produce:

$3x\equiv 2{\pmod {6}}\$

Aquí d = mcd(3,6) = 3 pero puesto que 3 no divide a 2, entonces no hay solución.

$5x\equiv 2{\pmod {6}}\$

Aquí d = mcd(5,6) = 1, el cual divide a cualquier b, y así solo hay exactamente una única solución en {0,1,2,3,4,5}: x=4.

$4x\equiv 2{\pmod {6}}\$

Aquí d = mcd(4,6) = 2, el cual divide a 2, y así solo hay exactamente dos soluciones en {0,1,2,3,4,5}: x=2 y x=5.

Resolución de congruencias lineales

En la resolución general de ecuaciones de la forma:

$ax\equiv b{\pmod {n}}$

si el máximo común divisor d = mcd(a, n) divide a b, entonces se puede encontrar una solución x para la congruencia como sigue: el algoritmo extendido de Euclides produce enteros r y s tales que ra + sn = d. Entonces x = rb/d es una solución. Las otras soluciones son los números congruentes con x módulo n/d.

Por ejemplo, la congruencia

$12x\equiv 20{\pmod {28}}\$

tiene 4 soluciones puesto que mcd(12, 28) = 4 divide a 20. El algoritmo extendido de Euclides da (-2)*12 + 1*28 = 4, i.e. r = -2 y s = 1. Por lo tanto, una solución es x = -2*20/4 = -10, y -10 = 4 módulo 7. Todas las demás soluciones deberán ser también congruentes con 4 módulo 7. Puesto que la ecuación original usa módulo 28, El conjunto de soluciones enteras en el rango de 0 a 27 es x = {4,11,18,25}.

Sistemas de congruencias lineales

Mediante el repetido uso del teorema de la congruencia lineal, se puede también resolver sistemas de congruencias lineales, como en el siguiente ejemplo: encontrar todos los números x tales que

2x ≡ 2 (mod 6)

3x ≡ 2 (mod 7)

2x ≡ 4 (mod 8).

Resolviendo la primera congruencia utilizando el método expuesto arriba, se obtiene que x ≡ 1 (mod 3), el cual puede ser escrito también como x = 3k + 1. Sustituyendo éste en la segunda congruencia y simplificando, se obtiene

9k ≡ −1 (mod 7).

Al resolver la congruencia resulta que k ≡ 3 (mod 7), o k = 7l + 3. Se sigue entonces que x = 3 (7l + 3) + 1 = 21l + 10. Sustituyendo esto en la tercera congruencia y simplificando de nuevo, se obtiene

42l ≡ −16 (mod 8)

que tiene como solución l ≡ 0 (mod 4), o l = 4m. Esto produce x = 21(4m) + 10 = 84m + 10, o

x ≡ 10 (mod 84)

que describe todas las soluciones del sistema.

Véase también

• Aritmética modular
• Teorema chino del resto

Referencias

• Santiago Zaragoza, Antonio Cipriano (2009). «2.4. Congruencias lineales». Teoría de números (1ª edición). Madrid: Visión libros. pp. 22-25. ISBN 978-84-9886-360-4. 
• Weisstein, Eric W. «Linear Congruence Equation». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q524257