Teorema del resto chino

Teorema para resolver congruencias simultáneas

Formulación original de Sunzi: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) con la solución x = 23 + 105 k , con k un número entero

En matemáticas , el teorema del resto chino establece que si se conocen los restos de la división euclidiana de un entero n por varios enteros, entonces se puede determinar de forma única el resto de la división de n por el producto de estos enteros, bajo la condición de que los divisores sean coprimos por pares (ningún par de divisores comparte un factor común distinto de 1).

Por ejemplo, si sabemos que el resto de n dividido por 3 es 2, el resto de n dividido por 5 es 3 y el resto de n dividido por 7 es 2, entonces, sin ninguna otra información, podemos determinar que el resto de n dividido por 105 (el producto de 3, 5 y 7) es 23. Es importante destacar que esto nos dice que si n es un número natural menor que 105, entonces 23 es el único valor posible de n .

También se conoce como teorema de Sunzi , ya que la declaración más antigua conocida es la del matemático chino Sunzi en el Sunzi Suanjing del siglo III al V d.C.

El teorema del resto chino se utiliza ampliamente para realizar cálculos con números enteros grandes, ya que permite reemplazar un cálculo para el cual se conoce un límite en el tamaño del resultado por varios cálculos similares con números enteros pequeños.

El teorema del resto chino (expresado en términos de congruencias ) es válido para todos los dominios ideales principales . Se ha generalizado a cualquier anillo , con una formulación que implica ideales bilaterales .

Historia

La primera formulación conocida del problema aparece en el libro del siglo V Sunzi Suanjing del matemático chino Sunzi: ^[1]

Hay cosas cuyo número es desconocido. Si las contamos de tres en tres, nos sobran dos; de cinco en cinco, nos sobran tres; y de siete en siete, nos sobran dos. ¿Cuántas cosas hay? ^[2]

El trabajo de Sunzi no sería considerado un teorema según los estándares modernos; solo da un problema particular, sin mostrar cómo resolverlo, mucho menos alguna prueba sobre el caso general o un algoritmo general para resolverlo. ^[3] Lo que equivale a un algoritmo para resolver este problema fue descrito por Aryabhata (siglo VI). ^[4] Los casos especiales del teorema del resto chino también eran conocidos por Brahmagupta (siglo VII) y aparecen en el Liber Abaci de Fibonacci (1202). ^[5] El resultado se generalizó más tarde con una solución completa llamada Da-yan-shu (大衍術) en el Tratado matemático en nueve secciones de Qin Jiushao de 1247 ^[6] que fue traducido al inglés a principios del siglo XIX por el misionero británico Alexander Wylie . ^[7]

El teorema del resto chino aparece en el libro de Gauss de 1801, Disquisitiones Arithmeticae . ^[8]

El concepto de congruencias fue introducido y utilizado por primera vez por Carl Friedrich Gauss en sus Disquisitiones Arithmeticae de 1801. ^[9] Gauss ilustra el teorema del resto chino en un problema que involucra calendarios, a saber, "encontrar los años que tienen un cierto número de período con respecto al ciclo solar y lunar y la indicción romana". ^[10] Gauss introduce un procedimiento para resolver el problema que ya había sido utilizado por Leonhard Euler pero que, de hecho, era un método antiguo que había aparecido varias veces. ^[11]

Declaración

Sean n ₁ , ..., n _k números enteros mayores que 1, que suelen llamarse módulos o divisores . Denotemos por N el producto de los n _i .

El teorema del resto chino afirma que si los n _i son coprimos por pares , y si a ₁ , ..., a _k son números enteros tales que 0 ≤ a _i < n _i para cada i , entonces hay un y sólo un número entero x , tal que 0 ≤ x < N y el resto de la división euclidiana de x por n _i es a _i para cada i .

Esto puede reformularse de la siguiente manera en términos de congruencias : si son coprimos por pares, y si a ₁ , ..., a _k son números enteros cualesquiera, entonces el sistema ${\displaystyle n_{i}}$

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

tiene una solución, y dos soluciones cualesquiera, digamos x ₁ y x ₂ , son congruentes módulo N , es decir, x ₁ ≡ x ₂ (mod N  ) . ^[12]

En álgebra abstracta , el teorema a menudo se reformula como: si los n _i son coprimos por pares, la función

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

define un isomorfismo de anillo ^[13]

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

