Teorema chinês do resto

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Teorema para resolver congruências simultâneas

A formulação original de Sun-tzu: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) com a solução x = 23 + 105k, com k um inteiro

Na matemática, o teorema chinês do resto afirma que, se alguém conhece os restos da divisão euclidiana de um inteiro n por vários inteiros, então pode-se determinar exclusivamente o resto da divisão de n pelo produto desses números inteiros, sob a condição de que os divisores sejam primos pares (não há dois divisores compartilhando um fator comum diferente de 1).

Por exemplo, se soubermos que o resto de n dividido por 3 é 2, o resto de n dividido por 5 é 3 e o resto de n dividido por 7 é 2, então sem saber o valor de n, podemos determinar que o resto de n dividido por 105 (o produto de 3, 5 e 7) é 23. Importante, isso nos diz que se n é um número natural menor que 105, então 23 é o único valor possível de n.

A declaração mais antiga conhecida do teorema é do matemático chinês Sun-tzu no Sun-tzu Suan-ching no século III EC.

O teorema chinês do resto é amplamente utilizado para computar com grandes inteiros, pois permite substituir uma computação para a qual se conhece um limite no tamanho do resultado por várias computações semelhantes em pequenos inteiros.

O teorema chinês do resto (expresso em termos de congruências) é verdadeiro em todos os domínios de ideais principais. Foi generalizado para qualquer anel, com uma formulação envolvendo ideais bilaterais.

História

A primeira declaração conhecida do teorema, como um problema com números específicos, aparece no livro do século III Sun-tzu Suan-ching do matemático chinês Sun-tzu:

Há certas coisas cujo número é desconhecido. Se os contarmos por três, temos dois parados; por cinco, temos três parados; e por sete, dois são deixados para cima. Quantas coisas existem?

O trabalho de Sun-tzu não contém nem uma prova nem um algoritmo completo. O que equivale a um algoritmo para resolver este problema foi descrito por Aryabhata (século VI). Casos especiais do teorema chinês do resto também eram conhecidos por Brahmagupta (século VII) e aparecem no Liber Abaci de Fibonacci (1202). O resultado foi posteriormente generalizado com uma solução completa chamada Da-yan-shu (大衍術) em Ch'in Chiu-shao's 1247 Tratado Matemático em Nove Seções ( 數書九章, Shu-shu Chiu-chang) que foi traduzido para o inglês no início do século XIX pelo missionário britânico Alexander Wylie.

O teorema restante chinês aparece no livro de Gauss 1801 Disquisições Arithmeticae.

A noção de congruência foi introduzida e usada pela primeira vez por Carl Friedrich Gauss em suas Disquisitiones Arithmeticae de 1801. Gauss ilustra o teorema chinês do resto em um problema envolvendo calendários, ou seja, "encontrar os anos que têm um certo número de período em relação ao ciclo solar e lunar e à indicação romana." Gauss introduz um procedimento para resolver o problema que já havia sido usado por Leonhard Euler, mas na verdade era um método antigo que apareceu várias vezes.

Declaração

Seja n₁,..., n_k inteiros maiores que 1, que são freqüentemente chamados de módulos ou divisores. Vamos denotar por N o produto de n_i.

O teorema chinês do resto afirma que, se n_i são primos pares, e se a₁,..., a_k são inteiros tais que 0 ≤ a_i < n_i para cada i, então há um e apenas um inteiro x, tal que 0 ≤ x < N e o restante da divisão euclidiana de x por n_i é a_i para cada i.

Isso pode ser reiniciado da seguinte forma em termos de congruências: Se o $n_{i}$ são pares coprime, e se um₁, um_k são quaisquer inteiros, então o sistema

{displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\&,,,vdots \x&equiv a_{k}{pmod {n_{k}}},end{aligned}}}

tem uma solução e quaisquer duas soluções, digamos x₁ e x₂, são módulos congruentes N, ou seja, $x 1 \equiv x 2 (mod N)$ .

Na álgebra abstrata, o teorema é frequentemente reformulado como: se os n_i são primos pares, o mapa

{displaystyle x{bmod {N}};mapsto ;(x{bmod {n}}_{1},,ldots,x{bmod {n}}_{k})}

define um isomorfismo de anel

{displaystyle mathbb {Z} /Nmathbb {Z} cong mathbb {Z} /n_{1}mathbb {Z} times cdots times mathbb {Z} /n_{k}mathbb {Z} }

