Teorema de congruencia lineal 1

Teorema de congruencia linealEn aritmtica modular, la cuestin de cundo una congruencia lineal puede ser resuelta se describe mediante elteorema de congruencia lineal. Si a y b dos nmeros enteros cualesquiera y n es un nmero entero positivo,entonces la congruencia

(1) tiene una solucin para x si y slo si b es divisible por el mximo comn divisor d de a y n (denotado mediantemcd(a,n)). Cuando ste es el caso, y x0 es una solucin de (1) , entonces el conjunto de todas las soluciones est dadopor

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

EjemploPor ejemplo, se puede examinar la ecuacin ax 2 (mod 6) con diferentes valores de a para ver lo que produce:

Aqu d = mcd(3,6) = 3 pero puesto que 3 no divide a 2, entonces no hay solucin.

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

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

Resolucin de congruencias linealesEn la resolucin general de ecuaciones de la forma:

si el mximo comn divisor d = mcd(a, n) divide a b, entonces se puede encontrar una solucin x para la congruenciacomo sigue: el algoritmo extendido de Euclides produce enteros r y s tales que ra + sn = d. Entonces x = rb/d es unasolucin. Las otras soluciones son los nmeros congruentes con x modulo n/d.Por ejemplo, la congruencia

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 solucin es x = -2*20/4 = -10, y -10 = 4 mdulo 7. Todas las dems solucionesdebern ser tambin congruentes con 4 mdulo 7. Puesto que la ecuacin original usa mdulo 28, El conjunto desoluciones enteras en el rango de 0 a 27 es x = {4,11,18,25}.

Teorema de congruencia lineal 2

Sistemas de congruencias linealesMediante el repetido uso del teorema de la congruencia lineal, se puede tambin resolver sistemas de congruenciaslineales, como en el siguiente ejemplo: encontrar todos los nmeros x tales que

2x 2 (mod 6)3x 2 (mod 7)2x 4 (mod 8).

Resolviendo la primera congruencia utilizando el mtodo expuesto arriba, se obtiene que x 1 (mod 3), el cualpuede ser escrito tambin 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 solucin 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.

Referencias Santiago Zaragoza, Antonio Cipriano (2009). 2.4. Congruencias lineales (en castellano). Teora de nmeros (1

edicin). Madrid: Visin libros. pp.22-25. ISBN 978-84-9886-360-1. Weisstein, Eric W. Linear Congruence Equation [1] (en ingls). MathWorld. Wolfram Research.

Referencias[1] http:/ / mathworld. wolfram. com/ LinearCongruenceEquation. html

Fuentes y contribuyentes del artculo 3

Fuentes y contribuyentes del artculoTeorema de congruencia lineal Fuente: http://es.wikipedia.org/w/index.php?oldid=64542720 Contribuyentes: Pablohn6, Raulshc, 1 ediciones annimas

LicenciaCreative Commons Attribution-Share Alike 3.0//creativecommons.org/licenses/by-sa/3.0/

Teorema de congruencia linealEjemploResolucin de congruencias lineales Sistemas de congruencias lineales Referencias

Licencia