entre el anillo de números enteros módulo N y el producto directo de los anillos de números enteros módulo n _i . Esto significa que para hacer una secuencia de operaciones aritméticas en una se puede hacer el mismo cálculo independientemente en cada una y luego obtener el resultado aplicando el isomorfismo (de derecha a izquierda). Esto puede ser mucho más rápido que el cálculo directo si N y el número de operaciones son grandes. Esto se usa ampliamente, bajo el nombre de cálculo multimodular , para el álgebra lineal sobre los números enteros o los números racionales . ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$

El teorema también puede reformularse en el lenguaje de la combinatoria como el hecho de que las progresiones aritméticas infinitas de números enteros forman una familia Helly . ^[14]

Prueba

La existencia y la unicidad de la solución pueden demostrarse independientemente. Sin embargo, la primera prueba de existencia, que se da a continuación, utiliza esta unicidad.

Unicidad

Supóngase que x e y son ambas soluciones de todas las congruencias. Como x e y dan el mismo resto, cuando se dividen por n _i , su diferencia x − y es un múltiplo de cada n _i . Como los n _i son coprimos por pares, su producto N también divide a x − y , y por lo tanto x e y son congruentes módulo N . Si se supone que x e y son no negativos y menores que N (como en el primer enunciado del teorema), entonces su diferencia puede ser un múltiplo de N solo si x = y .

Existencia (primera prueba)

El mapa

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

asigna clases de congruencia módulo N a sucesiones de clases de congruencia módulo n _i . La prueba de unicidad muestra que esta función es inyectiva . Como el dominio y el codominio de esta función tienen el mismo número de elementos, la función también es sobreyectiva , lo que prueba la existencia de la solución.

Esta prueba es muy sencilla, pero no proporciona ninguna manera directa de calcular una solución. Además, no se puede generalizar a otras situaciones en las que sí se puede aplicar la siguiente prueba.

Existencia (prueba constructiva)

La existencia puede establecerse mediante una construcción explícita de x . ^[15] Esta construcción puede dividirse en dos pasos: primero resolver el problema en el caso de dos módulos y luego extender esta solución al caso general por inducción sobre el número de módulos.

Caso de dos módulos

Queremos resolver el sistema:

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

donde y son coprimos . ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$

La identidad de Bézout afirma la existencia de dos números enteros y tales que ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$

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

Los números enteros y pueden calcularse mediante el algoritmo euclidiano extendido . ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$

Una solución la da

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

En efecto,

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

lo que implica que la segunda congruencia se demuestra de manera similar, intercambiando los subíndices 1 y 2. ${\displaystyle x\equiv a_{1}{\pmod {n_{1}}}.}$

Caso general

Consideremos una secuencia de ecuaciones de congruencia:

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

donde son coprimos por pares. Las dos primeras ecuaciones tienen una solución proporcionada por el método de la sección anterior. El conjunto de las soluciones de estas dos primeras ecuaciones es el conjunto de todas las soluciones de la ecuación ${\displaystyle n_{i}}$ ${\displaystyle a_{1,2}}$

${\displaystyle x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.}$

Como los otros son coprimos con esto, la solución del problema inicial de k ecuaciones se reduce a un problema similar con ecuaciones. Al iterar el proceso, se obtienen eventualmente las soluciones del problema inicial. ${\displaystyle n_{i}}$ ${\displaystyle n_{1}n_{2},}$ ${\displaystyle k-1}$

Existencia (construcción directa)

Para construir una solución no es necesario hacer una inducción sobre el número de módulos. Sin embargo, una construcción tan directa implica más cálculos con números grandes, lo que la hace menos eficiente y menos utilizada. No obstante, la interpolación de Lagrange es un caso especial de esta construcción, aplicada a polinomios en lugar de números enteros.

Sea el producto de todos los módulos excepto uno. Como los son coprimos entre sí, y son coprimos. Por lo tanto, se aplica la identidad de Bézout , y existen números enteros y tales que ${\displaystyle N_{i}=N/n_{i}}$ ${\displaystyle n_{i}}$ ${\displaystyle N_{i}}$ ${\displaystyle n_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle m_{i}}$

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

Una solución del sistema de congruencias es

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

De hecho, como es un múltiplo de para tenemos ${\displaystyle N_{j}}$ ${\displaystyle n_{i}}$ ${\displaystyle i\neq j,}$

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

Para cada uno ${\displaystyle i.}$

Cálculo

Consideremos un sistema de congruencias:

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

donde son coprimos por pares , y sean En esta sección se describen varios métodos para calcular la solución única para , tal que y estos métodos se aplican en el ejemplo ${\displaystyle n_{i}}$ ${\displaystyle N=n_{1}n_{2}\cdots n_{k}.}$ ${\displaystyle x}$ ${\displaystyle 0\leq x<N,}$

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

