Teorema chinês do resto

Predefinição:Mais notas

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.

Enunciado

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

${\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ . . . \\ x \equiv a_{n - 1} (\mod m_{n - 1}) \\ x \equiv a_{n} (\mod m_{n}) \end{matrix}$

Tem uma única solução: $x \equiv X (\mod 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{matrix} 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{matrix}$

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 (\mod 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} (\mod m_{k})$ .

Exemplo

${\begin{matrix} x \equiv 3 (\mod 5) \\ x \equiv 5 (\mod 13) \\ x \equiv 7 (\mod 29) \\ x \equiv 1 (\mod 41) \end{matrix}$

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

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

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

$\begin{matrix} x_{1} \times 13 \times 29 \times 41 & \equiv 1 (\mod 5) \\ x_{1} \times - 2 \times - 1 \times 1 & \equiv 1 (\mod 5) \\ x_{1} \times 2 & \equiv 1 (\mod 5) \\ x_{1} & \equiv 3 (\mod 5) \end{matrix}$

$\begin{matrix} x_{2} \times 5 \times 29 \times 41 & \equiv 1 (\mod 13) \\ x_{2} \times 5 \times 3 \times 2 & \equiv 1 (\mod 13) \\ x_{2} \times 4 & \equiv 1 (\mod 13) \\ x_{2} & \equiv 10 (\mod 13) \end{matrix}$

$\begin{matrix} x_{3} \times 5 \times 13 \times 41 & \equiv 1 (\mod 29) \\ x_{3} \times 5 \times 13 \times 17 & \equiv 1 (\mod 29) \\ x_{3} \times 3 & \equiv 1 (\mod 29) \\ x_{3} & \equiv - 10 (\mod 29) \end{matrix}$

$\begin{matrix} x_{4} \times 5 \times 13 \times 29 & \equiv 1 (\mod 41) \\ x_{4} \times 5 \times 13 \times - 12 & \equiv 1 (\mod 41) \\ x_{4} \times - 1 & \equiv 1 (\mod 41) \\ x_{4} & \equiv - 1 (\mod 41) \end{matrix}$

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

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

Finalmente:

$\begin{matrix} x & \equiv X \equiv 247928 (\mod 5 \times 13 \times 29 \times 41) \\ x & \equiv 16073 (\mod 77285) \end{matrix}$

Predefinição:Referencias

Ligações externas

Predefinição:Portal3 Predefinição:Controle de autoridade

↑ Predefinição:Citar web

[1] Predefinição:Citar web

[1]

Teorema chinês do resto

Índice

Enunciado

Demonstração

Exemplo

Ligações externas

Menu de navegação

Teorema chinês do resto

Enunciado

Demonstração

Exemplo

Ligações externas

Menu de navegação

Pesquisa