Teorema chinés do resto

En matemáticas, o teorema teorema chinés do resto expón que se un sabe os restos da división euclidiana dun enteiro n por varios enteiros, daquela un pode determinar o resto da división de n 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 n.

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.

A cita do matemático chinés Sunzi no Sunzi Suanjing foi:^[1]

Hai certas cousas cuxo número se descoñece. Se as contamos por tres, sobran dúas; por cinco, sobran tres; e por sete sobran dúas. Cantas cousas hai?^[2]

O que ven sendo un algoritmo para resolver este problema foi descrito por Aryabhata (século VI).^[3] Tamén Brahmagupta (no século VII) trataba casos especiais do teorema chinés do resto e aparecen no Liber Abaci (1202) de Fibonacci.^[4] 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.^[5][6]

A noción de congruencia foi introducida e utilizada por Carl Friedrich Gauss no seu Disquisitiones Arithmeticae de 1801.^[8] 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.^[9][10]

Sexan ${\displaystyle n_{1},\ldots ,n_{k}}$ enteiros superiores a 1, chamados módulos. Denotamos por N o produto dos ${\displaystyle n_{i}}$.

Enunciando o teorema chinés do resto podemos dicir que se os ${\displaystyle n_{i}}$ son coprimos por pares, e se ${\displaystyle a_{1},\ldots ,a_{k}}$ son enteiros tal que ${\displaystyle 0\leq a_{i}<n_{i}}$ para cada i, daquela hai un e só un enteiro x, tal que ${\displaystyle 0\leq x<N}$ e o resto da división euclidiana de x por ${\displaystyle n_{i}}$ é ${\displaystyle a_{i}}$para cada i.

Isto pódese reformular do seguinte xeito en termos de congruencias: Se os ${\displaystyle n_{i}}$ son coprimos por pares, e se

${\displaystyle a_{1},\ldots ,a_{k}}$ son enteiros calquera, daquela o sistema

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

ten solución, e dúas solucións calquera, digamos ${\displaystyle x_{1}}$ e ${\displaystyle x_{2}}$, son congruentes módulo N, é dicir, x₁ ≡ x₂ (mod N ).^[11]

En álxebra abstracta, o teorema adoita ser reformulado como: se os ${\displaystyle n_{i}}$son coprimos por pares, o mapa

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

Define un isomorfismo de aneis^[12]

${\displaystyle \mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z} }$

entre o anel de enteiros módulo N e o produto directo dos aneis de enteiros módulo os ${\displaystyle n_{i}}$. Isto significa que para facer unha secuencia de operacións aritméticas en ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ pódese facer o mesmo cálculo independentemente en cada ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$ 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.^[13]

A existencia e a unicidade da solución poden probarse independentemente. Con todo, a primeira proba de existencia, dada abaixo, utiliza a unicidade.

Se x e y son ambas as dúas solucións a todas as congruencias. Como x e y dan o mesmo resto, ao dividirse entre n_i, temos que a súa diferenza x − y é múltiplo de cada n_i. Como os n_i son coprimos por pares, o seu produto N tamén divide x − y, polo que x e y son congruentes módulo N. Se x e y se supón que non son negativos e son menores que N (como no primeiro enunciado do teorema), entón a súa diferenza só pode ser múltiplo de N se x = y.

Temos

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

este mapa asigna clases de congruencia módulo N a múltiples clases de congruencia módulo n_i . 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.

A existencia pódese establecer mediante unha construción explícita de x.^[14] 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.

Queremos solucionar o sistema:

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

onde ${\displaystyle n_{1}}$ e ${\displaystyle n_{2}}$ son coprimos.

Pola identidade de Bézout sabemos da existencia de dous números enteiros ${\displaystyle m_{1}}$ e ${\displaystyle m_{2}}$ tal que

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

Os enteiros ${\displaystyle m_{1}}$ e ${\displaystyle m_{2}}$ pódense calcular mediante o algoritmo euclidiano estendido.

Unha solución vén dada por

${\displaystyle x_{0}=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}$

Comprobamos,