Se presentan varios métodos de cálculo. Los dos primeros son útiles para ejemplos pequeños, pero resultan muy ineficientes cuando el producto es grande. El tercero utiliza la prueba de existencia dada en el § Existencia (prueba constructiva). Es el más conveniente cuando el producto es grande o para cálculos informáticos. ${\displaystyle n_{1}\cdots n_{k}}$ ${\displaystyle n_{1}\cdots n_{k}}$

Búsqueda sistemática

Es fácil comprobar si un valor de x es una solución: basta con calcular el resto de la división euclidiana de x por cada n _i . Así, para hallar la solución, basta con comprobar sucesivamente los números enteros de 0 a N hasta hallar la solución.

Aunque es un método muy simple, es muy ineficiente. Para el ejemplo simple que se considera aquí, se deben comprobar 40 números enteros (incluido 0 ) para encontrar la solución, que es 39. Se trata de un algoritmo de tiempo exponencial , ya que el tamaño de la entrada es, hasta un factor constante, el número de dígitos de N y el número promedio de operaciones es del orden de N.

Por lo tanto, este método rara vez se utiliza, ni para el cálculo manuscrito ni en ordenadores.

Búsqueda por tamizado

Las dos soluciones más pequeñas, 23 y 128, de la formulación original del problema del teorema del resto chino se encontraron usando un tamiz.

La búsqueda de la solución puede hacerse mucho más rápida mediante el cribado. Para este método, suponemos, sin pérdida de generalidad, que (si no fuera el caso, bastaría con reemplazar cada uno por el resto de su división por ). Esto implica que la solución pertenece a la progresión aritmética ${\displaystyle 0\leq a_{i}<n_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle n_{i}}$

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

Al probar los valores de estos números módulo, se encuentra finalmente una solución de las dos primeras congruencias. Entonces, la solución pertenece a la progresión aritmética. ${\displaystyle n_{2},}$ ${\displaystyle x_{2}}$

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

Al probar los valores de estos números módulo y continuar hasta que se haya probado cada módulo, finalmente se obtiene la solución. ${\displaystyle n_{3},}$

Este método es más rápido si los módulos se han ordenado por valor decreciente, es decir, si Para el ejemplo, esto da el siguiente cálculo. Consideramos primero los números que son congruentes con 4 módulo 5 (el módulo más grande), que son 4, 9 = 4 + 5 , 14 = 9 + 5 , ... Para cada uno de ellos, calculamos el resto por 4 (el segundo módulo más grande) hasta obtener un número congruente con 3 módulo 4. Luego, uno puede proceder sumando 20 = 5 × 4 en cada paso y calculando solo los restos por 3. Esto da ${\displaystyle n_{1}>n_{2}>\cdots >n_{k}.}$

4 mod 4 → 0. Continuar

4 + 5 = 9 mod 4 →1. Continuar

9 + 5 = 14 mod 4 → 2. Continuar

14 + 5 = 19 mod 4 → 3. Bien, continuamos considerando los residuos módulo 3 y sumando 5 × 4 = 20 cada vez.

19 mod 3 → 1. Continuar

19 + 20 = 39 mod 3 → 0. Bien, este es el resultado.

Este método funciona bien para cálculos escritos a mano con un producto de módulos que no es demasiado grande. Sin embargo, es mucho más lento que otros métodos para productos de módulos muy grandes. Aunque es considerablemente más rápido que la búsqueda sistemática, este método también tiene una complejidad temporal exponencial y, por lo tanto, no se utiliza en computadoras.

Utilizando la construcción de existencia

La prueba de existencia constructiva muestra que, en el caso de dos módulos, la solución puede obtenerse mediante el cálculo de los coeficientes de Bézout de los módulos, seguido de unas cuantas multiplicaciones, adiciones y reducciones módulo ${\displaystyle n_{1}n_{2}}$ (para obtener un resultado en el intervalo ). Como los coeficientes de Bézout pueden calcularse con el algoritmo euclidiano extendido , todo el cálculo, como máximo, tiene una complejidad temporal cuadrática de donde denota el número de dígitos de ${\displaystyle (0,n_{1}n_{2}-1)}$ ${\displaystyle O((s_{1}+s_{2})^{2}),}$ ${\displaystyle s_{i}}$ ${\displaystyle n_{i}.}$

