Teorema de congruencia lineal

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 sólo si b es divisible por el máximo común divisor d de a y n (denotado mediante mcd(a,n)). Cuando éste es el caso, y x0 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\Bbb{Z}\}.

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

Contenido

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í sólo 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í sólo 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 modulo 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, p.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 linal, 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

Referencias

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

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Aritmética modular — Saltar a navegación, búsqueda Cubierta de la edición original de Disquisitiones arithmeticae de Gauss, libro fundamental de la aritmética modular. En matemática, la aritmética modular es un sistema aritmético para clases de equivalencia((Clase de …   Wikipedia Español

  • Triángulo — Para otros usos de este término, véase Triángulo (desambiguación). El triángulo es un polígono de tres lados. Un triángulo, en geometría, es un polígono determinado por tres rectas que se cortan dos a dos en tres puntos (que no se encuentran… …   Wikipedia Español

  • Anillo cíclico — Saltar a navegación, búsqueda Contenido 1 Definición 2 Cálculo elemental 3 Aplicaciones directas a la aritmética 4 …   Wikipedia Español

  • Algoritmo de Euclides — El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además… …   Wikipedia Español

  • Matriz semejante — En álgebra lineal, se dice que dos matrices A y B de n por n sobre el cuerpo K son semejantes si existe una matriz invertible P de n por n sobre K tal que: P −1AP = B. Uno de los significados del término transformación de semejanza es una… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”