${\displaystyle {\begin{aligned}x_{0}&=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}}}$

iso implica que ${\displaystyle x_{0}\equiv a_{1}{\pmod {n_{1}}}.}$ A segunda congruencia próbase de xeito similar, trocando os subíndices 1 e 2.

O conxunto total de solucións será logo ${\displaystyle x=x_{0}+n_{1}n_{2}k}$ para k enteiro.

Considere unha secuencia de ecuacións de congruencia:

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

imos ver unha proba por construción e un exemplo por un método moi rápido

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

Sexa ${\displaystyle N_{i}=N/n_{i}}$ o produto de todos os módulos menos un. Como os ${\displaystyle n_{i}}$ son coprimos por pares, ${\displaystyle N_{i}}$ e ${\displaystyle n_{i}}$ son coprimos. Aplícamos a identidade de Bézout, e existen números enteiros ${\displaystyle M_{i}}$ e ${\displaystyle m_{i}}$ tal que

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

Unha solución do sistema de congruencias é

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

De feito, como ${\displaystyle N_{j}}$ é múltiplo de ${\displaystyle n_{i}}$ para ${\displaystyle i\neq j,}$ temos

para cada ${\displaystyle i.}$

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.

${\displaystyle {\begin{aligned}x&\equiv 1{\pmod {17}}\\x&\equiv 1{\pmod {16}}\\\end{aligned}}}$

Aquí

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

${\displaystyle 1\cdot 17+(-1)16=1.}$

${\displaystyle x_{0}=1\cdot 1\cdot 17+1\cdot (-1)16=1.}$

${\displaystyle x=1+17\cdot 16\cdot k=1+272k}$

Por tanto, a primeira solución ${\displaystyle x>100=273.}$

Cando a identidade de Bézout non é evidente pódese calcular co algoritmo de Euclides estendido^[15].

b) 17 piratas reparten un botín de máis de 100 moedas e sobra 1. Despois morre 1 pirata, reparten e sobran 7.

${\displaystyle {\begin{aligned}x&\equiv 1{\pmod {17}}\\x&\equiv 7{\pmod {16}}\\\end{aligned}}}$

Aquí

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

${\displaystyle 1\cdot 17+(-1)16=1.}$

${\displaystyle x_{0}=1\cdot 7\cdot 17+1\cdot (-1)16=103.}$

${\displaystyle x=103+17\cdot 16\cdot k=103+272k}$

Por tanto, a primeira solución ${\displaystyle x>100=103.}$

Exemplo con catro congruencias,^[16]

${\displaystyle {\begin{aligned}x&\equiv 6{\pmod {11}}\\x&\equiv 13{\pmod {16}}\\x&\equiv 9{\pmod {21}}\\x&\equiv 19{\pmod {25}}\\\end{aligned}}}$

Solución: o módulo da solución completa debe ser ${\displaystyle 11\cdot 16\cdot 21\cdot 25=92500}$, por seren coprimos.

E comezamos os cálculos

${\displaystyle {\begin{aligned}z_{1}&=m/m_{1}=m_{2}m_{3}m_{4}=16\cdot 21\cdot 25=8400.\\z_{2}&=m/m_{2}=m_{1}m_{3}m_{4}=11\cdot 21\cdot 25=5775.\\z_{3}&=m/m_{3}=m_{1}m_{2}m_{4}=11\cdot 16\cdot 25=4400.\\z_{4}&=m/m_{4}=m_{1}m_{2}m_{3}=11\cdot 16\cdot 21=3696.\\\end{aligned}}}$

${\displaystyle {\begin{aligned}y_{1}&=z_{1}^{-1}{\pmod {11}}=7^{-1}{\pmod {11}}=8{\pmod {11}}.\\y_{2}&=z_{2}^{-1}{\pmod {16}}=15^{-1}{\pmod {16}}=15{\pmod {16}}.\\y_{3}&=z_{3}^{-1}{\pmod {21}}=11^{-1}{\pmod {21}}=2{\pmod {21}}.\\y_{4}&=z_{4}^{-1}{\pmod {25}}=21^{-1}{\pmod {25}}=6{\pmod {25}}.\\\end{aligned}}}$