Para más de dos módulos, el método para dos módulos permite reemplazar dos congruencias cualesquiera por una única congruencia módulo el producto de los módulos. La iteración de este proceso proporciona eventualmente la solución con una complejidad, que es cuadrática en el número de dígitos del producto de todos los módulos. Esta complejidad temporal cuadrática no depende del orden en el que se reagrupan los módulos. Se pueden reagrupar los dos primeros módulos, luego reagrupar el módulo resultante con el siguiente, y así sucesivamente. Esta estrategia es la más fácil de implementar, pero también requiere más cálculos que involucran números grandes.

Otra estrategia consiste en particionar los módulos en pares cuyo producto tenga tamaños comparables (en la medida de lo posible), aplicar, en paralelo, el método de dos módulos a cada par, e iterar con un número de módulos dividido aproximadamente por dos. Este método permite una fácil paralelización del algoritmo. Además, si se utilizan algoritmos rápidos (es decir, algoritmos que funcionan en tiempo cuasilineal ) para las operaciones básicas, este método proporciona un algoritmo para todo el cómputo que funciona en tiempo cuasilineal.

En el ejemplo actual (que tiene sólo tres módulos), ambas estrategias son idénticas y funcionan de la siguiente manera.

La identidad de Bézout para 3 y 4 es

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

Poniendo esto en la fórmula dada para probar la existencia da

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

para una solución de las dos primeras congruencias, las otras soluciones se obtienen sumando a −9 cualquier múltiplo de 3 × 4 = 12. Se puede continuar con cualquiera de estas soluciones, pero la solución 3 = −9 +12 es menor (en valor absoluto ) y, por lo tanto, conduce probablemente a un cálculo más fácil.

La identidad de Bézout para 5 y 3 × 4 = 12 es

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

Aplicando nuevamente la misma fórmula obtenemos una solución del problema:

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

Las otras soluciones se obtienen sumando cualquier múltiplo de 3 × 4 × 5 = 60 , y la solución positiva más pequeña es −21 + 60 = 39 .

Como un sistema diofántico lineal

El sistema de congruencias resuelto por el teorema del resto chino puede reescribirse como un sistema de ecuaciones diofánticas lineales :

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

donde los enteros desconocidos son y Por lo tanto, cada método general para resolver tales sistemas puede usarse para encontrar la solución del teorema del resto chino, como la reducción de la matriz del sistema a la forma normal de Smith o la forma normal de Hermite . Sin embargo, como es habitual cuando se usa un algoritmo general para un problema más específico, este enfoque es menos eficiente que el método de la sección anterior, basado en un uso directo de la identidad de Bézout . ${\displaystyle x}$ ${\displaystyle x_{i}.}$

Sobre dominios ideales principales

En § Enunciado, el teorema del resto chino ha sido enunciado de tres maneras diferentes: en términos de restos, de congruencias y de un isomorfismo de anillo . El enunciado en términos de restos no se aplica, en general, a dominios ideales principales , ya que los restos no están definidos en tales anillos . Sin embargo, las otras dos versiones tienen sentido sobre un dominio ideal principal R : basta con reemplazar "entero" por "elemento del dominio" y por R. Estas dos versiones del teorema son verdaderas en este contexto, porque las demostraciones (excepto la primera demostración de existencia), se basan en el lema de Euclides y la identidad de Bézout , que son verdaderas sobre todo dominio principal. ${\displaystyle \mathbb {Z} }$

Sin embargo, en general, el teorema es sólo un teorema de existencia y no proporciona ninguna forma de calcular la solución, a menos que se tenga un algoritmo para calcular los coeficientes de la identidad de Bézout.

Sobre anillos polinomiales univariados y dominios euclidianos

El enunciado en términos de residuos dado en § Enunciado del teorema no puede generalizarse a ningún dominio ideal principal, pero su generalización a dominios euclidianos es sencilla. Los polinomios univariados sobre un cuerpo son el ejemplo típico de un dominio euclidiano que no son los números enteros. Por lo tanto, enunciamos el teorema para el caso del anillo para un cuerpo. Para obtener el teorema para un dominio euclidiano general, basta con reemplazar el grado por la función euclidiana del dominio euclidiano. ${\displaystyle R=K[X]}$ ${\displaystyle K.}$

