Calcular os três menores números que divididos por 11, 17 e 37 dão os restos respectivos 3, 10 e 13.

Seja x cada um dos números.

x ≡ 3 (mod 11)

x ≡ 10 (mod 17)

x ≡ 13 (mod 37)

Como m.d.c (11, 17, 37) podemos utilizar o Teorema do Resto Chinês.

Teremos uma solução tal que:

x ≡ x (mod m), onde m = 11*17*37 = 6919

x = 3 * 17 * 37 * x1 + 10*11* 37 *x2  + 13 * 11* 17 x3

Pelo Teorema os números x1, x2 e x3 (obtidos por tentativa e erro) são tais que:

x1 * 17 * 37   ≡ 1 (mod 11) ∴ x1≡  6

x2 * 11 * 37   ≡ 1 (mod 17) ∴ x2≡   16

x3 * 11 * 17   ≡ 1 (mod 37) ∴ x3≡  19



Logo,

x = 11322 + 65120 + 46189 = 122631

x ≡  122631 (mod 6919)

x ≡ 5008 (mod 6919)

Os números x são da forma 

x = 6919 * k + 5008, k ∈ N. Fazendo k = 1. 2. 3 para os três menores números, vamos obtê-los: 5008, 11927 e 18846.

QSL?

Teorema do Resto Chinês

Enunciado 

Se mk é um inteiro positivo e mdc(mi,mj) = 1 (i ≠ j)(números primos entre si) então o sistema de congruências lineares:

x ≡ a1 (mod.m1)

x ≡ a2 (mod.m2)

x ≡ a3 (mod.m3)

x ≡ a4 (mod.m4)

x ≡ a5 (mod.m5)

x ≡ a6 (mod.m6)

...

x ≡ an-1 (mod.mn-1)

x ≡ an (mod.mn)

Tem uma única solução: x ≡ X (mod.m) m=m1m2m3...mn-1 mn

O valor de X pode ser encontrado utilizando-se o Teorema do Resto Chinês:

X= a1.M1.x1+ a2.M2.x2+ a3.M3.x3+ a4.M4.x4+ ...+ an.Mn.xn

Ma é o produto de todos os mk com exceção de ma (Exemplo: M1=m2.m3.....mn)

xa é o número que torna Ma.xa≡1(mod ma)

Demonstração 

De fato, ao dividirmos aa.Ma.xa por ma o resto da divisão será aa, uma vez que o produto Ma.xa é côngruo 1 módulo ma. Os outros termos serão côngruos a 0 módulo ma porque contêm o mesmo em seu Mk.

Desta forma, a soma será X = aa + 0 + 0 + 0 + 0 + 0 + 0 + 0 = aa≡ aa (mod.ma).

Exemplo 

x ≡ 3 (mod.5)

x ≡ 5 (mod.13)

x ≡ 7 (mod.29)

x ≡ 1 (mod.41)

X = 3.13.29.41.x1 + 5.5.29.41.x2 + 7.5.13.41.x3 + 1.5.13.29.x4

x1.13.29.41≡1(mod.5) → x1.(-2)(-1)(1)≡x1.2≡1(mod.5)

x1≡3(mod.5)

x2.5.29.41≡1(mod.13) → x2.5.3.2≡1(mod.13)→ x2.4≡1(mod.13)

x2≡10(mod. 13)

x3.5.13.41≡1(mod.29) →x3.5.13.17≡1(mod.29)&rarr x3.3≡1(mod.29)

x3≡-10(mod.29)

x4.5.13.29≡1(mod.41) →x4.5.13.(-12) ≡1(mod.41)→x4.(-1) ≡1(mod.41)

x4≡-1(mod.41)

X=3.13.29.41.3 + 5.5.29.41.10 + 7.5.13.41.(-10) + 1.5.13.29.(-1)

X=139113 + 297250 – 186550 -1885

X=247928

x≡X≡247928(mod.5.13.29.41) → x≡16073(mod.77285)

http://pt.wikipedia.org/wiki/Teorema_chin%C3%AAs_do_resto