Teorema Chino Del Residuo

1 Introducion

En este documento se expondr´a un breve resumen de la clase dictada por el

profesor Guillermo Mantilla.Clase en la cual se discutieron dos resultados El

teorema chino del Residuo y la interpolaci´on de Lagrange

2 Teorema chino del residuo

2.1 Historia

Llamado as´ı porque ya se empleaba en la civilizaci´on china en el siglo I a.c

en casos muy , concretos como era para clacular fechas de eventos astronomicos.Tambien

existen diferentes ”mitos” sobre su creaci´on: mitos de los cuales

no se hablara por su falta de veracidad.

2.2 Enunciado

sean m1, m2, .., mk primos relativos positivos que integran el sistema de congruencias

y sea r1, r2, ..rk el residuo quelos constituye.El sistema de congruencias

x ≡ r1 mod m1

x ≡ r2 mod m2

...

x ≡ rk mod mk

Tiene una unica solucion modm1m2...mk. en particular tiene una unica solucion

0 ≤ x < m1m2...mk

2.3 Demostracion

fijamos un i tal que 1 < i < k y sea

si = n/ni = n1n2..ni−1ni+1...nk

es facil ver que (n,si)=1.SeaRni=r1,...rz el sitema can´onico reducido residuos

m´odulo ni

.

→ siRni=sir1, ..., sirz

Es un sistema reducido de residuos m´odulo ni

.Ahora, como 1 ∈ Rni,entonces

debe ecistir un elemento b ∈ siRni tal que1 ≡ Resn1 mod b.Este elemento b ser´a

por supuesto de la forma sirt-En resumen , para cada i hemos encontrado un

entero Ci tal que sirt ≡ 1 mod ni

.

1

por ende para cada i tenemos siciai ≡ 1 mod ni

Ahora , sea s

=

X

k

i=1

siciai

para cada i , s ≡ ai mod ni

, como quer´ıamos demostrar.

2.4 Ejemplos

Resuelva el siguiente sistema de congruencias lineales

x ≡ 2 mod 3

x ≡ 3 mod 4

x ≡ 2 mod 7

Solucion: Dado que 3,4,7 son primos relativos entre s´ı , por el teorema chino

del residuo sabemos que el sistema posee una solucion entera :

(i)Comos ≡ 2 bmod3 exite a en los enteros tal ques = 3a + 2

(ii)Por (i)tenemos que 3a + 2 ≡ 3 mod 4.Manipulamos esta congruencia de tal

manera que se despeje a

3a + 2 ≡ 3 mod 4 → 3a + 2 − 2 ≡ 3 − 2 mod 4 (sumar -2)

3a/equiv1 mod 4

→ −a ≡ 1 mod 4

→ a + 4 ≡ 3 mod 4

→ a ≡ 3 mod 4

(iii)Por (ii) existe b entero talue a = 4b + 3,luego

x = 3(4b + 3) + 2 = 12b + 11

(iv) Entonces 12b + 11 ≡ 2 mod 7.Ahora ”despejamos a b ”:

12b + 11 ≡ 2 mod 7

→ 12b ≡ 5 mod 7

→ 5b ≡ 5 mod 5

→ b ≡ 1 mod 1

javascript:void(0);

(v) Por (iv) existe c entero tal que b = 7c1.Por ende , s = 12(7c+ 1) + 11=84c+

23.Como

...