El teorema chino del resto para polinomios es, por tanto: Sean (los módulos), para , polinomios coprimos por pares en . Sea el grado de , y sea la suma de Si son polinomios tales que o para cada i , entonces, hay un y solo un polinomio , tal que y el resto de la división euclidiana de por es para cada i . ${\displaystyle P_{i}(X)}$ ${\displaystyle i=1,\dots ,k}$ ${\displaystyle R=K[X]}$ ${\displaystyle d_{i}=\deg P_{i}}$ ${\displaystyle P_{i}(X)}$ ${\displaystyle D}$ ${\displaystyle d_{i}.}$ ${\displaystyle A_{i}(X),\ldots ,A_{k}(X)}$ ${\displaystyle A_{i}(X)=0}$ ${\displaystyle \deg A_{i}<d_{i}}$ ${\displaystyle P(X)}$ ${\displaystyle \deg P<D}$ ${\displaystyle P(X)}$ ${\displaystyle P_{i}(X)}$ ${\displaystyle A_{i}(X)}$

La construcción de la solución puede realizarse como en § Existencia (prueba constructiva) o § Existencia (prueba directa). Sin embargo, la última construcción puede simplificarse utilizando, como sigue, la descomposición en fracciones parciales en lugar del algoritmo euclidiano extendido .

Por lo tanto, queremos encontrar un polinomio que satisfaga las congruencias ${\displaystyle P(X)}$

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

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

Consideremos los polinomios

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

La descomposición en fracciones parciales de da k polinomios con grados tales que ${\displaystyle 1/Q(X)}$ ${\displaystyle S_{i}(X)}$ ${\displaystyle \deg S_{i}(X)<d_{i},}$

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

y por lo tanto

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

Entonces una solución del sistema de congruencia simultánea viene dada por el polinomio

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

De hecho, tenemos

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

Esta solución puede tener un grado mayor que La única solución de grado menor que se puede deducir considerando el resto de la división euclidiana de por Esta solución es ${\displaystyle D=\sum _{i=1}^{k}d_{i}.}$ ${\displaystyle D}$ ${\displaystyle B_{i}(X)}$ ${\displaystyle A_{i}(X)S_{i}(X)}$ ${\displaystyle P_{i}(X).}$

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

Interpolación de Lagrange

Un caso especial del teorema del resto chino para polinomios es la interpolación de Lagrange . Para ello, considérense k polinomios mónicos de grado uno:

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

Son coprimos por pares si son todos diferentes. El resto de la división por de un polinomio es , según el teorema del resto del polinomio . ${\displaystyle x_{i}}$ ${\displaystyle P_{i}(X)}$ ${\displaystyle P(X)}$ ${\displaystyle P(x_{i})}$

Ahora, sean constantes (polinomios de grado 0) en Tanto la interpolación de Lagrange como el teorema del resto chino afirman la existencia de un único polinomio de grado menor que tal que ${\displaystyle A_{1},\ldots ,A_{k}}$ ${\displaystyle K.}$ ${\displaystyle P(X),}$ ${\displaystyle k}$

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

Para cada uno ${\displaystyle i.}$

La fórmula de interpolación de Lagrange es exactamente el resultado, en este caso, de la construcción de la solución anterior. Más precisamente, sea

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

La descomposición en fracciones parciales de es ${\displaystyle {\frac {1}{Q(X)}}}$

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

De hecho, al reducir el lado derecho a un denominador común se obtiene

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

y el numerador es igual a uno, por ser un polinomio de grado menor que el cual toma el valor uno para distintos valores de ${\displaystyle k,}$ ${\displaystyle k}$ ${\displaystyle X.}$

Utilizando la fórmula general anterior, obtenemos la fórmula de interpolación de Lagrange:

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

Interpolación de Hermite

La interpolación de Hermite es una aplicación del teorema del resto chino para polinomios univariados, que pueden involucrar módulos de grados arbitrarios (la interpolación de Lagrange involucra solo módulos de grado uno).

El problema consiste en encontrar un polinomio del menor grado posible, tal que el polinomio y sus primeras derivadas tomen valores dados en algunos puntos fijos.

Más precisamente, sean elementos del campo fundamental y, para sean los valores de las primeras derivadas del polinomio buscado en (incluida la derivada 0, que es el valor del propio polinomio). El problema es encontrar un polinomio tal que su derivada j  -ésima tome el valor en para y ${\displaystyle x_{1},\ldots ,x_{k}}$ ${\displaystyle k}$ ${\displaystyle K,}$ ${\displaystyle i=1,\ldots ,k,}$ ${\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}}$ ${\displaystyle r_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle P(X)}$ ${\displaystyle a_{i,j}}$ ${\displaystyle x_{i},}$ ${\displaystyle i=1,\ldots ,k}$ ${\displaystyle j=0,\ldots ,r_{j}.}$