${\displaystyle {\begin{aligned}w_{1}&=y_{1}z_{1}{\pmod {92400}}=67200{\pmod {92400}}.\\w_{2}&=y_{2}z_{2}{\pmod {92400}}=86625{\pmod {92400}}.\\w_{3}&=y_{3}z_{3}{\pmod {92400}}=8800{\pmod {92400}}.\\w_{4}&=y_{4}z_{4}{\pmod {92400}}=22176{\pmod {92400}}.\\\end{aligned}}}$

${\displaystyle x=a_{1}w_{1}+a_{2}w_{2}+a_{3}w_{3}+a_{4}w_{4}{\pmod {92400}}}$. ${\displaystyle x=2029869{\pmod {92400}}=89469{\pmod {92400}}}$.

O sistema de congruencias resolvido polo teorema chinés do resto pódese reescribir como un sistema de ecuacións diofantianas lineares:

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

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.

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 R: abonda con substituír "enteiro" por "elemento do dominio" e ${\displaystyle \mathbb {Z} }$ por R. 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.

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 ${\displaystyle R=K[X]}$ para un corpo ${\displaystyle K.}$ 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 ${\displaystyle P_{i}(X)}$ (os módulos), para ${\displaystyle i=1,\dots ,k}$, polinomios coprimos por pares en ${\displaystyle R=K[X]}$ . Sexa ${\displaystyle d_{i}=\deg P_{i}}$ o grao de ${\displaystyle P_{i}(X)}$, e ${\displaystyle D}$ a suma dos ${\displaystyle d_{i}.}$ Se ${\displaystyle A_{i}(X),\ldots ,A_{k}(X)}$ son polinomios tales que ${\displaystyle A_{i}(X)=0}$ ou ${\displaystyle \deg A_{i}<d_{i}}$ para cada i, daquela, hai un e só un polinomio ${\displaystyle P(X)}$, tal que ${\displaystyle \deg P<D}$ e o resto da división euclidiana de ${\displaystyle P(X)}$ por ${\displaystyle P_{i}(X)}$ é ${\displaystyle A_{i}(X)}$ por cada i.

Polo tanto, agora queremos atopar un polinomio ${\displaystyle P(X)}$, que satisfai as congruencias

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

para ${\displaystyle i=1,\ldots ,k.}$

Considere os polinomios

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

A descomposición en fraccións parciais de ${\displaystyle 1/Q(X)}$ dá k polinomios ${\displaystyle S_{i}(X)}$ de grao ${\displaystyle \deg S_{i}(X)<d_{i},}$ tal que

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

e así

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

Por tanto unha solución do sistema de congruencias simultáneas vén dada polo polinomio

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

De feito, 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 1\leq i\leq k.}$

A solución pode ter un grao superior a ${\displaystyle D=\sum _{i=1}^{k}d_{i}.}$ Podemos deducir a única solución de grao menor que ${\displaystyle D}$ se consideramos o resto ${\displaystyle B_{i}(X)}$ da división euclidiana de ${\displaystyle A_{i}(X)S_{i}(X)}$ por ${\displaystyle P_{i}(X).}$ Esta solución é

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

Un caso especial para polinomios é a interpolación de Lagrange. Para isto, considere k polinomios mónicos de grao un:

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

Son coprimos por pares se os ${\displaystyle x_{i}}$ son todos diferentes. O resto da división por ${\displaystyle P_{i}(X)}$ dun polinomio ${\displaystyle P(X)}$ é ${\displaystyle P(x_{i})}$, polo teorema do resto.

Agora, sexan ${\displaystyle A_{1},\ldots ,A_{k}}$ constantes (polinomios de grao 0) en ${\displaystyle K.}$ Tanto a interpolación de Lagrange como o teorema chinés do resto afirman a existencia dun polinomio único ${\displaystyle P(X),}$ de grao inferior a ${\displaystyle k}$ tal que

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

para cada ${\displaystyle i.}$

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

