miniatura|Formulación orixinal de Sunzi: 2 (mod 7) coa solución con k enteiro En matemáticas, o teorema teorema chinés do resto expón que se coñecemos os restos da división euclidiana dun enteiro por varios enteiros, daquela podemos determinar o resto da división de polo produto destes enteiros, baixo a condición de que os divisores sexan coprimos por pares (ningunha parella de divisores comparte un factor común á parte do 1).
As palabras resto e residuo son equivalentes, e ambas as dúas pódense ver nos documentos existentes.
Por exemplo, se sabemos 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, daquela sen saber o valor de n, podemos determinar que o resto de n dividido por 105 (produto de 3, 5, e 7) é 23. Importante: isto dinos que se n é un número natural menor de 105, entón 23 é o único valor posíbel de .
A redacción coñecida máis antiga do teorema foi feita polo matemático chinés Sunzi no Sunzi Suanjing entre os séculos III e V (d.C).
O teorema chinés do resto úsase amplamente para computar enteiros grandes, pois permite traballar con números de tamaño limitado.
O teorema chinés do resto (expresado como congruencias) é certo sobre todo dominio ideal principal. Está xeneralizado a calquera anel, cunha formulación que implica ideais bilaterais.
Historia A cita do matemático chinés Sunzi no Sunzi Suanjing foi:
O que ven sendo un algoritmo para resolver este problema foi descrito por Aryabhata (século VI). Tamén Brahmagupta (no século VII) trataba casos especiais do teorema chinés do resto e aparecen no Liber Abaci (1202) de Fibonacci. O resultado foi máis tarde xeneralizado cunha solución completa chamada Da-yan-shu () en Qin Jiushao 1247 Tratado Matemático en Nove Seccións que foi traducido a inglés no século XIX polo misioneiro británico Alexander Wylie. miniatura|O teorema chinés do resto aparece no libro de Gauss de Disquisitiones Arithmeticae. A noción de congruencia foi introducida e utilizada por Carl Friedrich Gauss no seu Disquisitiones Arithmeticae de 1801. Gauss Ilustra o teorema chinés do resto nun problema que implica calendarios, "atopar os anos que teñen un determinado número de período en relación ao ciclo solar e lunar e a indición romana (período de 15 anos)." Gauss Presenta un procedemento para solucionar o problema que xa era utilizado por Leonhard Euler.
Enunciado Sexan enteiros superiores a 1, chamados módulos. Denotamos por o produto dos .
Enunciando o teorema chinés do resto podemos dicir que se os son coprimos por pares, e se son enteiros tal que para cada , daquela hai un e só un enteiro x, tal que e o resto da división euclidiana de x por é para cada .
Isto pódese reformular do seguinte xeito en termos de congruencias: Se os son coprimos por pares, e se
son enteiros calquera, daquela o sistema
ten solución, e dúas solucións calquera, digamos e , son congruentes módulo N, é dicir, .
En álxebra abstracta, o teorema adoita ser reformulado como: se os son coprimos por pares, o mapa
Define un isomorfismo de aneis
entre o anel de enteiros módulo N e o produto directo dos aneis de enteiros módulo os . Isto significa que para facer unha secuencia de operacións aritméticas en pódese facer o mesmo cálculo independentemente en cada e despois obtér o resultado aplicando o isomorfismo (de dereita a esquerda). Isto será máis rápido que o cálculo directo se N e o número de operacións son grandes. Isto é amplamente usado, baixo o nome de computación multimodular, en álxebra linear sobre os números enteiros ou os números racionais.
O teorema tamén se pode reformular na linguaxe da combinatoria porque as infinitas progresións aritméticas de números enteiros teñen a propiedade de Helly.
Proba A existencia e a unicidade da solución poden probarse independentemente. Con todo, a primeira proba de existencia, dada abaixo, utiliza a unicidade.
Unicidade Se e son ambas as dúas solucións a todas as congruencias. Como e dan o mesmo resto, ao dividirse entre , temos que a súa diferenza é múltiplo de cada . Como os son coprimos por pares, o seu produto tamén divide , polo que e son congruentes módulo . Se e se supón que non son negativos e son menores que (como no primeiro enunciado do teorema), entón a súa diferenza só pode ser múltiplo de se .
Existencia (primeira proba) Temos
este mapa asigna clases de congruencia módulo a múltiples clases de congruencia módulo . A proba de unicidade mostra que este mapa é inxectivo. Como o dominio e o codominio deste mapa teñen o mesmo número de elementos, o mapa tamén é sobrexectivo, o que proba a existencia da solución.
Esta proba é moi sinxela mais non proporciona ningún xeito directo de calcular unha solución. Ademais, non se pode xeneralizar a outras situacións nas que a seguinte proba si.
Existencia e solución A existencia pódese establecer mediante unha construción explícita de . Esta construción pódese dividir en dous pasos, primeiro resolvendo o problema no caso de dous módulos, e despois estendendo esta solución ao caso xeral por indución sobre o número de módulos.
Caso de dous módulos Queremos solucionar o sistema:
onde e son coprimos.
Pola identidade de Bézout sabemos da existencia de dous números enteiros e tal que
Os enteiros e pódense calcular mediante o algoritmo euclidiano estendido.
Unha solución vén dada por
Comprobamos,
iso implica que A segunda congruencia próbase de xeito similar, trocando os subíndices 1 e 2.
O conxunto total de solucións será logo para enteiro.
Caso xeral Considere unha secuencia de ecuacións de congruencia:
imos ver unha proba por construción e un exemplo por un método moi rápido
Sexa o produto de todos os módulos menos un. Como os son coprimos por pares, e son coprimos. Aplícamos a identidade de Bézout, e existen números enteiros e tal que
Unha solución do sistema de congruencias é
De feito, como é múltiplo de para temos
para cada
Exemplos Para o caso de dúas congruencias imos ver dúas versións do problema dos piratas.
a) 17 piratas reparten un botín de máis de 100 moedas e sobra 1. Despois morre 1 pirata, reparten e segue a sobrar unha.
Aquí
Por tanto, a primeira solución
Cando a identidade de Bézout non é evidente pódese calcular co algoritmo de Euclides estendido.
b) 17 piratas reparten un botín de máis de 100 moedas e sobra 1. Despois morre 1 pirata, reparten e sobran 7.
Aquí
Por tanto, a primeira solución
Caso xeral Exemplo con catro congruencias,
Solución: o módulo da solución completa debe ser , por seren coprimos.
E comezamos os cálculos
. .
Como un sistema diofantiano linear O sistema de congruencias resolvido polo teorema chinés do resto pódese reescribir como un sistema de ecuacións diofantianas lineares:
Polo tanto, pódense usar todos os métodos xerais para resolver tales sistemas, como a redución da matriz do sistema á forma normal de Smith ou á forma normal de Hermite.
Sobre dominios de ideais principais O teorema enunciouse de tres formas diferentes: en termos de restos, de congruencias e dun isomorfismo de anel. A declaración en termos de restos non se aplica, en xeral, aos dominios de ideais principais, xa que os restos non se definen nestes aneis. Non obstante, as outras dúas versións teñen sentido sobre un dominio ideal principal : abonda con substituír "enteiro" por "elemento do dominio" e por . Estas dúas versións do teorema son certas neste contexto, porque as demostracións (excepto a primeira proba de existencia), baséanse no lema de Euclides e na identidade de Bézout, que son certas en todos os dominios principais.
Sobre aneis de polinomios dunha variábel e dominios euclidianos Os polinomios univariados sobre un corpo son o exemplo típico dun dominio euclidiano que non son os enteiros. Polo tanto, enunciamos o teorema para o caso do anel para un corpo Para obter o teorema nun dominio euclidiano en xeral, abonda con substituír o grao pola función euclidiana do dominio euclidiano.
O teorema chinés do resto para polinomios é así: Sexan (os módulos), para , polinomios coprimos por pares en . Sexa o grao de , e a suma dos Se son polinomios tales que ou para cada , daquela, hai un e só un polinomio , tal que e o resto da división euclidiana de por é por cada .
Polo tanto, agora queremos atopar un polinomio , que satisfai as congruencias
para
Considere os polinomios
A descomposición en fraccións parciais de dá polinomios de grao tal que
e así
Por tanto unha solución do sistema de congruencias simultáneas vén dada polo polinomio
De feito, temos
para
A solución pode ter un grao superior a Podemos deducir a única solución de grao menor que se consideramos o resto da división euclidiana de por Esta solución é
Interpolación de Lagrange Un caso especial para polinomios é a interpolación de Lagrange. Para isto, considere polinomios mónicos de grao un:
Son coprimos por pares se os son todos diferentes. O resto da división por dun polinomio é , polo teorema do resto.
Agora, sexan constantes (polinomios de grao 0) en Tanto a interpolación de Lagrange como o teorema chinés do resto afirman a existencia dun polinomio único de grao inferior a tal que
para cada
A fórmula de interpolación de Lagrange é exactamente o resultado, neste caso, da construción anterior da solución. Máis precisamente, se temos
A descomposición parcial da fracción é
Agora, se reducimos o lado dereito a un denominador común obtemos
e o numerador é igual a 1, xa que é un polinomio de grao menor que que toma o valor 1 para diferentes valores de Desta fórmula, podemos obter a fórmula de interpolación de Lagrange:
Interpolación de Hermite A interpolación de Hermite é unha aplicación do teorema para polinomios univariados, que admite módulos de graos arbitrarios (a interpolación de Lagrange só admite módulos de grao un).
Debemos conseguir un polinomio do menor grao posible, de xeito que o polinomio e as súas primeiras derivadas tomen valores dados nalgúns puntos fixos.
Sexan , elementos do corpo e, para sexan os valores das primeiras derivadas en do polinomio buscado (incluída a derivada 0, que é o valor do propio polinomio). O problema consiste en atopar un polinomio tal que a súa derivada j -ésima tome o valor en para e
Considere o polinomio
Este é o polinomio de Taylor de orde en do polinomio descoñecido Polo tanto, debemos ter
Pola contra, calquera polinomio que satisfai estas congruencias, en particular verifica, para calquera
polo tanto é o seu polinomio de Taylor de orde en , e con iso temos que resolve o problema inicial da interpolación de Hermite. O teorema chinés do resto afirma que existe exactamente un polinomio de grao menor que a suma dos que satisfai estas congruencias.
Xeneralización a módulos non coprimos O teorema chinés do resto pódese xeneralizar a módulos non coprimos. Sexa ser calquera número enteiro, deixe ; , e considere o sistema de congruencias:
Se , entón este sistema ten unha solución única módulo . En caso contrario, non ten solucións.
Se usamos a identidade de Bézout para escribir , daquela a solución vén dada por
Isto define un número enteiro, xa que divide tanto como . A demostración é moi semellante á dos módulos coprimos.
Xeneralización a aneis arbitrarios O teorema chinés do resto pódese xeneralizar a calquera anel, usando ideais coprimos (tamén chamados ideais comaximais). Dous ideais e son coprimos se hai elementos e tal que Esta relación xoga o papel da identidade de Bézout nas probas relacionadas con esta xeneralización, que polo demais son moi semellantes. A xeneralización pódese expresar do seguinte xeito.
Sexan ideais bilaterais dun anel e sexa a súa intersección. Se os ideais son coprimos por pares, temos o isomorfismo:
entre o anel cociente e o produto directo de onde " " denota a imaxe do elemento no anel cociente definido polo ideal Alén diso, se é conmutativo, daquela, o ideal intersección dos ideais coprimos par pares é igual ao seu produto; é dicir
se e son coprimos para todo .