Considere el polinomio

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

Este es el polinomio de Taylor de orden en , del polinomio desconocido Por lo tanto, debemos tener ${\displaystyle r_{i}-1}$ ${\displaystyle x_{i}}$ ${\displaystyle P(X).}$

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

Por el contrario , cualquier polinomio que satisfaga estas congruencias, en particular, verifica, para cualquier ${\displaystyle P(X)}$ ${\displaystyle k}$ ${\displaystyle i=1,\ldots ,k}$

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

por lo tanto, su polinomio de Taylor es de orden , es decir, resuelve el problema de interpolación de Hermite inicial. El teorema del resto chino afirma que existe exactamente un polinomio de grado menor que la suma de los que satisface estas congruencias. ${\displaystyle P_{i}(X)}$ ${\displaystyle r_{i}-1}$ ${\displaystyle x_{i}}$ ${\displaystyle P(X)}$ ${\displaystyle r_{i},}$ ${\displaystyle k}$

Existen varias formas de calcular la solución. Se puede utilizar el método descrito al principio de § Sobre anillos polinómicos univariados y dominios euclidianos. También se pueden utilizar las construcciones dadas en § Existencia (prueba constructiva) o § Existencia (prueba directa). ${\displaystyle P(X).}$

Generalización a módulos no coprimos

El teorema del resto chino se puede generalizar a módulos no coprimos. Sea cualquier número entero, sea ; , y considere el sistema de congruencias: ${\displaystyle m,n,a,b}$ ${\displaystyle g=\gcd(m,n)}$ ${\displaystyle M=\operatorname {lcm} (m,n)}$

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

Si , entonces este sistema tiene una solución única módulo . En caso contrario, no tiene soluciones. ${\displaystyle a\equiv b{\pmod {g}}}$ ${\displaystyle M=mn/g}$

Si se utiliza la identidad de Bézout para escribir , entonces la solución viene dada por ${\displaystyle g=um+vn}$

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

Esto define un entero, ya que g divide tanto a m como a n . De lo contrario, la prueba es muy similar a la de los módulos coprimos. ^[16]

Generalización a anillos arbitrarios

El teorema del resto chino se puede generalizar a cualquier anillo , utilizando ideales coprimos (también llamados ideales comaximales ). Dos ideales I y J son coprimos si hay elementos y tales que Esta relación juega el papel de la identidad de Bézout en las demostraciones relacionadas con esta generalización, que por lo demás son muy similares. La generalización puede enunciarse de la siguiente manera. ^{[17] [18]} ${\displaystyle i\in I}$ ${\displaystyle j\in J}$ ${\displaystyle i+j=1.}$

Sean I ₁ , ..., I _k ideales bilaterales de un anillo y sea I su intersección . Si los ideales son coprimos por pares, tenemos el isomorfismo : ${\displaystyle R}$