entre o anel de inteiros modulo N e o produto direto dos anéis de inteiros modulo o n_Eu.... Isso significa que para fazer uma sequência de operações aritméticas em ${displaystyle mathbb {Z} /Nmathbb {Z}}$ um pode fazer a mesma computação independentemente em cada ${displaystyle mathbb {Z} /n_{i}mathbb {Z} }$ e, em seguida, obter o resultado aplicando o isomorfismo (à direita à esquerda). Isso pode ser muito mais rápido do que a computação direta se N e o número de operações são grandes. Isto é amplamente utilizado, sob o nome computação multimodular, para álgebra linear sobre os inteiros ou os números racionais.

O teorema também pode ser expresso na linguagem da combinatória como o fato de que as progressões aritméticas infinitas de inteiros formam uma família Helly.

Prova

A existência e a unicidade da solução podem ser provadas independentemente. No entanto, a primeira prova de existência, apresentada a seguir, usa essa unicidade.

Singularidade

Suponha que $x$ e $y$ são soluções para todas as congruências. Como $x$ e $y$ dê o mesmo resto, quando dividido por $n i$ , sua diferença $x - y$ é um múltiplo de cada $n i$ . Como os $n i$ são coprimos emparelhados, seu produto $N$ também divide $x - y$ e, portanto, $x$ e $y$ são módulos congruentes $N$ . Se $x$ e $y$ devem ser não negativos e menores que $N$ (como na primeira declaração do teorema), então sua diferença pode ser um múltiplo de $N$ somente se $x = y$ .

Existência (primeira prova)

O mapa

{displaystyle x{bmod {N}}mapsto (x{bmod {n}}_{1},ldotsx{bmod {n}}_{k})}

mapeia classes de congruência módulo $N$ para sequências de classes de congruência módulo $n i$ . A prova de unicidade mostra que este mapa é injetivo. Como o domínio e o contradomínio deste mapa possuem o mesmo número de elementos, o mapa também é sobrejetivo, o que prova a existência da solução.

Esta prova é muito simples, mas não fornece nenhuma maneira direta de calcular uma solução. Além disso, não pode ser generalizado para outras situações em que a prova a seguir pode.

Existência (prova construtiva)

A existência pode ser estabelecida por uma construção explícita de $x$ . Esta construção pode ser dividida em duas etapas, primeiro resolvendo o problema no caso de dois módulos, e então estendendo esta solução para o caso geral por indução no número de módulos.

Caso de dois módulos

Queremos resolver o sistema:

{displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\x&equiv a_{2}{pmod {n_{2}}},end{aligned}}}

Onde? $n_{1}$ e $n_{2}$ são coprime.

A identidade de Bézout afirma a existência de dois inteiros $m_{1}$ e $m_{2}$ tal que

{displaystyle m_{1}n_{1}+m_{2}n_{2}=1.}

Os inteiros $m_{1}$ e $m_{2}$ pode ser computado pelo algoritmo estendido Euclidean.

Uma solução é dada por

{displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}

Na verdade,

{displaystyle {begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},end{aligned}}}

implicando que ${displaystyle xequiv a_{1}{pmod {n_{1}}}.}$ A segunda congruência é provada de forma semelhante, trocando os subscritos 1 e 2.

Caso geral

Considere uma sequência de equações de congruência:

{displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\&vdots \x&equiv a_{k}{pmod {n_{k}}},end{aligned}}}

onde o $n_{i}$ são coprime emparelhado. As duas primeiras equações têm uma solução ${displaystyle a_{1,2}}$ fornecido pelo método da seção anterior. O conjunto das soluções dessas duas primeiras equações é o conjunto de todas as soluções da equação

{displaystyle xequiv a_{1,2}{pmod {n_{1}n_{2}}}.}

Como o outro $n_{i}$ são coprime com ${displaystyle n_{1}n_{2},}$ Isso reduz a resolução do problema inicial de $k$ equações para um problema semelhante com $k-1$ equações. Iterando o processo, um recebe eventualmente as soluções do problema inicial.

Existência (construção direta)

Para construir uma solução, não é necessário fazer uma indução no número de módulos. No entanto, tal construção direta envolve mais computação com grandes números, o que a torna menos eficiente e menos utilizada. No entanto, a interpolação de Lagrange é um caso especial dessa construção, aplicada a polinômios em vez de inteiros.

Vamos. ${displaystyle N_{i}=N/n_{i}}$ ser o produto de todos os moduli mas um. Como $n_{i}$ são coprime emparelhado, $N_{i}$ e $n_{i}$ são coprime. Assim aplica-se a identidade de Bézout, e existem inteiros $M_{i}$ e $m_{i}$ tal que

{displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}

Uma solução do sistema de congruências é

{displaystyle x=sum _{i=1}^{k}a_{i}M_{i}N_{i}.}

Na verdade, como $N_{j}$ é um múltiplo de $n_{i}$ para ${displaystyle ineq j,}$ nós temos

{displaystyle xequiv a_{i}M_{i}N_{i}equiv a_{i}(1-m_{i}n_{i})equiv a_{i}{pmod {n_{i}}},}

para todos $i.$

Computação

Considere um sistema de congruências:

{displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\&vdots \x&equiv a_{k}{pmod {n_{k}}},\end{aligned}}}

onde o $n_{i}$ são pares coprime, e deixe ${displaystyle N=n_{1}n_{2}cdots n_{k}.}$ Nesta seção vários métodos são descritos para a computação da solução única para $x$ , tal que $<math alttext="{displaystyle 0leq x0\leq \leq x<N,{displaystyle 0leq x<N,} <img alt="{displaystyle 0leq x$ e estes métodos são aplicados no exemplo

{displaystyle {begin{aligned}x&equiv 0{pmod {3}}\x&equiv 3{pmod {4}}\x&equiv 4{pmod {5}}.end{aligned}}}

Vários métodos de computação são apresentados. Os dois primeiros são úteis para pequenos exemplos, mas tornam-se muito ineficientes quando o produto ${displaystyle n_{1}cdots n_{k}}$ é grande. O terceiro usa a prova de existência dada em § Existence (prova construtiva). É o mais conveniente quando o produto ${displaystyle n_{1}cdots n_{k}}$ é grande, ou para computação de computador.

Pesquisa sistemática

É fácil verificar se um valor de $x$ é uma solução: basta calcular o resto da divisão euclidiana de $x$ por cada $n i$ . Assim, para encontrar a solução, basta verificar sucessivamente os inteiros de $0$ a $N$ até encontrar a solução.

Apesar de muito simples, este método é muito ineficiente. Para o exemplo simples considerado aqui, $40$ inteiros (incluindo $0$ ) devem ser verificados para encontrar a solução, que é $39$ . Este é um algoritmo de tempo exponencial, pois o tamanho da entrada é, até um fator constante, o número de dígitos de $N$ , e o número médio de operações é da ordem de $N$ .

Portanto, este método raramente é usado, nem para computação manuscrita nem em computadores.

Pesquisar por peneiramento

As duas mais pequenas soluções, 23 e 128, da formulação original do problema teorema restante chinês encontrado usando uma peneira

A busca da solução pode ser feita dramaticamente mais rápida por peneiramento. Para este método, supomos, sem perda de generalidade, que $<math alttext="{displaystyle 0leq a_{i}0≤ ≤ umEu...<nEu...{displaystyle 0leq a_{i}<n_{i}}<img alt="{displaystyle 0leq a_{i}$ (se não fosse o caso, bastaria substituir cada um $a_{i}$ pelo restante de sua divisão por $n_{i}$ ). Isto implica que a solução pertence à progressão aritmética

{displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},ldots }

Ao testar os valores desses números modulo ${displaystyle n_{2},}$ um eventualmente encontra uma solução $x_{2}$ das duas primeiras congruências. Então a solução pertence à progressão aritmética

{displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},ldots }

Testando os valores desses números modulo ${displaystyle n_{3},}$ e continuando até que cada módulo tenha sido testado eventualmente produz a solução.

Este método é mais rápido se o moduli foi ordenado pela diminuição do valor, ou seja, se $n_{2}>cdots >n_{k}.}" xmlns="http://www.w3.org/1998/Math/MathML">n1>n2>⋯ ⋯ >nk.Não. n_{1}>n_{2}>cdots - Sim.n_{2}>cdots >n_{k}.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba4dd6fff3697e044c65ec36913cc6ceb4715d53" style="vertical-align: -0.671ex; width:20.047ex; height:2.176ex;"/>$ Por exemplo, isso dá a seguinte computação. Consideramos primeiro os números que são congruentes a 4 modulo 5 (o maior módulo), que são 4, 9 = 4 + 5, 14 = 9 + 5, Para cada um deles, compute o restante por 4 (o segundo maior módulo) até obter um número congruente para 3 modulo 4. Então pode-se prosseguir adicionando 20 = 5 × 4 em cada etapa, e computando apenas os restos por 3. Isto dá

4 mod 4 → 0. Continuar