${\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 descomposición parcial da fracción ${\displaystyle {\frac {1}{Q(X)}}}$ é

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

Agora, se reducimos o lado dereito a un denominador común obtemos

${\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 1, xa que é un polinomio de grao menor que ${\displaystyle k,}$ que toma o valor 1 para ${\displaystyle k}$ diferentes valores de ${\displaystyle X.}$ Desta fórmula, podemos obter a fórmula de interpolación de Lagrange:

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

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 ${\displaystyle x_{1},\ldots ,x_{k}}$, ${\displaystyle k}$ elementos do corpo ${\displaystyle K,}$ e, para ${\displaystyle i=1,\ldots ,k,}$ sexan ${\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}}$ os valores das primeiras derivadas ${\displaystyle r_{i}}$ en ${\displaystyle x_{i}}$ do polinomio buscado (incluída a derivada 0, que é o valor do propio polinomio). O problema consiste en atopar un polinomio ${\displaystyle P(X)}$ tal que a súa derivada j -ésima tome o valor ${\displaystyle a_{i,j}}$ en ${\displaystyle x_{i},}$ para ${\displaystyle i=1,\ldots ,k}$ e ${\displaystyle j=0,\ldots ,r_{j}.}$

Considere o polinomio

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

Este é o polinomio de Taylor de orde ${\displaystyle r_{i}-1}$ en ${\displaystyle x_{i}}$ do polinomio descoñecido ${\displaystyle P(X).}$ Polo tanto, debemos ter

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

Pola contra, calquera polinomio ${\displaystyle P(X)}$ que satisfai estas ${\displaystyle k}$ congruencias, en particular verifica, para calquera ${\displaystyle i=1,\ldots ,k}$

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

polo tanto ${\displaystyle P_{i}(X)}$ é o seu polinomio de Taylor de orde ${\displaystyle r_{i}-1}$ en ${\displaystyle x_{i}}$, e con iso temos que ${\displaystyle P(X)}$ 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 ${\displaystyle r_{i},}$ que satisfai estas ${\displaystyle k}$ congruencias.

O teorema chinés do resto pódese xeneralizar a módulos non coprimos. Sexa ${\displaystyle m,n,a,b}$ ser calquera número enteiro, deixe ${\displaystyle g=\gcd(m,n)}$ ; ${\displaystyle M=\operatorname {lcm} (m,n)}$, e considere o sistema de congruencias:

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

Se ${\displaystyle a\equiv b{\pmod {g}}}$, entón este sistema ten unha solución única módulo ${\displaystyle M=mn/g}$. En caso contrario, non ten solucións.

Se usamos a identidade de Bézout para escribir ${\displaystyle g=um+vn}$, daquela a solución vén dada por

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

Isto define un número enteiro, xa que g divide tanto m como n. A demostración é moi semellante á dos módulos coprimos. ^[17]

O teorema chinés do resto pódese xeneralizar a calquera anel, usando ideais coprimos (tamén chamados ideais comaximais). Dous ideais I e J son coprimos se hai elementos ${\displaystyle i\in I}$ e ${\displaystyle j\in J}$ tal que ${\displaystyle i+j=1.}$ Esta relación xoga o papel da identidade de Bézout nas probas relacionadas con esta xeralización, que polo demais son moi semellantes. A xeneralización pódese expresar do seguinte xeito. ^{[18] [19]}

Sexan I₁, ..., I_k ideais bilaterais dun anel ${\displaystyle R}$ e sexa I a súa intersección. Se os ideais son coprimos por 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 cociente ${\displaystyle R/I}$ e o produto directo de ${\displaystyle R/I_{i},}$ onde " ${\displaystyle x{\bmod {I}}}$ " denota a imaxe do elemento ${\displaystyle x}$ no anel cociente definido polo ideal ${\displaystyle I.}$ Alén diso, se ${\displaystyle R}$ é conmutativo, daquela, o ideal intersección dos ideais coprimos par pares é igual ao seu produto; é dicir

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

se ${\displaystyle I_{i}}$ e ${\displaystyle I_{j}}$ son coprimos para todo i ≠ j.

Sexan ${\displaystyle I_{1},I_{2},\dots ,I_{k}}$ ideais bilaterais coprimos por pares con ${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$ e sexa

${\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}$

o isomorfismo definido anteriormente. Sexa ${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$ o elemento de ${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$ cuxos compoñentes son todos 0 agás o elemento i-ésimo que é 1 e ${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

Os ${\displaystyle e_{i}}$ son idempotentes centrais que son ortogonais por pares; isto significa, en particular, que ${\displaystyle e_{i}^{2}=e_{i}}$ e ${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$ para cada i e j . Máis aínda, un ten ${\textstyle e_{1}+\cdots +e_{n}=1,}$ e ${\displaystyle I_{i}=R(1-e_{i}).}$

En resumo, esta xeneralización do teorema chinés do resto é a equivalencia entre ideais bilaterais coprimos por pares con intersección cero e idempotentes centrais e ortogonais por pares que suman 1.^[20]

O teorema chinés do resto utilizouse para construír unha numeración de Gödel para as secuencias, que forma parte da demostración dos teoremas de incompletitude de Gödel.

O algoritmo FFT de factor primo usa o teorema chinés do resto para reducir o cálculo dunha transformada de Fourier rápida de tamaño ${\displaystyle n_{1}n_{2}}$ ao cálculo de dúas transformadas rápidas de Fourier de tamaños menores ${\displaystyle n_{1}}$ e ${\displaystyle n_{2}}$ (coa condición de ${\displaystyle n_{1}}$ e ${\displaystyle n_{2}}$ seren coprimos).

Na sinatura de certificados HTTPS e durante o descifrado utilízase habitualmete o algoritmo RSA que usa o teorema chinés do resto.

As técnicas de resolución de ambigüidade de rango utilizadas co radar de frecuencia de repetición de pulso medio poden verse como un caso especial do teorema chinés do resto.

Dada unha función sobrexectiva ${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m}$ de grupos abelianos finitos, podemos usar o teorema chinés do resto para dar unha descrición completa de calquera mapa deste tipo. En 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_{j}}\end{aligned}}}$

onde ${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}}$. Alén diso, para calquera mapa inducido

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

da sobrexección orixinal, temos ${\displaystyle a_{k}\geq b_{l}}$ e ${\displaystyle p_{n_{k}}=p_{m_{l}},}$ xa que para un par de primos ${\displaystyle p,q}$, as únicas sobrexeccións diferentes de cero

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

poden definirse se ${\displaystyle p=q}$ e ${\displaystyle a\geq b}$.

Estas observacións son fundamentais para construír o anel de enteiros profinitos, que se dá como o límite inverso de todos estes mapas.

Teorema de Dedekind sobre a independencia linear dos caracteres. Sexa M un monoide e k un dominio integral, visto como un monoide considerando a multiplicación en k. Daquela calquera familia finita (f_i)_i∈I de distintos homomorfismos monoides f_i: M → k é linearmente independente. Noutras palabras, toda familia (α_i)_i∈I de elementos α_i ∈ k que satisfai

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$

debe ser igual á familia (0)_i∈I .

Proba. Primeiro supoña que k é un corpo, se non, substitúa o dominio integral k polo seu corpo cociente, e nada mudará. Podemos estender linearmente os homomorfismos monoides f_i : M → k a homomorfismos de k-álxebra (álxebra de corpo k) F_i : k[M] → k, onde k[M] é o anel monoide de M sobre k. Así, por linearidade, a condición

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}$

produce

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

Proseguimos, para i, j ∈ I; i ≠ j os dous mapas k -lineais F_i : k[M] → k e F_j : k[M] → k non son proporcionais entre si. En caso contrario f_i e f_j tamén serían proporcionais e, polo tanto, iguais xa que como homomorfismos monoides satisfán: f_i (1) = 1 =  f_j (1), o que contradí a suposición de que son distintos.

Polo tanto, os kernels Ker F_i e Ker F_j son distintos. Xa que k[M]/Ker F_i ≅ F_i (k[M]) = k é un corpo, Ker F_i é un ideal máximo de k[M] para cada i en I . Como os ideais Ker F_i e Ker F_j son distintos e máximos tamén son coprimos sempre que i ≠ j. O teorema chinés do resto (para aneis en xeral) produce un isomorfismo:

${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

onde

${\displaystyle K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.}$

En consecuencia, o mapa

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

é sobrexectivo. Baixo os isomorfismos k[M]/Ker F_i → F_i (k[M]) = k, o mapa Φ corresponde a:

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

Agora,

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}$

produce

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

para cada vector (u_i)_i∈I na imaxe do mapa ψ. Dado que ψ é sobrexectivo, isto significa que

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

para cada vector

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

En consecuencia, (α_i)_i∈I = (0)_i∈I. QED.

• Bourbaki, N. (1989). Algebra I. Springer. ISBN 3-540-64243-9. 
• Dauben, Joseph W. (2007). "Chapter 3: Chinese Mathematics". En Katz, Victor J. The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook. Princeton University Press. pp. 187–384. ISBN 978-0-691-11485-9. 
• Dence, Joseph B.; Dence, Thomas P. (1999). Elements of the Theory of Numbers. Academic Press. ISBN 9780122091308. 
• Duchet, Pierre (1995). "Hypergraphs". En Graham, R. L.; Grötschel, M.; Lovász, L. Handbook of combinatorics, Vol. 1, 2. Amsterdam: Elsevier. pp. 381–432. MR 1373663. . See in particular Section 2.5, "Helly Property", pp. 393–394.
• Gauss, Carl Friedrich (1986). Disquisitiones Arithemeticae. Traducido por Clarke, Arthur A. (Second, corrected ed.). New York: Springer. ISBN 978-0-387-96254-2. 
• Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (2nd ed.). Springer-Verlag. ISBN 0-387-97329-X. 
• Kak, Subhash (1986). Computational aspects of the Aryabhata algorithm (PDF). Indian Journal of History of Science 21. pp. 62–71. 
• Katz, Victor J. (1998). A History of Mathematics / An Introduction (2nd ed.). Addison Wesley Longman. ISBN 978-0-321-01618-8. 
• Libbrecht, Ulrich (1973). Chinese Mathematics in the Thirteenth Century: the "Shu-shu Chiu-chang" of Ch'in Chiu-shao. Dover Publications Inc. ISBN 978-0-486-44619-6. 
• Ore, Øystein (1952). The general Chinese remainder theorem. The American Mathematical Monthly 59. pp. 365–370. MR 48481. doi:10.2307/2306804. 
• Ore, Oystein (1988) [1948]. Number Theory and Its History. Dover. ISBN 978-0-486-65620-5. 
• Pisano, Leonardo (2002). Fibonacci's Liber Abaci. Traducido por Sigler, Laurence E. Springer-Verlag. pp. 402–403. ISBN 0-387-95419-8. 
• Rosen, Kenneth H. (1993). Elementary Number Theory and its Applications (3rd ed.). Addison-Wesley. ISBN 978-0201-57889-8. 
• Sengupta, Ambar N. (2012). Representing Finite Groups, A Semisimple Introduction. Springer. ISBN 978-1-4614-1232-8. 
• University of Illinois Chicago. The Chinese Remainder Theorem (PDF). 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. . See Section 31.5: The Chinese remainder theorem, pp. 873–876.
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996). Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography. World Scientific Publishing. pp. 1–213. ISBN 981-02-2827-9. 
• Hungerford, Thomas W. (1974). Algebra. Graduate Texts in Mathematics, Vol. 73. Springer-Verlag. pp. 131–132. ISBN 978-1-4612-6101-8. 
• Knuth, Donald (1997). The Art of Computer Programming. 2: Seminumerical Algorithms (Third ed.). Addison-Wesley. ISBN 0-201-89684-2. . See Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).

• Cobertura
• Principio de Hasse

• Calculadora online dun sistema de congruencias
• Calculadora online do algoritmo de Euclides estendido
• Texto completo de Sun-tzu Suan-ching (Chinés)