${\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 el anillo cociente y el producto directo de donde " " denota la imagen del elemento en el anillo cociente definido por el ideal Además, si es conmutativo , entonces la intersección ideal de ideales coprimos por pares es igual a su producto ; es decir ${\displaystyle R/I}$ ${\displaystyle R/I_{i},}$ ${\displaystyle x{\bmod {I}}}$ ${\displaystyle x}$ ${\displaystyle I.}$ ${\displaystyle R}$

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

si I _i y I _j son coprimos para todo i ≠ j .

Interpretación en términos de idempotentes

Sean ideales bilaterales coprimos por pares con y ${\displaystyle I_{1},I_{2},\dots ,I_{k}}$ ${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$

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

Sea el isomorfismo definido anteriormente. Sea el elemento cuyos componentes son todos 0 excepto el i  ésimo que es 1 , y ${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$ ${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$ ${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

Son idempotentes centrales que son ortogonales entre sí ; esto significa, en particular, que y para cada i y j . Además, se tiene y ${\displaystyle e_{i}}$ ${\displaystyle e_{i}^{2}=e_{i}}$ ${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$ ${\textstyle e_{1}+\cdots +e_{n}=1,}$ ${\displaystyle I_{i}=R(1-e_{i}).}$

En resumen, este teorema de resto chino generalizado es la equivalencia entre dar ideales bilaterales coprimos por pares con una intersección cero y dar idempotentes centrales y ortogonales por pares que suman 1. [ ^19]

Aplicaciones

Numeración de secuencias

El teorema del resto chino se ha utilizado para construir una numeración de Gödel para secuencias , que participa en la prueba de los teoremas de incompletitud de Gödel .

Transformada rápida de Fourier

El algoritmo FFT de factores primos (también llamado algoritmo de Good-Thomas) utiliza el teorema del resto chino para reducir el cálculo de una transformada rápida de Fourier de tamaño al cálculo de dos transformadas rápidas de Fourier de tamaños más pequeños y (siempre que y sean coprimos). ${\displaystyle n_{1}n_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$

Encriptación

La mayoría de las implementaciones de RSA utilizan el teorema del resto chino durante la firma de certificados HTTPS y durante el descifrado.

El teorema del resto chino también puede emplearse en la compartición de secretos , que consiste en distribuir un conjunto de porciones entre un grupo de personas que, todas juntas (pero ninguna sola), pueden recuperar un cierto secreto del conjunto de porciones dado. Cada una de las porciones se representa en una congruencia, y la solución del sistema de congruencias utilizando el teorema del resto chino es el secreto a recuperar. La compartición de secretos utilizando el teorema del resto chino utiliza, junto con el teorema del resto chino, secuencias especiales de números enteros que garantizan la imposibilidad de recuperar el secreto de un conjunto de porciones con menos de una determinada cardinalidad .

Resolución de ambigüedad de rango

Las técnicas de resolución de ambigüedad de alcance utilizadas con radares de frecuencia de repetición de pulsos media pueden considerarse un caso especial del teorema del resto chino.

Descomposición de sobreyecciones de grupos abelianos finitos

Dada una sobreyección de grupos abelianos finitos , podemos utilizar el teorema del resto chino para dar una descripción completa de cualquier función de este tipo. En primer lugar, el teorema da isomorfismos ${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m}$

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

donde . Además, para cualquier mapa inducido ${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}}$

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

de la sobreyección original, tenemos y dado que para un par de primos , las únicas sobreyecciones distintas de cero ${\displaystyle a_{k}\geq b_{l}}$ ${\displaystyle p_{n_{k}}=p_{m_{l}},}$ ${\displaystyle p,q}$

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

se puede definir si y . ${\displaystyle p=q}$ ${\displaystyle a\geq b}$

Estas observaciones son fundamentales para construir el anillo de números enteros profinitos , que se da como un límite inverso de todos esos mapas.

Teorema de Dedekind

Teorema de Dedekind sobre la independencia lineal de los caracteres. Sea M un monoide y k un dominio integral , visto como un monoide considerando la multiplicación por k . Entonces, cualquier familia finita (  f _i  ) _{i ∈ I} de homomorfismos de monoides distintos f _i  : M → k es linealmente independiente . En otras palabras, cada familia ( α _i ) _{i ∈ I} de elementos α _i ∈ k que satisfacen  

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

debe ser igual a la familia (0) _{i ∈ I} .

Demostración. Supongamos primero que k es un cuerpo , de lo contrario, reemplacemos el dominio integral k por su cuerpo cociente , y nada cambiará. Podemos extender linealmente los homomorfismos monoides f _i  : M → k a los homomorfismos de k - álgebra F _i  : k [ M ] → k , donde k [ M ] es el anillo monoide de M sobre k . Entonces, por linealidad, la condición 

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

rendimientos

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

A continuación, para i , j ∈ I ; i ≠ j las dos funciones k -lineales F _i  : k [ M ] → k y F _j  : k [ M ] → k no son proporcionales entre sí. De lo contrario, f _i y f _j también serían proporcionales y, por lo tanto, iguales, ya que, como homomorfismos monoides, satisfacen: f _i  (1) = 1 =   f _j  (1) , lo que contradice la suposición de que son distintas.     

Por lo tanto, los núcleos Ker  F _i y Ker  F _j son distintos. Como k [ M ]/Ker  F _i ≅ F _i  ( k [ M ]) = k es un cuerpo, Ker F _i es un ideal maximal de k [ M ] para cada i en I . Como son distintos y maximalistas, los ideales Ker  F _i y Ker  F _j son coprimos siempre que i ≠ j . El teorema del resto chino (para anillos generales) 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}}}$

dónde

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

En consecuencia, el 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}}}$

es sobreyectiva. Bajo los isomorfismos k [ M ]/Ker  F _i → F _i  ( k [ M ]) = k , la función Φ 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}}}$

Ahora,

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

rendimientos

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

para cada vector ( u _i ) _{i ∈ I} en la imagen de la función ψ . Como ψ es sobreyectiva, esto 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.

Véase también

• Sistema de cobertura
• Principio de Hasse
• Sistema de numeración de residuos

Notas

