View
4.656
Download
5
Category
Preview:
DESCRIPTION
Trabajo presentado en el Seminario como opción para la obtención del Título de Licenciado en Matemática.Ciudad Universitaria, Octavio Méndez Pereira Panamá, 2010
Citation preview
Trabajo presentado en el Seminario como opción para la obtención del Título de Licenciado en Matemática.
UNIVERSIDAD DE PANAMÁ
FACULTAD DE CIENCIAS NATURALES EXACTAS Y TECNOLOGÍAS
ESCUELA DE MATEMÁTICA
Teorema Chino de los Restos
Zugeily Tejeira.
CED: 5-706-2044
Ciudad Universitaria, Octavio Méndez Pereira
Panamá, 2010
DEDICATORIA
Esta monografía va dedicada en especial a los dos seres más
queridos, a Dios y mi querida abuela Inés B. de Cañizalez por
ser mi mayor inspiración.
A mis padres Manuel Tejeira e Indelida de Tejeira por su
apoyo incondicional, a mis hermanos Emanuel Tejeira e Iann
Tejeira por haber sido una gran motivación en mis estudios.
A mis amigos por sus consejos y apoyo, a mis compañeros
por su ayuda durante mis estudios y en especial a mi querido
amigo, hermano, compañero, Fezal Bhana que durante estos
años hemos compartido y vivido muchas experiencias juntos.
AGRADECIMIENTO
Agradezco al Señor Todo Poderoso por haberme permitido
cumplir esta pequeña meta.
A mis padres y hermanos por apoyarme, aconsejarme y
guiarme en mis decisiones.
A los profesores que durante la licenciatura me llenaron de conocimiento, en especial al profesor Dr. Jaime Gutiérrez por guiarme en la elaboración de esta monografía.
Contenido
Introducción
Contexto Histórico
Aportes de:
Sun Tzu Qin Jiushao Alexander Wylie
Contexto Teórico
Congruencia Clases de restos y sistemas completos de
restos Congruencias lineales Sistemas de congruencias lineales Teorema chino de los restos. Teorema chino de los restos generalizado
Teorema chino de los restos congruentes para enteros
Aplicación
Conclusión
Bibliografía
Introducción
Sabemos que cada congruencia lineal tiene solución, pero como encontraríamos solución a un sistema de congruencias lineales simultáneamente.
Este contexto se reunirá una serie de conceptos para el
desarrollo y entendimiento de la solución del mismo. En este
desarrollaremos el teorema chino de los restos. Se puede
destacar que su origen se remonta a la antigua china, fue
descubierto en el siglo 12 de nuestra era por el chino Sun
Tzu, fue el primero en trabajar con este teorema. A parte de
saber sobre este desarrollo también eran conocidas algunas
de sus aplicaciones. El teorema chino de los restos es uno de
los más usados en la teoría de números, se mostrara
diferentes ejemplos de la resolución del mismo.
Posee una enorme aplicación en diferentes áreas, para
mencionar como en la cronología y la criptografía. En la
cronología, solo conociendo el año juliano de un año
cualquiera, podemos calcular su año solar, dorado y de
indicción y en criptografía, en especial para reducir
operaciones con números enormes mediante el paso a
congruencias. En el algoritmo RSA, por ejemplo, los cálculos
se hacen módulo n, donde n es un producto de dos primos p y
q.
El Teorema Chino de los Restos tuvo una de sus primeras
apariciones en el siglo III.
Sun Tzu (722 aC - 481 aC)
El primero que trabajó con este teorema fue el matemático
chino Sun Tzu, vivió en el pgeríodo de primavera y otoño (722
aC - 481 aC) durante la Dinastía Zhou (1045 aC - 221 aC).
La forma original del teorema, está contenida en un libro
escrito por Sun Tzu llamado "aritmética manual del maestro
Sun", que es un libro chino que datan de 287 d.C. a 473 d.c.
Además fue desarrollado simultáneamente por griegos y
chinos, para resolver algunos problemas en relación con la
astronomía.
Además Sun Tzu fue escritor, pensador, político y militar
chino, autor del más antiguo y brillante tratado militar, "El
arte de la guerra". Dedicó gran parte de su vida a las
confrontaciones y debido a sus innumerables triunfos fue
considerado un experto estratega y militar. Uno de los
discípulos de Sun Tzu, Sun Wu, es el encargado de compilar
en trece tomos sus conocimientos y finalmente Sun Pin,
descendiente de Wu, es el que publica "El arte de la guerra".
Sun Tzu fue el primer estratega y teórico militar de China y ha
sido aclamado como el "sabio militar". Su libro "El arte de la
guerra" es el primer tratado castrense del mundo y su
influencia ha superado las fronteras militares llegando a la
política, la diplomacia, la cultura y la economía.
En su obra describe el armamento chino así como también sus
sistemas de mando, comunicación, disciplina, distinciones de
rango, estrategia y logística.
En "El arte de la guerra" considera que el poder es usado por
los políticos en interés de sus estados, sin acentuar el interés
por la moralidad o la ética en los actos. Lo importante para
esta posición política (que no ha cambiado demasiado con el
transcurso de los siglos) es lograr una mayor cuota de poder
en el orden internacional.
Qin Jiushao (1202 - 1261)
Nació en Ziyang, Sichuan, Su ascendencia era de Shandong,
es considerado como uno de los más grandes matemáticos
del siglo XIII. Además el se llevó a cabo en muchos otros
campos, sin embargo, y celebró una serie de cargos
burocráticos en varios provincias chinas.
Escribió el famoso tratado Shushu Jiuzhang (Tratado
matemático en nueve secciones) que apareció en 1247. El
tratado cubre temas que van desde el análisis indeterminado
a los asuntos militares y de estudio. En el
tratado, Qin incluyó una versión del teorema
chino del resto, el cual contiene un gran
trabajo sobre este, proporciona una ecuación
cuyos coeficientes son variables y, entre otros
resultados. Además en este tratado fue publicado por primera
vez el teorema, el cual es un enunciado sobre congruencias
simultáneas.
En geometría, descubrió "fórmula Qin Jiushao "en encontrar el
área de un triángulo con una longitud dada de tres lados. Este
es el mismo que la fórmula de Herón, descubierto antes.
Qin explica por primera vez como expertos chinos calculaban
datos astronómicos según el ritmo del solsticio de invierno.
Entre de sus logros está la introducción de una técnica para
solucionar ecuaciones( Un algoritmo numérico basado en el
método de Horner), hallar sumas de series aritméticas y
solucionar sistemas lineales. También introdujo el uso del
símbolo cero en las matemáticas chinas
Puesto que también hace comentarios prácticos sobre las
matemáticas, el libro de Qin proporciona una valiosa
información sobre las condiciones sociales y económicas en
China durante el siglo XIII. Qin desarrolló su talento en
muchas otras áreas además de las matemáticas, como en la
música, tiro con arco, esgrima, poesía y arquitectura.
Después de haber completado su trabajo en matemáticas,
entró en la política. Era jactancioso, corrupto, acusado de
soborno y de la intoxicación por sus enemigos, por lo que
varias veces fue relevado de sus funciones, y puesto en
"suspensión". Aun así, se las arregló para llegar a ser muy
rico. A diferencia de muchos matemáticos antiguos, que tenía
fama de sabio y no muy aburrido rápidamente con las
matemáticas, lo que puede ser la razón por él se centró tan
poco de su vida en su estudio.
Alexander Wylie
Nació en Londres, Inglaterra el 6 abril 1815 y falleció 10
febrero 1887, británica protestante cristiana
misionera a China. Él es conocido por su trabajo
de traducción y de becas durante la última
dinastía Qing. Su gran aporte fue en llevar a
Europa el Teorema Chino de los restos.
Fue a la escuela a Drumlithie, Kincardineshire , y al Chelsea .
While apprenticed to a cabinet-maker he picked up a
grammar written in Latin , and after mastering the latter
tongue made such good progress with the former, that in
1846 engaged him to superintend the 's press at . Mientras
que un aprendiz de ebanista cogió una gramática china
escrita en latín , y después de dominar la lengua esta última
hizo un buen progreso como con la primera, que en 1846
James Legge lo contrató para supervisar la Sociedad Misionera
de Londres 'en Shanghai . In this position he acquired a wide
knowledge of Chinese religion and civilization, and especially
of their , so that he was able to show that 's method (1819)
of solving equations of all orders had been known to the
Chinese mathematicians of the 14th century. En esta posición
él adquirió un amplio conocimiento de la religión y la
civilización china, y especialmente de su matemática , de
modo que fue capaz de demostrar que Sir George Horner s
método "(1819) para resolver ecuaciones de todas las
órdenes habían sido conocidos por los matemáticos chinos del
siglo 14.
En chino, tradujo libros sobre aritmética , cálculo ( Loomis ),
álgebra ( De Morgan s '), la mecánica , la astronomía (
Herschel s '), en colloboration con Li Shanlan, y la marina de
vapor del motor (TJ principal Brown y T), como así como las
traducciones del Evangelio según San Mateo y el Evangelio
según Marcos . In English his chief works were Memorials of
Protestant Missionaries (1867), Notes on Chinese Literature
(Shanghai, 1867), Jottings on the Science of Chinese
Mathematics and collection of articles published under the
title Chinese Researches by Alexander Wylie (Shanghai,
1897). En Inglés sus obras más importantes fueron los
monumentos de los misioneros protestantes (1867), Notas
sobre la Literatura China (Shangai, 1867), Apuntes sobre la
ciencia de las matemáticas chinas y la recopilación de
artículos publicados bajo el título chino Investigaciones por
Alexander Wylie (Shangai, 1897). He also published an article
on the in Xian . También publicó un artículo sobre la
nestoriana Tablet en Xian.
Mientras que en China, Alejandro Wylie amasó una gran
colección de libros antiguos chinos. En 1882, vendió su
colección de cerca de 20.000 títulos chinos a la Biblioteca de
Oxford . Su colección se encuentra ahora en la Biblioteca
Bodleian de Alejandro Wylie Colección.
Antes de mencionar el teorema presentaremos algunos
teoremas y definiciones, para poder desarrollar el Teorema
Chino De Los Restos.
1. Congruencia
1.1 Definición
Sean a, b y m enteros con m > 0, se dice que a es
congruente con b módulo m, y se denota simbólicamente
como a≡b (modm ) , si y solo si m divide la diferencia a – b. el
número m se llama módulo de la congruencia. Esto quiere
decir que la congruencia es equivalente a la relación de
divisibilidad m|(a – b). El símbolo de congruencia ≡ fue
elegido por Gauss para sugerir una analogía con el signo de
igualdad =.
En particular a≡0 (modm ) si y solo si, m|a. Por lo tanto
a≡b (modm ) .Si y sólo si a−b≡0(modm). Si m ∤ (a−b )escribimos
a≡b (modm ) , entonces a y b son incongruentes mod m.
Ejemplos
27≡3 (mod 4 ) , ya que 27 – 3 = 24 y este es divisible por
4.
47≡7(mod 8) ya que 47 – 7 =40 y este es divisible por 8.
1≡−1(mod 2), ya que 1- (-1)=2 y este es divisible por 2.
N es par sí, y sólo si, n≡0(mod 2).
Sa≡b(mod m) entonces a≡b(mod d) con d|m, d>0.
1.2 Propiedades
Enunciaremos algunos teoremas que prueban que las
congruencias poseen las propiedades formales de las
ecuaciones y sus respectivas demostraciones.
Teorema 1.2.1
La congruencia es una relación de equivalencia. Tenemos:
a) Reflexiva
a≡a (modm )
b) Simétrica
a≡b(mod m) Implica b≡a(mod m)
c) Transitiva
a≡b (modm ) yb≡c (mod m ) Implica a≡c (modm)
Demostración:
Aplicando las propiedades de la divisibilidad tenemos:
a) Como m|0 entonces queda demostrado.
b) Si m|(a – b) entonces m| (b – a).
c) Si m|(a – b) y m| (b – c) entonces m|(a – b) + (b – c) = m|
(a – c).
Teorema 1.2.2.
Si a≡b (modm ) y α≡ β (mod m ) .Es decir que dos congruencias
respecto del mismo módulo se pueden sumar, restar o
multiplicar, miembro a miembro, como si fuesen ecuaciones.
El mismo resultado es verdadero para un número finito de
congruencias respecto al mismo módulo.
a) ax+∝ y≡bx+ βy (mod m) para todo entero x e y.
b) a∝≡b β (modm ) .
c) an≡bn(mod m) para cada entero positivo n.
d) f ( a )≡f (b ) ( modm ) para cada polinomio f con coeficientes
enteros.
Demostración:
a) Como m|(a – b) y m|(∝−β ¿≡0, entonces m| x(a – b) + y(
∝−β ¿= ax+∝ y¿−(bx+βy ) .
b) Partiendo de la demostración anterior (a) tenemos que
a∝−bβ=∝ (a−b )+b (∝−β )≡0 (modm ) .
c) Sustituyendo ∝=a y β=b en (b) y hacemos inducción sobe
n.
d) Utilizar la parte (c) e inducción sobre el grado f.
Ejemplo
Regla de divisibilidad por 11. Un entero z > 0 es divisible por
11 si, y sólo si, la suma de los dígitos de su expresión decimal
es divisible por 11. Sea z cualquier entero expresado en el
sistema decimal en la forma
nnaaaaz 10........1010 2
210 , donde i =0,1,…n , 90 ia ,
y 0na
Esta propiedad se demuestra aplicando congruencias. Por el
teorema (1.2.2) tenemos:
110 ( mod 11 )
1102 ( mod 11 )
1103 ( mod 11 )
1104 ( mod 11 )
…
10n ≡±1 (mod 11) dependiendo si n es par o impar.
Por tanto
00 aa (mod 11)
11 10 aa ( mod 11 )
22
2 10 aa ( mod 11 )
…
an10n ≡±an (mod 11)
Entonces naaaaaaz ....43210 (mod 11)
Si la suma de los dígitos de un entero alternados en signos es
divisible por 11, entonces el número es divisible por 11.
Por ejemplo. El número 3162819 es divisible por 11 ya
que 3-1+6-2+8-1+9= 22 el cual es divisible por 11.
Teorema 1.2.3
Si c > 0 entonces a≡b(mod m) si y sólo si, ac ≡bc (modmc ) .
Demostración:
Tenemos m|(b – a) si y sólo si, cm| c(b – a).
Teorema 1.2.4
Ley de la simplificación. Si ac ≡bc (mod m) y d= (m,c ), entonces
a≡b(modmd
).
En otras palabras, un factor común c se puede simplificar si el
módulo se divide por d ≡(m,c ). En particular un factor común
que es primo con el módulo se puede simplificar siempre.
Demostración:
Dado que ac ≡bc (mod m) tenemos m|c(a – b) o sea md
∨ cd
(a−b ) .
Pero (m/d, c(d)) = 1 y por tanto m/d|(a – b).
Teorema 1.2.5
Supongamos que a≡b(mod m). Si d|m y d|a, entonces d|b.
Demostración:
Supongamos que d>0. Si d|m entonces a≡b(mod m) implica
a≡b(mod d). Pero, si d|a, entonces a≡0(mod d) por lo que b≡0 (modd ) .
Teorema 1.2.6
Si a≡b(mod m) entonces (a, m) = (b, m). Con otras palabras, los
números que son congruentes módulo m tienen el mismo mcd
con m.
Demostración:
Sea d=(a m) y e= (b, m). Entonces d|m y d|a, luego d|b por
tanto d|e. Análogamente, e|m, y e|b, luego e|a; por tanto
e|d por consiguiente d=e.
Teorema 1.2.7
Si a≡b(mod m) y si 0≤|a−b|<m, entonces a =b.
Demostración:
Como m|(a – b) tenemos m≤∨a−b∨¿ salvo si a –b = 0.
Teorema 1.2.8
Tenemos a≡b(mod m) si, sólo si, a y b tienen el mismo resto
cuando se dividen por m.
Demostración:
Escribimos a≡mq+s , b=mQ+R ,en donde 0≤r<m y 0≤ R<m . Entonces a
– b a−b≡r−R(modm) y 0≤|r−R|<m y aplicamos el teorema anterior
(1.2.7).
Teorema 1.2.9
Si a≡b(mod m) y a≡b(mod n) con (m n) =1, entonces a≡b (modmn ) .
Demostración:
Puesto que m y n dividen a (a – b) y (m, n) =1 también m· n
divide a (a – b).
2. Clases de restos y sistemas completos de
restos.
2.1 Definición
Consideremos un módulo fijo m > 0. Sea â el conjunto de
todos los enteros x tales que x≡a(modm) y llamaremos a â la
clase de restos de a módulo m.
Entonces â consta de todos los enteros de la forma a + mq,
q=0, ±1, ±2,… .
2.2 Propiedades
Las siguientes propiedades de las clases de restos son
consecuencia fácil de esta definición.
Teorema 2.2.1
Para un módulo m dado tenemos:
a) â=b si, y sólo si, a≡b (modm ) .
b) Dos enteros x e y pertenecen a la misma clase de
restos si, y sólo si x≡ y (modm ).
c) Las m clases de restos 1, 2,…, m son disjuntas y su
unión es el conjuntos de todos los enteros.
Definición:
Un conjunto de m representantes, uno de cada una de las
clases de restos 1,2,…, m se llama sistema completo de
restos módulo m.
Ejemplos Todo conjunto formado de m enteros,
incongruentes mod m, es un sistema completo de restos mod
m. Por ejemplo,
{1, 2,…, m}; {0, 1, 2,…, m-1}; {1, m +2, 2m + 3, 3m + 4,…,
m2}.
Teorema 2.2.2
Supongamos (k, m) =1. Si {a1,. . ., am} es un sistema
completo de restos módulo m, también lo es {ka1,…, kam}.
Demostración:
Si ka1 ≡ kaj (mod m) entonces a1 ≡ aj (mod m) ya que (k, m)
=1. Por consiguiente ningún par de elementos del conjunto
{ka1,…, kam} es congruente módulo m. puesto que en este
conjunto existen m elementos constituye un sistema completo
de restos.
3. Congruencias lineales
3.1 Definición
Sea f(x) polinomios con coeficientes enteros, por lo que los
valores de estos polinomios serán enteros cuando x sea
entero. Un entero x que satisfaga la congruencia polinómica
f ( x ) ≡0 (modm)
Se llama solución de la congruencia. Además, si x≡ y (modm)
entonces f (x)≡f ( y )(modm) o sea que cada congruencia que tenga
una solución tiene una infinidad. Por consiguiente, conviene
que las soluciones pertenecientes a la misma clase de restos
no deben contarse como distintas. Y cuando se habla del
número de soluciones de una congruencia, se refiere al
número de soluciones incongruentes, esto es, al número de
soluciones contenidas en el conjunto {1, 2,…, m} o en algún
otro sistema completo de restos módulo m. Por consiguiente
cada congruencia polinómica módulo m tiene a lo sumo m
soluciones.
Ejemplos
La congruencia lineal 2 x≡3 (mod 4) carece de solución,
puesto que 2x -3 es impar para cada x y, por
consiguiente, no puede ser divisible por 4.
La congruencia cuadrática x2≡1(mod 8) admite
exactamente cuatro soluciones dadas por x≡1 ,3 ,5 ,7(mod 8).
La teoría de las congruencias lineales quedará totalmente
descrita mediante los tres teoremas siguientes:
Teorema 3.1.1.
Si mcd(a, m)= 1. Entonces la congruencia lineal ax ≡b (modm)
tiene exactamente una solución.
Demostración:
Es preciso verificar únicamente los números 1, 2,…, m, ya que
constituyen un sistema residual completo. Por consiguiente se
forman los productos a, 2a,…, ma. Puesto que (a, m) =1 estos
números constituyen también un sistema residual completo.
Por tanto solo uno de estos productos es congruente con b
modulo m. esto es, existe un único x que satisface ax ≡b (modm).
Teorema 3.1.2
Si mcd (a, m) = d. Entonces la congruencia lineal ax ≡b (modm)
tiene solución si, sólo si, d/b.
Demostración:
Si existe una solución entonces d|b la congruencia ad
x≡bd(mod
md
)
tiene una solución puesto que (a/d, m/d)=1, y esta solución es
también una solución de ax ≡b (modm)
Teorema 3.1.3
Si (a, m)=d y d|b. Entonces la congruencia lineal
(1)ax≡b(mod m)
tiene exactamente d soluciones módulo m. vienen dadas por
(2) t ,t+md
,t+2md
,… ,t+(d−1 ) md
,
En donde t es la solución única módulo m/d, de la congruencia
lineal (3) ad
x≡bd (mod
md ) .
Demostración:
Cada solución de (3) es solución (1) y recíprocamente, cada
solución de (1) satisface (3). Luego los d números
t ,t+md
,t+2md
,… ,t+(d−1 ) md
, son soluciones de ad
x≡bd (mod
md ) y, por
tanto, de (1). Dos cualesquiera de ellos no son congruentes
módulo m puesto que las relaciones
t+rmd
≡ t+smd
(modm ) , con0≤r<d ,0≤s<d implican
rmd
≡smd
(modm ) , por lo tanto r ≡ s(modd) pero 0≤|r−s|<dluego r = s.
Como vemos falta demostrar que ax ≡b (modm)no tiene más
soluciones que las descritas en (2). Si es una solución de (1)
entonces ay ≡at(modm) luego y ≡t (modmd ) . Por lo tanto y= t + km/d
para un cierto k. pero k ≡r ( modd ) para un r que verifica 0≤r<d .
Por consiguiente kmd
≡rmd
(modm ) , luego y ≡t+rmd
(mod m ) .
por consiguiente y es congruente módulo m con uno de los
números descritos en t ,t+md
,t+2md
,… ,t+(d−1 ) md
,luego queda
demostrado.
Teorema 3.1.4.
Si (a, b) = d existen enteros x e y tales que ax + by =d.
Demostración:
La congruencia lineal ax ≡d (modb ) tiene una solución. Por lo
tanto existe un entero y tal que d – ax = by. Esto nos da ax +
by =d, luego queda demostrado.
Sistemas de congruencias lineales
Un sistema de congruencias lineales es un sistema de la forma
a1 x≡b1(mod n1)
a2 x≡b2(modn2)
…
ak x ≡bk (modnk)
Es decir, se trata de un sistema de k ecuaciones pero con una sola incógnita.
Con el uso de estos teoremas y definiciones desarrollaremos
la parte más importante de este trabajo, el teorema chino de
los restos.
4. Teorema chino de los restos.
Un sistema de dos o más congruencias lineales no tiene
necesariamente solución, aunque cada una de las
congruencias individuales si tenga solución. Por ejemplo no
existe ningún x que satisfaga simultáneamente x≡1 (mod 2 ) y
x≡0(mod 4), a pesar de que cada una de ellas, separadamente
tenga solución. En este ejemplo, los módulos 2 y 4 no son
primos entre sí. Ahora demostraremos que todo sistema de
dos o más congruencias lineales que, separadamente admite
solución única se puede resolver también simultáneamente, si
los módulos son dos a dos primos entre sí. Para resolver este
tipo de sistema de congruencias lineales hay un caso especial
como lo es teorema chino de los restos.
El matemático y poeta chino Sun Tsu planteó hace alrededor
de 1800 años el siguiente problema:
Tengo un conjunto de objetos. Cuando los cuento de tres en
tres, me sobran dos; cuando los cuento de cinco en cinco, me
sobran tres; cuando los cuento de siete en siete, me sobran
dos. ¿Cuántos objetos poseo?
Un resultado clásico de teoría de números proporciona
condiciones para que un problema del tipo anterior tenga
solución. Como homenaje a Sun Tsu, dicho resultado se
conoce como el teorema chino del resto. En su versión más
simple, el teorema se enuncia de la siguiente manera:
Teorema 4.1
Teorema chino de los restos. Supongamos que m1, m2,. . ., mr
son enteros positivos, primos entre sí, dos a dos: (m i, mk) =
1 si i≠ k. Y Sean b1, b2,. . ., br enteros arbitrarios. Entonces el
sistema de congruencias lineales
x≡b1(mod m1)
x≡b2(modm2)
.
.
.
x≡br (modmr)
Todas las soluciones x de este sistema son congruentes
módulo m, donde
m= m1. m2. … . mr.
Demostración:
Sean M= m1. m2. … mr y Mk = M/mk donde Mk es el producto
de todos los módulos excepto el k-ésimo módulo. Entonces
como todos los módulos son tomados dos a dos, primos entre
sí, esto quiere decir que mcd (Mk, mk) =1, y aplicando el
teorema que dice: “Si mcd(a, m) = d. Entonces la
congruencia lineal ax ≡b (modm) tiene solución si, sólo si, d/b”.
Sea
x = b1 · M1 · M’1 + b2 · M2 · M’2 +… + br · Mr · M’r.
Consideremos cada uno de los términos de esta suma módulo
mk. Dado que Mi ≡0(modmk ) si i≠ k tenemos x≡bk M k M ´ k≡bk (modmk ) .
Por tanto x satisface cada una de las congruencias del
sistema. Es fácil probar además que el sistema posee una
única solución módulo M. En efecto, si x e y son dos
soluciones del sistema tenemos x≡ y (modmk ) para cada k y,
puesto que los mk son, dos a dos primos entre sí, también
tenemos x≡ y (mod M ) . luego queda demostrada.
Ejemplo.
1. Encuentre los dos números positivos mínimos que tengan residuos 2, 3, 2 cuando se divide por 3,5,y 7 respectivamente. En congruencias seria:
Tenemos que m=3x5x7= 105. Tomando los primos relativos dos a dos M1= 35, M2= 21, M3= 15.
• Para encontrar N tendríamos que :
M 1 N1 ≡1mod(3)35 N1≡1mod(3)2 N1≡1mod (3)
N1= 2
M 2 N2 ≡1mod (5 )21 N2≡1mod (5)N2 ≡1mod(5)
N2 = 2
M 3 N 3≡1mod (7)15 N3≡1mod(7)N3 ≡1mod(7)
N3 = 1
La solución al sistema de congruencia seria:
X= b1M1N1 + b2 M2N2 + b3 M3N3
X= (2)(35)(2) + (3)(21)(1) + (2)(15)(1)X= 140 + 63 + 30
X= 233
Las dos mínima soluciones son 23 y 128, en general todas las soluciones de este sistema tienen la forma 23 + 105n
Lema
Consideremos la descomposición de n en factores primosn=pe1 1·…· pek k, donde p1 ,…, pkson primos diferentes. Para cualesquiera enteros a y b :a≡b (modn ) a≡b(mod peii)para cada i = 1,..., k
Ejemplo
Vamos a resolver la congruencia 91 x≡419 (mod 440 ) .
Al ser mcd(91, 440) = 1 tiene solución y, por ser 440 = 23 · 5 · 11, la congruencia es equivalente al sistema
91 x≡419 (mod 8 )
91 x≡419 (mod 5 )
91 x≡419 (mod 11 )
esto es
3 x≡3 (mod 8 )
x≡4 (mod 5 )
3 x≡1 (mod 11 )
o lo que es lo mismo:
x≡1 (mod 8 )
x≡4 (mod 5 )
x≡4 (mod 11)
Sistema, este último, en el que
a1=1 , a2=4 , a3=4 , n1=8 ,n2=5 , n3=11 , n=n1 · n2 · n3=440
c1=55 , c2=88 , c3=40
c1 d1≡1 (mod n1 )=55d1≡1 (mod 8 )=d1≡7 ( mod 8 ) ;d1=7
c2 d2≡1 (mod n2 )=88d2 ≡1 (mod 5 )=d2≡2 (mod 5 ); d2=2
c3 d3≡1 (modn3 )=40d3≡1 (mod 11)=d3≡8 (mod 11) ;d3=8
x0=a1c1 d1+a2 c2d2+a3c3 d3=1 ·55 ·7+4 ·88 ·2+4 ·40·=2369
por lo que la solución general viene dada por la de la congruencia
x≡2369 (mod 440 ) x ≡169(mod 440)
Teorema chino de los restos congruentes para
enteros
Sean x1,..., xr valores enteros, y p1,..., pr valores enteros
relativamente primos dos a dos, cuyo producto es n = p1 ×...
× pr. En estas condiciones, el sistema de ecuaciones
congruenciales dado por:
x ≡xi (mod pi ) para i = 1, ..., r
tiene una solución única x ϵ [0, n – 1], tal que:
x = ¿
con yi valores enteros que verifican las relaciones:
y i ≡ (n / pi )−1 (mod p i ) parai=1 ,…, r .
Para verlo, se consideran los valores enteros pi y ( n / pi ),
para i = 1, ..., r. Estos valores son relativamente primos dos a
dos, ya que p1, ..., pr a su vez lo son. Entonces, existen
valores enteros yi, tales que:
(n / pi) yi ≡ 1 ( mod pi) para i = 1, ..., r.
Además, puesto que p j divide a (n / pi) para todo 1≤ i ≠ j ≤ r,
se tiene que:
(n / pi) yi ≡ 0 (mod p j).
Con todo lo anterior, y teniendo en cuenta que pi divide a n,
para i = 1,..., r, el valor entero x dado por la ecuación anterior,
es solución del sistema de ecuaciones congruenciales
formulado al principio del teorema, puesto que se verifica:
x ≡ (n / pi) yi xi ≡ xi (mod pi) para i = 1, ..., r.
La solución x ϵ [0, n – 1] es única. Para verlo, se considera otra
solución x’ _ x, con x’ ϵ [0, n – 1], tal que verificase que x’ ≡
xi (mod pi) para i = 1... r. Entonces, puesto que los enteros
p1,..., pr son relativamente primos dos a dos, se verificaría que
x ≡ x’ (mod n) y, por tanto, que x = x’, lo cual supone una
contradicción de la hipótesis inicial.
Ejemplo:
2. Calcular la solución entera del sistema de ecuaciones
congruentes siguientes, mediante el teorema Chino de
restos congruentes.
x ≡ 67 (mod 92)
x ≡ 42 (mod 87)
x ≡ 24 (mod 77).
Cálculo del sistema de ecuaciones congruenciales mediante el
teorema Chino de restos congruentes.
x ≡ 67 (mod 92)
x ≡ 42 (mod 87)
x ≡ 24 (mod 77)
n = (77) (87)(92) = 616308
Se calculan los valores siguientes:
y i ≡ (n / pi )−1 (mod p i )
y1 ≡(616308 / 92)-1 ≡ 6699 ≡ 27 (mod 92)
y2 ≡ (616308 / 87)-1 ≡ 7084 ≡ 40 (mod 87)
y3 ≡(616308 / 77)-1 ≡8004 ≡ 19 (mod 77)
La solución x ≡¿ es
x ≡( 61630877
.19 .24 ) + (616308
87.40 .42) + (
61630877
.27 .67)
x ≡ 551883 (mod 616308).
Con este último teorema con su respectivo ejemplo, damos por concluida nuestro interesante contexto teórico del teorema chino de los restos.
Resolución del teorema usando ecuaciones diofantinas.
Una congruencia de la forma:
ax ≡ b (mod m)
Donde m es un entero positivo, a y b son números enteros y x es una variable entera, se llama congruencia lineal o ecuación de congruencia lineal (lineal por aparecer la variable x como potencia de grado uno, únicamente).
Resolver esta ecuación consiste (como en el caso de la aritmética entera) en encontrar todos los enteros x que
satisfagan la ecuación diofántica equivalente ax + my = b.
En el caso de Zm, la ecuación tendrá solución si y solo si mcd(a,m)|b , y en este caso tendrá exactamente d = mcd(a,m) soluciones distintas en Zm de la forma:
x= x0 + (m.t)/d
Donde t = 0, 1,2,..., d-1 y x0 es una solución particular de la ecuación diofántica ax + my = b.
Ejemplo:
Se tiene que resolver el sistema de congruencias
n=3(mod 17)
n=4 (mod 11)
n=5(mod 6)
Vamos primero a resolverlo sin usar directamente el algoritmo que se desprende de la demostración del teorema chino del residuo. Las dos primeras ecuaciones de congruencias pueden ser planteadas de la siguiente manera:
n=17 r+3=11 s+4. Utilizaremos el método de las ecuaciones diofantinas para resolver este sistema.
La ecuación diofantina 17 r+3=11s+4puede transformarse a
11 s=17−1.
Entonce s=r+(6 r−1)/11, y para que s resulte entero es claro que x=(6 r−1)/11 debe ser entero. Y si x va a ser entero, entonces r=11 x+1 /6=x+(5 x+1)/6 debe ser también entero. Pero, para ello, y=(5 x+1)/6 debe ser entero. Es decir, x=(6 y−1)/5= y+( y−1)/5. De aquí que z=( y−1)/5 tiene que ser entero. De nuevo, se sigue
que y=5 z+1 debe ser entero. Pero esto se cumple simplemente con tomar z entero.
Ahora nos regresamos hasta poner r o s en términos de z. Entonces, x=5 z+1+z=6 z+1. Y, de aquí, r=x+ y=6 z+1+5 z+1=11z+2. Por lo tanto, un n que satisface las dos primeras condiciones es n=17 (11 z+2 )+3=187 z+37. (Notemos que al dividir este n entre 17 deja 3 de residuo y si lo dividimos entre 11 deja 4.) Pero falta considerar la tercera condición.
Para ello resolvemos el sistema compuesto de esta ecuación recién lograda y la correspondiente a la tercera condición. Y el sistema se reduce a resolver la ecuación diofantina n=187 r+37=6 s+5, la cual podemos poner como 6 s=187 r+32.
Y de nuevo aplicamos el método diofantino: s=31r+5+(r+2)/6 y, como x=(r+2)/6 debe ser entero, r=6 x−2; y ya está, pues basta con tomar entero para que r sea entero.
Ahora, de regreso, ponemos en términos de x: n=187 r+37=187 (6 x−2 )+37=1122 x−374+37=1122 x−337. El lector puede verificar que esta ecuación cumple con las tres condiciones.
Así que si tomamos y la solución es 785.
Una aplicación del teorema chino del resto en la Cronología
Para muchas personas, el calendario ha sido siempre un gran misterio. Al mirar un almanaque colgado en la pared, con sus doce meses invariables, sentimos que algún desconocido ha hecho un plan anual para nosotros, en donde se debe viajar en el tiempo siguiendo una secuencia de meses, días de la semana, fechas religiosas, etc.Como matemático nos preguntamos ¿Porqué es tan complicado el almanaque? ¿De dónde salieron esos nombres
para los meses? ¿Por qué se tiene un calendario distinto para cada año? En este trabajo, como aplicación del tema, trataremos algunos aspectos relacionados con el calendario que, por supuesto, develarán algunos de los misterios planteados arriba. También haremos una incursión en el pasado para enterarnos de otros calendarios anteriores al nuestro, los cuales han pasado de moda pero son de interés para aquellos estudiosos de la historia y la astronomía.Curiosamente, un teorema de la teoría de números, será la clave mágica que permita conocer la relación entre los viejos sistemas de cronología.
El Calendario Gregoriano
El origen de nuestro calendario actual se encuentra en el Calendario Juliano, llamado así por Julio César, quien participó activamente en el diseño de éste.En dicho calendario cada año constaba de 365 días y cada cuatro años había un año bisiesto de 366 días. El calendario de 12 meses comenzaba en el mes de Marzo y finalizaba en Febrero. El nombre y duración de los meses eran los siguientes:
Durante el tiempo de César el mes quinto cambió de nombre por Julio, en honor a este Emperador. Más tarde, el mismo Julio César decidió que el año debería comenzar en Enero. De esta manera quedó organizado el Calendario sin sufrir ninguna modificación hasta la reforma del Papa Gregorio XIII en 1582.
Desde la época de los reyes de Roma, pasando por el Imperio, los años se numeraban de acuerdo al período de cada rey o emperador. Con un nuevo gobernante se iniciaba un nuevo ciclo y con él se comenzaba a contar desde el uno. Esto se modificó con el triunfo del Cristianismo, cuando se comenzó a numerarlos en forma diferente. A partir de entonces, el año 1 fue el nacimiento de Cristo y el día de Navidad el primer día de la era Cristiana, luego los años se cuentan en sucesión creciente, partiendo desde este inicio. Esta reforma fue hecha en el 533 d.c. durante el periodo del Emperador Dionisio Exigus.
ELEMENTO
NECESARIO Nombre en Latin
Marzo 30 Martius
Abril 30 Aprilis
Mayo 31 Maius
Junio 30 Junius
Quinto 31 Quintilis
Sexto 31 Sextilis
Septiembre
30 Septembris
OctubreNoviembre Diciembre Enero Febrero
31 Octobris 30 Novembris 31 Decembris 31 Januaris 28 Februarius
Una de las motivaciones que han tenido todos los pueblos en el momento de establecer un Calendario, es la de ubicar correctamente las fiestas religiosas. Así observamos que en el Calendario Cristiano, el Domingo de Pascua determina las otras fechas movibles como la Ascensión y el Corpus Cristi. Durante el Concilio de Nicea en el 325 d.c. se acordó fijar esta fecha, como el primer domingo después de luna nueva que aparezca en el Equinoccio de primavera (21 de Marzo) o después. Si la luna nueva aparece un Domingo, entonces elDomingo de Pascua sería el domingo siguiente.
Si bien el Calendario Juliano funcionó bien durante algunos siglos, la celebración de una Semana Santa a fines del siglo XVI, en donde el Domingo de Pascua correspondió al 11 de Marzo, hizo pensar a muchos que este Calendario estaba lejos de ser perfecto. Veamos el porqué de semejante error.
El año Astronómico, una revolución completa de la tierra alrededor del sol, es de 365 días, 6 horas, 9 minutos y 9.5 segundos. Sin embargo el año visible o Año Tropical, período entre dos equinoccios de primavera, es más corto: 365 días, 5 horas, 48 minutos y 46.43 segundos.El Calendario Juliano suponía que el año tenía 365 días y un cuarto, lo cual excede en 11 minutos y 14 segundos al Año Tropical. Como consecuencia de esto, se comete un error de un día cada 128 años. Esto explica el desfasaje entre la celebración de Domingo de Pascua y el Calendario Juliano.
A fin de corregir este error, el Papa Gregorio XIII introdujo una reforma en el calendario, mediante la cual se eliminaron 10 días de la historia. Se decidió que el día siguiente al 4 de Octubre de 1582, fuese el 15 de Octubre. Además se redujeron los años bisiestos mediante la siguiente convención. Los años bisiestos seculares (divisibles por 100) serán sólo
aquellos divisibles por 400. Así por ejemplo 1800 y 1900 no son bisiestos, pero 2000 será bisiesto.Esta reforma del Calendario Juliano se conoce con el nombre de CalendarioGregoriano y es el calendario que se ha venido usando hasta el presente.
El periodo juliano
Una de las medidas más usadas en la cronología histórica es la de los Días Julianos. Los Días Julianos tienen la misma duración que los días solares, sin embargo estos se cuentan a partir del primero de Enero del 4713 a.c., el cual es el día juliano 1, y de allí en adelante se numeran los días en sucesión creciente.Este sistema fue ideado por Joseph Justus Scaliger de Leyden, con la finalidad de tener un sistema único de medición del tiempo, compatible con las antiguas cronologías. El mismo apareció por primera vez en su obra " De emendatione temporum" (Paris 1583).
Estos dias julianos se agrupan en periodos de 7980 años. Cada uno de estos periodos se denomina Ciclo Juliano o Periodo Juliano. La razón para elegir semejante número, la veremos a continuación.Tenemos que 7980 = 28 x 19 x 15 y cada uno de estos factores tiene un significado muy especial dentro de los calendarios de distintas cronologías.
1. Ciclo Solar
El número 28 corresponde al llamado Ciclo Solar de 28 años. Este es el ciclo más pequeño en el cual los días de la semana y las fechas del calendario se repiten. El primer año de un ciclo solar es aquel en que el primero de Enero es Lunes. Por ejemplo el año 1560 tiene año solar 1. Ahora bien la pregunta que nos hacemos es la siguiente ¿Porqué se repiten los almanaques cada 28 años? Pues sencillamente un año normal de 365 días contiene 52 semanas más un día, luego cada 7 años (normales) se repiten las fechas del almanaque en los mismos días de la semana. Pero, cada cuatro años hay uno bisiesto, de 366 días lo cual hace que en realidad el ciclo sea de 4x7 = 28 días.
2. Ciclo Lunar
El ciclo lunar o ciclo metónico, es un periodo igual a 19 años solares. La razón de esto se debe al astrónomo griego Metón, siglo 5 d.c., quien descubrió que 19 años solares son iguales a 235 meses lunares.El mes lunar o mes sinódico, es el intervalo de tiempo entre dos conjunciones consecutivas del sol y la luna (4 fases lunares). Este tiene una duración de 29 días, 12 horas y 44 minutos.En la Iglesia Cristiana hubo necesidad de introducir el ciclo lunar dentro delCalendario, debido a la determinación del Domingo de Pascua, el cual depende de la luna llena, como ya hemos explicado. Los años del ciclo metónico se llaman años dorados.El primer año de un ciclo es aquel en que las fases lunares del mes de Enero de dicho año comienzan el 24 de Diciembre.Así por ejemplo en el año 1 de la era cristiana se inició un ciclo metónico. Luego el año 1 d.c. tiene número dorado 1, el año 2 d.c. tiene número dorado 2,…, etc. Luego el año 20
tiene número de oro 1, y así sucesivamente. La regla para calcular el número de oro t, de un año x cualquiera es:
t ≡ x+1mod 19
Por ejemplo 1994 tiene número de oro 19, pues
1994+1=1995≡19mod 19
Este sistema fue introducido por el Emperador Dionisio Exigus en el año 532d.c. y este año tiene número dorado 1.
3. Ciclo de Indicción
Finalmente, el número 15 corresponde a otro ciclo, el cual no tiene nada que ver con astronomía. Se trata de un ciclo fiscal del Imperio Romano que constaba de 15 años y se llama la indicción. Cada 15 años se hacía una valuación de las propiedades de los contribuyentes con el fin de determinar el impuesto a pagar. Este ciclo fue introducido por el Emperador Constantino en el año 313 d.c. correspondiendo a este año el primer año de dicho ciclo.
La idea de Scaliger era usar un sistema de cronología que incluyera todos estos ciclos. Esto permitiría calcular fácilmente una fecha determinada al pasar de un sistema a otro. El problema entonces era escoger una fecha apropiada para iniciar la cuenta de los años julianos. Se necesitaba un
año x de la historia, tal que en ese año se diera inicio a los tres ciclos. Esto es, x debe tener:
Año solar = 1 Año dorado = 1 Año de indicción = 1
Usando congruencias, se origina el sistema
{x≡1560mod 28x≡532mod 19x≡313 mod 15
Reduciendo esto se tiene
{x≡20 mod 28x≡0mod 19x≡13 mod 15
Veamos cómo se resuelve este problema.
Aplicando el Teorema Chino de Restos tenemos lo siguiente:Notemos que (28, 27) = 1, (28,15) = 1 y (15,19) = 1. Luego el sistema anterior posee solución, y por lo tanto es posible hallar una fecha de inicio del periodo juliano con las condiciones antes establecidas.A fin de determinar el valor de x, comenzaremos por usar la primera ecuación.
Luegox= 20 + 28k
Usando la segunda ecuación nos queda
20 + 28k ≡0mod 191 + 9k ≡ 0mod 19
9k ≡ 18mod 19
de dondek ≡ 2mod 19
Luegok = 2 + 19s
y por lo tanto volviendo a x en la última ecuación tenemos
76 + 532s ≡ 13mod 151 + 7s ≡ 13mod 15
luego, 7s ≡ 12mod 15, de donde s ≡ 6mod 15. Por lo tanto s = 6 + 15t.Nuevamente, si reemplazamos este valor en la expresión para x nos da
x = 76 + 532(6 + 15t) = 326 + 7980t
Luego la solución viene dada por
x ≡ 3268mod 7980
Sin embargo, descartamos el año 3268 por ser del futuro y buscamos el año y en que se inició el periodo juliano anterior. Esto es
y = 3268 - 7980 = - 4712
En el calendario gregoriano, el año - 4712 corresponde al 4713 a.c. (no hay año 0) y este se toma como el año 1 juliano.
Ejemplo. Conociendo el año juliano de un año cualquiera, podemos calcular su año solar, dorado y de indicción; basta tomar los restos de la división del número entre 28, 19 y 15 respectivamente. Por ejemplo para buscar el año juliano de 1993, el cual llamaremos x, hacemos
x = 4713 + 1993 = 6706
Luego dividimos a 6706 entre 28, 19 y 15 respectivamente para obtener los restos que nos dan toda la información. Por lo tanto
Año solar de 1993 = 14
Año dorado de 1993 = 18
Año de indicción de 1993 = 1
Buscar el año Juliano de 2010.Tenemos x= 4713 + 2010= 6723. Luego nos encontramos en él:
Año solar = 3Año dorado= 4
Año de indicción= 3
El teorema chino del resto en la Criptografía
El teorema chino del resto también tiene importantes aplicaciones en criptografía, en especial para reducir operaciones con números enormes mediante el paso a congruencias. En el algoritmo RSA, por ejemplo, los cálculos se hacen módulo n, donde n es un producto de dos primos p y q. Tamaños habituales para n son 1024, 2048 ó 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo Zn al anillo Zp ×Zq. La suma de las longitudes de bit de p y q es la longitud de bit de n, haciendo p y q considerablemente menor que n. Esto acelera mucho los cálculos. Se puede observar que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de " inyección de fallos".
Conclusiones
Llegamos a las siguientes conclusiones, luego de
haber realizado una nutrida investigación en el
Teorema Chino de los Restos.
Se afirma que los antiguos chinos utilizaban
este resultado para contar a los soldados en
su ejército
El Teorema Chino de los Restos es un resultado
clásico de teoría de números.
Observamos como las congruencias y sus
propiedades juegan un papel importante para
el desarrollo del Teorema Chino de los Restos.
Aprendimos de como este teorema juega un
papel importante para el desarrollo de un
sistema de congruencia.
Al igual que muchos resultados en
Matemática, el teorema chino de los restos
tiene una gran aplicación, algunas como en la
cronología y criptografía.
Bibliografía
Algoritmos Eficientes Para El Cálculo en la Estructura
Algebraica Zm, Autora: Sandra Molina Redondo, Madrid,
Junio De 2006.
Una aplicación del teorema chino del resto en la
Cronología, Boletín de la Asociación Matemática
Venezolana Vol. II, No. 1 (1995), Francisco Rivero.
T. M. Apostol, Introducción a la Teoría Analítica de
Números, Editorial Reverté, S.A., Barcelona – Bogotá –
buenos Aires – Caracas- México
http://enwikipedia.org/wiki/linear_congruence_theorem
http://
www.emis.de/journals/BAMV/conten/vol2/vol2n1p21-
28.pdf.
http://www.dma.fi.upm.es/java/matematicadiscreta/aritmeticamodular/congruencias2.html#1
Recommended