4 + 5 = 9 mod 4 →1. Continue.

9 + 5 = 14 mod 4 → 2. Continuar

14 + 5 = 19 mod 4 → 3. OK, continue considerando restos modulo 3 e adicionando 5 × 4 = 20 cada vez

19 mod 3 → 1. Continuar

19 + 20 = 39 mod 3 → 0. OK, este é o resultado.

Este método funciona bem para computação manuscrita com um produto de módulos que não é muito grande. No entanto, é muito mais lento do que outros métodos, para produtos muito grandes de módulos. Embora dramaticamente mais rápido que a busca sistemática, esse método também tem uma complexidade de tempo exponencial e, portanto, não é usado em computadores.

Usando a construção de existência

A prova de existência construtiva mostra que, no caso de dois moduli, a solução pode ser obtida pela computação dos coeficientes Bézout do moduli, seguidos por algumas multiplicações, adições e reduções modulo $n_{1}n_{2}$ (para obter um resultado no intervalo ${displaystyle (0,n_{1}n_{2}-1)}$ ). Como os coeficientes do Bézout podem ser computados com o algoritmo euclidiano estendido, toda a computação, no máximo, tem uma complexidade de tempo quadrático de ${displaystyle O((s_{1}+s_{2})^{2}),}$ Onde? $s_{i}$ denota o número de dígitos de ${displaystyle n_{i}.}$

Para mais de dois módulos, o método para dois módulos permite a substituição de quaisquer duas congruências por uma única congruência módulo o produto dos módulos. A iteração deste processo fornece eventualmente a solução com uma complexidade, que é quadrática no número de dígitos do produto de todos os módulos. Essa complexidade de tempo quadrática não depende da ordem em que os módulos são reagrupados. Pode-se reagrupar os dois primeiros módulos, depois reagrupar o módulo resultante com o próximo, e assim por diante. Essa estratégia é a mais fácil de implementar, mas também requer mais computação envolvendo grandes números.

Outra estratégia consiste em particionar os módulos em pares cujo produto tenha tamanhos comparáveis (tanto quanto possível), aplicando, em paralelo, o método dos dois módulos a cada par, e iterando com um número de módulos aproximadamente dividido por dois. Este método permite uma fácil paralelização do algoritmo. Além disso, se algoritmos rápidos (isto é, algoritmos que trabalham em tempo quase linear) forem usados para as operações básicas, esse método fornece um algoritmo para toda a computação que funciona em tempo quase linear.

No exemplo atual (que tem apenas três módulos), ambas as estratégias são idênticas e funcionam da seguinte maneira.

A identidade de Bézout para 3 e 4 é

{displaystyle 1times 4+(-1)times 3=1.}

Colocar isso na fórmula dada para provar a existência dá

{displaystyle 0times 1times 4+3times (-1)times 3=-9}

para uma solução das duas primeiras congruências, as outras soluções sendo obtidas adicionando a −9 qualquer múltiplo de 3 × 4 = 12. Pode-se continuar com qualquer uma dessas soluções, mas a solução 3 = −9 +12 é menor (em valor absoluto) e, portanto, leva provavelmente a um cálculo mais fácil

Identidade de Bézout para 5 e 3 × 4 = 12 é

{displaystyle 5times 5+(-2)times 12=1.}

Aplicando novamente a mesma fórmula, obtemos a solução do problema:

{displaystyle 5times 5times 3+12times (-2)times 4=-21.}

As outras soluções são obtidas adicionando qualquer múltiplo de 3 × 4 × 5 = 60, e a menor solução positiva é −21 + 60 = 39.

Como um sistema diofantino linear

O sistema de congruências resolvido pelo teorema chinês do resto pode ser reescrito como um sistema de equações diofantinas lineares:

{displaystyle {begin{aligned}x&=a_{1}+x_{1}n_{1}\&vdots \x&=a_{k}+x_{k}n_{k},end{aligned}}}

onde os inteiros desconhecidos são $x$ e o $x_{i}.$ Portanto, todo método geral para resolver tais sistemas pode ser usado para encontrar a solução do teorema restante chinês, como a redução da matriz do sistema para a forma normal de Smith ou forma normal de Hermite. No entanto, como de costume ao usar um algoritmo geral para um problema mais específico, esta abordagem é menos eficiente do que o método da seção anterior, com base em um uso direto da identidade de Bézout.

Sobre domínios ideais principais