1. Katz 1998, pág. 197
2. Dence y Dence 1999, pág. 156
3. Dauben 2007, pág. 302
4. Kak 1986
5. Pisano 2002, págs. 402-403
6. Dauben 2007, pág. 310
7. Librería 1973
8. Gauss 1986, artículos 32–36
9. Irlanda y Rosen 1990, pág. 36
10. Mineral 1988, pág. 247
11. Mineral 1988, pág. 245
12. Irlanda y Rosen 1990, pág. 34
13. Irlanda y Rosen 1990, pág. 35
14. Duchet 1995
15. Rosen 1993, pág. 136
16. Mineral 1952.
17. Irlanda y Rosen 1990, pág. 181
18. Sengupta 2012, pág. 313
19. Bourbaki, N. 1989, pág. 110

Referencias

• Dauben, Joseph W. (2007), "Capítulo 3: Matemáticas chinas", en Katz, Victor J. (ed.), Las matemáticas de Egipto, Mesopotamia, China, India e Islam: un libro de consulta , Princeton University Press, págs. 187–384, ISBN 978-0-691-11485-9
• Dence, Joseph B.; Dence, Thomas P. (1999), Elementos de la teoría de números, Academic Press, ISBN 9780122091308
• Duchet, Pierre (1995), "Hypergraphs", en Graham, RL; Grötschel, M .; Lovász, L. (eds.), Manual de combinatoria, vol. 1, 2 , Ámsterdam: Elsevier, págs. 381–432, SEÑOR  1373663. Véase en particular la Sección 2.5, "Helly Property", págs. 393-394.
• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae, traducido por Clarke, Arthur A. (segunda edición corregida), Nueva York: Springer , ISBN 978-0-387-96254-2
• Irlanda, Kenneth; Rosen, Michael (1990), Una introducción clásica a la teoría de números moderna (2.ª ed.), Springer-Verlag, ISBN 0-387-97329-X
• Kak, Subhash (1986), "Aspectos computacionales del algoritmo Aryabhata" (PDF) , Indian Journal of History of Science , 21 (1): 62–71
• Katz, Victor J. (1998), Una historia de las matemáticas / Una introducción (2.ª ed.), Addison Wesley Longman, ISBN 978-0-321-01618-8
• Libbrecht, Ulrich (1973), Matemáticas chinas en el siglo XIII: el "Shu-shu Chiu-chang" de Ch'in Chiu-shao , Dover Publications Inc, ISBN 978-0-486-44619-6
• Ore, Øystein (1952), "El teorema general del resto chino", The American Mathematical Monthly , 59 (6): 365–370, doi :10.2307/2306804, JSTOR  2306804, MR  0048481
• Ore, Oystein (1988) [1948], Teoría de números y su historia , Dover, ISBN 978-0-486-65620-5
• Pisano, Leonardo (2002), Liber Abaci de Fibonacci, traducido por Sigler, Laurence E., Springer-Verlag, págs. 402–403, ISBN 0-387-95419-8
• Rosen, Kenneth H. (1993), Teoría de números elementales y sus aplicaciones (3.ª ed.), Addison-Wesley, ISBN 978-0201-57889-8
• Sengupta, Ambar N. (2012), Representación de grupos finitos: una introducción semisimple , Springer, ISBN 978-1-4614-1232-8
• Bourbaki, N. (1989), Álgebra I, Springer, ISBN 3-540-64243-9

Lectura adicional

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introducción a los algoritmos (Segunda ed.), MIT Press y McGraw-Hill, ISBN 0-262-03293-7. Véase la Sección 31.5: El teorema del resto chino, págs. 873–876.
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Teorema del resto chino: aplicaciones en informática, codificación y criptografía, World Scientific Publishing, págs. 1–213, ISBN 981-02-2827-9
• Hungerford, Thomas W. (1974), Álgebra, Textos de posgrado en matemáticas, vol. 73, Springer-Verlag, págs. 131-132, ISBN 978-1-4612-6101-8
• Knuth, Donald (1997), El arte de la programación informática , vol. 2: Algoritmos seminuméricos (tercera edición), Addison-Wesley, ISBN 0-201-89684-2. Véase la Sección 4.3.2 (págs. 286–291), ejercicio 4.6.2–3 (página 456).

Enlaces externos

• "Teorema del resto chino", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. , "Teorema del resto chino", MathWorld
• Teorema del resto chino en PlanetMath .
• Texto completo del Sun-tzu Suan-ching (chino) – Proyecto de texto chino
• Teorema del resto chino en ProofWiki