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{\text{ }}(i\neq j)$ (números primos entre si) então o sistema de congruências lineares:

${\begin{cases}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\...\\x\equiv a_{n-1}{\pmod {m_{n-1}}}\\x\equiv a_{n}{\pmod {m_{n}}}\end{cases}}$

Tem uma única solução: $x\equiv X{\pmod {M}}$ onde $M=m_{1}\times m_{2}\times ...\times m_{n-1}\times m_{n}$

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

${\begin{aligned}X=\;&a_{1}\times M_{1}\times x_{1}\\+\;&a_{2}\times M_{2}\times x_{2}\\&...\\+\;&a_{n-1}\times M_{n-1}\times x_{n-1}\\+\;&a_{n}\times M_{n}\times x_{n}\end{aligned}}$

Onde $M_{a}$ é o produto de todos os $m_{k}$ com exceção de $m_{a}$. Exemplo: $M_{1}=m_{2}\times m_{3}...m_{n}$ e $M_{2}=m_{1}\times m_{3}...m_{n}$.

Adicionalmente, $x_{a}$ é o número que torna $M_{a}\times x_{a}\equiv 1{\pmod {m_{a}}}$.

Demonstração

De fato, ao dividirmos $a_{k}\times M_{k}\times x_{k}$ por $m_{k}$ o resto da divisão será $a_{k}$, uma vez que o produto $M_{k}\times x_{k}$ é côngruo 1 módulo $m_{k}$. Os outros termos serão côngruos a 0 módulo $m_{k}$ porque contêm o mesmo em seu $M_{k}$.

Desta forma, a soma será: $X=a_{k}+0+...+0=a_{k}\equiv a_{k}{\pmod {m_{k}}}$.

Exemplo

${\begin{cases}x\equiv 3{\pmod {5}}\\x\equiv 5{\pmod {13}}\\x\equiv 7{\pmod {29}}\\x\equiv 1{\pmod {41}}\end{cases}}$

Podemos escrever a solução $X$ como:

${\begin{aligned}X=\;&3\times 13\times 29\times 41\times x_{1}\\+\;&5\times 5\times 29\times 41\times x_{2}\\+\;&7\times 5\times 13\times 41\times x_{3}\\+\;&1\times 5\times 13\times 29\times x_{4}\end{aligned}}$

Subsequentemente, calculamos os valores de $x_{i}$:

${\begin{aligned}x_{1}\times 13\times 29\times 41&\equiv 1{\pmod {5}}\\x_{1}\times -2\times -1\times 1&\equiv 1{\pmod {5}}\\x_{1}\times 2&\equiv 1{\pmod {5}}\\x_{1}&\equiv 3{\pmod {5}}\end{aligned}}$

${\begin{aligned}x_{2}\times 5\times 29\times 41&\equiv 1{\pmod {13}}\\x_{2}\times 5\times 3\times 2&\equiv 1{\pmod {13}}\\x_{2}\times 4&\equiv 1{\pmod {13}}\\x_{2}&\equiv 10{\pmod {13}}\end{aligned}}$

${\begin{aligned}x_{3}\times 5\times 13\times 41&\equiv 1{\pmod {29}}\\x_{3}\times 5\times 13\times 17&\equiv 1{\pmod {29}}\\x_{3}\times 3&\equiv 1{\pmod {29}}\\x_{3}&\equiv -10{\pmod {29}}\end{aligned}}$

${\begin{aligned}x_{4}\times 5\times 13\times 29&\equiv 1{\pmod {41}}\\x_{4}\times 5\times 13\times -12&\equiv 1{\pmod {41}}\\x_{4}\times -1&\equiv 1{\pmod {41}}\\x_{4}&\equiv -1{\pmod {41}}\end{aligned}}$

Com os valores de $x_{i}$ em mão, o valor de $X$ é:

${\begin{aligned}X=\;&3\times 13\times 29\times 41\times 3\\+\;&5\times 5\times 29\times 41\times 10\\+\;&7\times 5\times 13\times 41\times (-10)\\+\;&1\times 5\times 13\times 29\times (-1)\\=\;&139113+297250-186550-1885\\=\;&247928\end{aligned}}$

Finalmente:

${\begin{aligned}x&\equiv X\equiv 247928{\pmod {5\times 13\times 29\times 41}}\\x&\equiv 16073{\pmod {77285}}\end{aligned}}$

Ligações externas

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