Em § Declaração, o teorema restante chinês foi declarado de três maneiras diferentes: em termos de restos, de congruências e de um isomorfismo de anel. A declaração em termos de restos não se aplica, em geral, aos principais domínios ideais, uma vez que os restos não são definidos em tais anéis. No entanto, as duas outras versões fazem sentido sobre um domínio ideal principal $R$ : basta substituir "integer" por "elemento do domínio" e $mathbb {Z}$ por $R$ . Essas duas versões do teorema são verdadeiras neste contexto, porque as provas (exceto para a primeira prova de existência), são baseadas na identidade de Euclid e Bézout, que são verdadeiras sobre cada domínio principal.

No entanto, em geral, o teorema é apenas um teorema de existência e não fornece nenhuma maneira de calcular a solução, a menos que se tenha um algoritmo para calcular os coeficientes da identidade de Bézout.

Sobre anéis polinomiais univariados e domínios euclidianos

A declaração em termos de restos dados na declaração de teorema de § não pode ser generalizada para qualquer domínio ideal principal, mas sua generalização para domínios euclidianos é simples. Os polinômios univariados sobre um campo é o exemplo típico de um domínio euclidiano que não é os inteiros. Portanto, declaramos o teorema para o caso do anel ${displaystyle R=K[X]}$ para um campo $K.$ Para obter o teorema para um domínio Euclidiano geral, basta substituir o grau pela função euclidiana do domínio euclidiano.

