Teorema chinês do resto

Na Teoria dos números, o Teorema Chinês do Resto define que um sistema de congruências lineares, de módulos coprimos entre si, admite uma solução simultânea referente ao produto dos módulos calculados no sistema.

O teorema é atribuído primeiramente ao matemático chinês Sun Tzu Suan Ching, tendo uma de suas primeiras aparições no “Manual de aritmética do mestre Sun”, um livro chinês que data de 287 d.C. a 473 d.C. Ele foi desenvolvido simultaneamente por gregos e chineses com o intuito de resolver alguns problemas relativos à astronomia.

Enunciado

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

x ≡ a₁ (mod.m₁)

x ≡ a₂ (mod.m₂)

...

x ≡ a_n-1 (mod.m_n-1)

x ≡ a_n (mod.m_n)

Tem uma única solução: x ≡ X (mod.m) m=m₁m₂m₃...m_n-1 m_n

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

X= a₁.M₁.x₁+ a₂.M₂.x₂+...+ a_n.M_n.x_n

M_a é o produto de todos os m_k com exceção de m_a (Exemplo: M₁=m₂.m₃.....m_n)

x_a é o número que torna M_a.x_a≡1(mod m_a)

Demonstração

De fato, ao dividirmos a_a.M_a.x_a por m_a o resto da divisão será a_a, uma vez que o produto M_a.x_a é côngruo 1 módulo m_a. Os outros termos serão côngruos a 0 módulo m_a porque contêm o mesmo em seu M_k.

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

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

x₁.13.29.41≡1(mod.5) → x₁.(-2)(-1)(1)≡x₁.2≡1(mod.5)

x₁≡3(mod.5)

x₂.5.29.41≡1(mod.13) → x₂.5.3.2≡1(mod.13)→ x₂.4≡1(mod.13)

x₂≡10(mod. 13)

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

x₃≡-10(mod.29)

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

x₄≡-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)

Ligações externas

• «O general e o Teorema Chinês dos Restos» 
• «Unicamp» (PDF) 
• «Universidade Federal de Lavras» (PDF) 
• «Universidade Federal de Pernambuco» (PDF)