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”,^[1] 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.

Se ${\displaystyle m_{k}}$ é um inteiro positivo e ${\displaystyle mdc(m_{i},m_{j})=1{\text{ }}(i\neq j)}$ (números primos entre si) então o sistema de congruências lineares:

${\displaystyle {\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: ${\displaystyle x\equiv X{\pmod {M}}}$ onde ${\displaystyle M=m_{1}\times m_{2}\times ...\times m_{n-1}\times m_{n}}$

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

${\displaystyle {\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 ${\displaystyle M_{a}}$ é o produto de todos os ${\displaystyle m_{k}}$ com exceção de ${\displaystyle m_{a}}$. Exemplo: ${\displaystyle M_{1}=m_{2}\times m_{3}...m_{n}}$ e ${\displaystyle M_{2}=m_{1}\times m_{3}...m_{n}}$.

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

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

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

${\displaystyle {\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 ${\displaystyle X}$ como:

${\displaystyle {\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 ${\displaystyle x_{i}}$:

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

${\displaystyle {\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 ${\displaystyle x_{i}}$ em mão, o valor de ${\displaystyle X}$ é:

${\displaystyle {\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:

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

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