O teorema restante chinês para polinômios é assim: Deixe ${displaystyle P_{i}(X)}$ (o moduli) ser, para ${displaystyle i=1,dotsk}$ , parwise coprime polinômios em ${displaystyle R=K[X]}$ . Vamos. ${displaystyle d_{i}=deg P_{i}}$ ser o grau de ${displaystyle P_{i}(X)}$ e $D$ ser a soma da ${displaystyle d_{i}.}$ Se ${displaystyle A_{i}(X),ldotsA_{k}(X)}$ são polinomiais tais que ${displaystyle A_{i}(X)=0}$ ou $<math alttext="{displaystyle deg A_{i}deg⁡ ⁡ AEu...<DEu...{displaystyle deg A_{i}<d_{i}}<img alt="{displaystyle deg A_{i}$ para todos $Eu...$ , então, há um e apenas um polinomial $P(X)$ , tal que $<math alttext="{displaystyle deg Pdeg P<D{displaystyle deg P<D} <img alt="{displaystyle deg P$ e o restante da divisão euclidiana $P(X)$ por ${displaystyle P_{i}(X)}$ o ${displaystyle A_{i}(X)}$ para todos $Eu...$ .

A construção da solução pode ser feita como em § Existência (prova construtiva) ou § Existência (prova direta). No entanto, a última construção pode ser simplificada usando, como segue, a decomposição de frações parciais em vez do algoritmo euclidiano estendido.

Assim, queremos encontrar um polinômio $P(X)$ , que satisfaz as congruências

{displaystyle P(X)equiv A_{i}(X){pmod {P_{i}(X)}},}

para ${displaystyle i=1,ldotsk.}$

Considere os polinômios

{displaystyle {begin{aligned}Q(X)&=prod _{i=1}^{k}P_{i}(X)\Q_{i}(X)&={frac {Q(X)}{P_{i}(X)}}.end{aligned}}}

A decomposição parcial da fração ${displaystyle 1/Q(X)}$ dá $k$ polinômios ${displaystyle S_{i}(X)}$ com graus $<math alttext="{displaystyle deg S_{i}(X)deg⁡ ⁡ SEu...(X)<DEu...,{displaystyle deg S_{i}(X)<d_{i},}<img alt="{displaystyle deg S_{i}(X)$ tal que

{displaystyle {frac {1}{Q(X)}}=sum _{i=1}^{k}{frac {S_{i}(X)}{P_{i}(X)}},}

e assim

{displaystyle 1=sum _{i=1}^{k}S_{i}(X)Q_{i}(X).}

Então uma solução do sistema de congruência simultânea é dada pelo polinômio

{displaystyle sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X).}

Na verdade, temos

{displaystyle sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)equiv A_{i}(X){pmod {P_{i}(X)}},}

para ${displaystyle 1leq ileq k.}$

Esta solução pode ter um grau maior do que ${displaystyle D=sum _{i=1}^{k}d_{i}.}$ A solução única de grau menos do que $D$ pode ser deduzido considerando o restante ${displaystyle B_{i}(X)}$ da divisão Euclidiana ${displaystyle A_{i}(X)S_{i}(X)}$ por ${displaystyle P_{i}(X).}$ Esta solução é

{displaystyle P(X)=sum _{i=1}^{k}B_{i}(X)Q_{i}(X).}

Interpolação Lagrange

Um caso especial do teorema chinês do resto para polinômios é a interpolação de Lagrange. Para isso, considere $k$ polinômios mônicos de grau um:

{displaystyle P_{i}(X)=X-x_{i}.}

Eles são coprime pares se o $x_{i}$ são todos diferentes. O restante da divisão por ${displaystyle P_{i}(X)}$ de um polinômio $P(X)$ o $P(x_i)$ , pelo teorema restante polinomial.

Agora, deixa. $A_{1},ldotsA_{k}$ ser constantes (polinomiais de grau 0) em $K.$ Tanto a interpolação de Lagrange quanto o teorema restante chinês afirmam a existência de um polinomial único ${displaystyle P(X),}$ de grau inferior a $k$ tal que

{displaystyle P(x_{i})=A_{i},}

para todos $i.$

A fórmula de interpolação de Lagrange é exatamente o resultado, neste caso, da construção da solução acima. Mais precisamente, deixe

{displaystyle {begin{aligned}Q(X)&=prod _{i=1}^{k}(X-x_{i})\[6pt]Q_{i}(X)&={frac {Q(X)}{X-x_{i}}}.end{aligned}}}

A decomposição parcial da fração ${displaystyle {frac {1}{Q(X)}}}$ o

{displaystyle {frac {1}{Q(X)}}=sum _{i=1}^{k}{frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}

Na verdade, reduzindo o lado direito a um denominador comum, obtém-se

{displaystyle sum _{i=1}^{k}{frac {1}{Q_{i}(x_{i})(X-x_{i})}}={frac {1}{Q(X)}}sum _{i=1}^{k}{frac {Q_{i}(X)}{Q_{i}(x_{i})}},}

e o numerador é igual a um, como sendo um polinômio de grau menos do que $k,$ que leva o valor um para $k$ diferentes valores de $X.$

Usando a fórmula geral acima, obtemos a fórmula de interpolação de Lagrange:

{displaystyle P(X)=sum _{i=1}^{k}A_{i}{frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}

Interpolação Hermite

A interpolação de Hermite é uma aplicação do teorema chinês do resto para polinômios univariados, que podem envolver módulos de graus arbitrários (a interpolação de Lagrange envolve apenas módulos de grau um).

O problema consiste em encontrar um polinômio de menor grau possível, tal que o polinômio e suas primeiras derivadas tomem valores dados em alguns pontos fixos.

Mais precisamente, deixe $x_{1},ldotsx_{k}$ ser $k$ elementos do campo de terra $K,$ e, para ${displaystyle i=1,ldotsk,}$ Deixa-me. ${displaystyle a_{i,0},a_{i,1},ldotsa_{i,r_{i}-1}}$ ser os valores do primeiro $r_{i}$ derivados do polinomial procurado em $x_{i}$ (incluindo o derivado 0, que é o valor do próprio polinomial). O problema é encontrar um polinomial $P(X)$ tal que o seu JJderivado toma o valor $a_{i,j}$ em ${displaystyle x_{i},}$ para $i=1,ldotsk$ e ${displaystyle j=0,ldotsr_{j}.}$

Considere o polinômio

{displaystyle P_{i}(X)=sum _{j=0}^{r_{i}-1}{frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}

Este é o polinômio Taylor de ordem ${displaystyle r_{i}-1}$ em $x_{i}$ , do polinomial desconhecido ${displaystyle P(X).}$ Portanto, devemos ter

{displaystyle P(X)equiv P_{i}(X){pmod {(X-x_{i})^{r_{i}}}}.}

Por outro lado, qualquer polinomial ${displaystyle P(X)}$ que satisfaz estes $k$ congruências, em particular verifica, para qualquer ${displaystyle i=1,ldotsk}$

{displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}

por conseguinte, ${displaystyle P_{i}(X)}$ é a sua Taylor polinomial de ordem ${displaystyle r_{i}-1}$ em $x_{i}$ , isto é, $P(X)$ resolve o problema inicial de interpolação Hermite. O teorema restante chinês afirma que existe exatamente um polinômio de grau menos do que a soma da ${displaystyle r_{i},}$ que satisfaz estes $k$ congruências.

Existem várias maneiras de computar a solução ${displaystyle P(X).}$ Pode-se usar o método descrito no início de § Sobre anéis polinomiais univariados e domínios euclidianos. Pode-se também usar as construções dadas em § Existência (prova construtiva) ou § Existência (prova direta).

Generalização para módulos não coprime

O teorema restante chinês pode ser generalizado para moduli não-coprime. Vamos. ${displaystyle m,n,a,b}$ ser qualquer inteiro, deixe ${displaystyle g=gcd(m,n)}$ ; ${displaystyle M=operatorname {lcm} (m,n)}$ , e considerar o sistema de congruências:

{displaystyle {begin{aligned}x&equiv a{pmod {m}}\x&equiv b{pmod {n}},end{aligned}}}

Se ${displaystyle aequiv b{pmod {g}}}$ , então este sistema tem uma solução única modulo ${displaystyle M=mn/g}$ . Caso contrário, não tem soluções.

Se alguém usa a identidade de Bézout para escrever ${displaystyle g=um+vn}$ , então a solução é dada por

{displaystyle x={frac {avn+bum}{g}}.}

Isso define um número inteiro, pois $g$ divide ambos $m$ e $n$ . Caso contrário, a prova é muito semelhante àquela para módulos coprimos.

Generalização para anéis arbitrários

O teorema restante chinês pode ser generalizado para qualquer anel, usando ideais coprime (também chamados ideais comaximais). Dois ideais $Eu...$ e $JJ$ são coprime se há elementos $iin I$ e $jin J$ tal que ${displaystyle i+j=1.}$ Esta relação desempenha o papel da identidade de Bézout nas provas relacionadas com esta generalização, que de outra forma são muito semelhantes. A generalização pode ser declarada da seguinte forma.

Vamos. $Eu... 1, Eu... k$ ser ideais de dois lados de um anel $R$ e deixar $Eu...$ ser a interseção deles. Se os ideais são coprime em pares, temos o isomorfismo:

{displaystyle {begin{aligned}R/I&to (R/I_{1})times cdots times (R/I_{k})\x{bmod {I}}&mapsto (x{bmod {I}}_{1},,ldots,x{bmod {I}}_{k}),end{aligned}}}

entre o anel quociente $R/I$ e o produto direto do ${displaystyle R/I_{i},}$ Onde " ${displaystyle x{bmod {I}}}$ " denota a imagem do elemento $x$ no anel quociente definido pelo ideal ${displaystyle I.}$ Além disso, se $R$ é comutativo, então a interseção ideal de ideais coprime em pares é igual ao seu produto; isto é

{displaystyle I=I_{1}cap I_{2}cap cdots cap I_{k}=I_{1}I_{2}cdots I_{k},}

if $I i$ e $I j$ são primos primos para todo $i \neq j .$

Interpretação em termos de idempotentes

Vamos. ${displaystyle I_{1},I_{2},dotsI_{k}}$ ser pares coprime dois lados ideais com ${displaystyle bigcap _{i=1}^{k}I_{i}=0,}$ e

{displaystyle varphi:Rto (R/I_{1})times cdots times (R/I_{k})}

ser o isomorfismo definido acima. Vamos. ${displaystyle f_{i}=(0,ldots1,ldots0)}$ ser o elemento de ${displaystyle (R/I_{1})times cdots times (R/I_{k})}$ cujos componentes são todos $0$ exceto o $Eu...$ o que é $1$ e ${displaystyle e_{i}=varphi ^{-1}(f_{i}).}$

O $e_{i}$ são idempotentes centrais que são emparelhados ortogonais; isto significa, em particular, que ${displaystyle e_{i}^{2}=e_{i}}$ e ${displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$ para todos $Eu...$ e $JJ$ . Além disso, um tem ${textstyle e_{1}+cdots +e_{n}=1,}$ e ${displaystyle I_{i}=R(1-e_{i}).}$

Em resumo, este teorema generalizado do resto chinês é a equivalência entre fornecer ideais de dois lados coprimos aos pares com uma interseção zero e fornecer idempotentes ortogonais centrais e aos pares que somam $1$ .

Aplicativos

Numeração de sequência

O teorema chinês do resto foi usado para construir uma numeração de Gödel para sequências, que está envolvida na prova dos teoremas da incompletude de Gödel.

Transformada rápida de Fourier

O algoritmo FFT (também chamado algoritmo Good-Thomas) usa o teorema restante chinês para reduzir a computação de uma rápida transformação de Fourier de tamanho $n_{1}n_{2}$ à computação de duas transformações rápidas de Fourier de tamanhos menores $n_{1}$ e $n_{2}$ (desde que $n_{1}$ e $n_{2}$ são coprime).

Criptografia

A maioria das implementações de RSA usa o teorema do resto chinês durante a assinatura de certificados HTTPS e durante a descriptografia.

O teorema chinês dos restos também pode ser usado no compartilhamento de segredos, que consiste na distribuição de um conjunto de compartilhamentos entre um grupo de pessoas que, todas juntas (mas ninguém sozinho), podem recuperar um certo segredo de um determinado conjunto de compartilhamentos. Cada uma das partes é representada em uma congruência, e a solução do sistema de congruências usando o teorema chinês dos restos é o segredo a ser recuperado. O compartilhamento de segredo usando o teorema do resto chinês usa, junto com o teorema do resto chinês, sequências especiais de inteiros que garantem a impossibilidade de recuperar o segredo de um conjunto de compartilhamentos com menos de uma certa cardinalidade.

Resolução de ambiguidade de intervalo

As técnicas de resolução de ambigüidade de alcance usadas com radar de frequência de repetição de pulso médio podem ser vistas como um caso especial do teorema chinês do resto.

Decomposição de sobrejeções de grupos abelianos finitos

Dada uma surjeção ${displaystyle mathbb {Z} /nto mathbb {Z} /m}$ de grupos abelianos finitos, podemos usar o teorema restante chinês para dar uma descrição completa de qualquer tal mapa. Em primeiro lugar, o teorema dá isomorfismos

{displaystyle {begin{aligned}mathbb {Z} /n&cong mathbb {Z} /p_{n_{1}}^{a_{1}}times cdots times mathbb {Z} /p_{n_{i}}^{a_{i}}\mathbb {Z} /m&cong mathbb {Z} /p_{m_{1}}^{b_{1}}times cdots times mathbb {Z} /p_{m_{j}}^{b_{i}}end{aligned}}}

Onde? ${displaystyle {p_{m_{1}},ldotsp_{m_{j}}}subseteq {p_{n_{1}},ldotsp_{n_{i}}}}$ . Além disso, para qualquer mapa induzido

{displaystyle mathbb {Z} /p_{n_{k}}^{a_{k}}to mathbb {Z} /p_{m_{l}}^{b_{l}}}

da surjeção original, temos ${displaystyle a_{k}geq b_{l}}$ e ${displaystyle p_{n_{k}}=p_{m_{l}},}$ desde para um par de primos $p,q$ , as únicas surjeções não zero

{displaystyle mathbb {Z} /p^{a}to mathbb {Z} /q^{b}}

pode ser definido se $p=q$ e $ageq b$ .

Essas observações são essenciais para a construção do anel de inteiros profinitos, que é dado como um limite inverso de todos esses mapas.

Teorema de Dedekind

Teorema de Dedekind sobre a independência linear dos caracteres. Seja $M$ um monoid e $k$ um domínio integral, visto como um monoid considerando a multiplicação em $k$ . Então qualquer família finita $(f i) i \in I$ de homomorfismos monoides distintos $f i : M \to k$ é linearmente independente. Em outras palavras, cada família $(α i) i \in I$ de elementos $α i \in k$ satisfatório

sum_{i in I}alpha_i f_i = 0

deve ser igual à família $(0) i \in I$ .

Prova. Primeiro, suponha que $k$ é um campo, caso contrário, substitua o domínio integral $k$ por seu campo quociente e nada mudará. Podemos estender linearmente os homomorfismos monoides $f i : M \to k$ para $k$ -homomorfismos álgebra $F i : k [M] \to k$ , onde $k [M]$ é o anel monoide de $M$ sobre $k$ . Então, por linearidade, a condição

sum_{iin I}alpha_i f_i = 0,

rendimentos

sum_{i in I}alpha_i F_i = 0.

Em seguida, para $i, j \in I; i \neq j$ os dois mapas $k$ -lineares $F i : k [M] \to k$ e $F j : k [M] \to k$ não são proporcionais entre si. Caso contrário $f i$ e $f j$ também seriam proporcionais e, portanto, iguais, pois, como homomorfismos monóides, eles satisfazem: $f i (1) = 1 = f j (1)$ , o que contradiz a suposição de que eles são distintos.

Portanto, os kernels $Ker F i$ e $Ker F j$ são distintos. Desde $k [M]/Ker F i ≅ F i (k [M]) = k$ é um campo, $Ker F i$ é um ideal maximal de $k [M]$ para cada $i$ em $I$ . Por serem distintos e maximais os ideais $Ker F i$ e $Ker F j$ são coprimos sempre que $i \neq j$ . O Teorema Chinês do Resto (para anéis gerais) produz um isomorfismo: