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 , siendo 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 número entero n entre varios números enteros, entonces se puede determinar de forma única el resto de la división de n por el producto de estos números enteros, bajo la condición de que el los divisores son coprimos por pares (no hay dos divisores que compartan 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 conocer el valor de 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 .

La declaración más antigua conocida del teorema es del matemático chino Sunzi en el Sunzi Suanjing entre los siglos III y V d.C.

El teorema del resto chino se usa ampliamente para calcular 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 chino del resto (expresado en términos de congruencias ) es cierto en todo dominio ideal principal . Se ha generalizado a cualquier anillo , con una formulación que involucra ideales bilaterales .

Historia

La declaración más antigua conocida del teorema, como un problema con números específicos, aparece en el libro del siglo V Sunzi Suanjing del matemático chino Sunzi: ^[1]

Hay ciertas cosas cuyo número se desconoce. Si los contamos de tres en tres, nos sobran dos; de cinco en cinco, nos sobran tres; y para los siete, sobran dos. ¿Cuántas cosas hay? ^[2]

El trabajo de Sunzi no contiene ni una prueba ni un algoritmo completo. ^[3] Aryabhata (siglo VI) describió lo que equivale a un algoritmo para resolver este problema . ^[4] Brahmagupta (siglo VII) también conocía casos especiales del teorema del resto chino 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]

La noción de congruencias fue introducida y utilizada 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 a la indicación romana." ^[10] Gauss introduce un procedimiento para resolver el problema que ya había sido utilizado por Leonhard Euler pero que en realidad 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 a menudo se denominan módulos o divisores . Denotemos por N el producto de n _i .

El teorema del resto chino afirma que si n _i son coprimos por pares , y si a ₁ , ..., ak _son números enteros tales que 0 ≤ a _i < n _i para cada i , entonces hay uno y sólo un 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 se puede reformular de la siguiente manera en términos de congruencias : si son coprimos por pares, y si a ₁ , ..., _ak 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, el mapa

${\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 uno se puede hacer el mismo cálculo de forma independiente 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 computación multimodular , para álgebra lineal sobre números enteros o racionales . ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$

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

Prueba

La existencia y unicidad de la solución pueden probarse de forma independiente. Sin embargo, la primera prueba de existencia, que se proporciona a continuación, utiliza esta unicidad.

Unicidad

Supongamos que xey son 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 no son negativos y son menores que N (como en el primer enunciado del teorema), entonces su diferencia puede ser un múltiplo de N sólo 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 secuencias de clases de congruencia módulo n _i . La prueba de unicidad muestra que este mapa es inyectivo . Como el dominio y el codominio de este mapa tienen el mismo número de elementos, el mapa también es sobreyectivo , lo que prueba la existencia de la solución.

Esta prueba es muy simple pero no proporciona ninguna forma 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 se puede dividir en dos pasos, primero resolviendo el problema en el caso de dos módulos y luego extendiendo esta solución al caso general mediante 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 viene dada por

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

implicando 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

Considere 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 solución proporcionada por el método del apartado 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, esto reduce la resolución del problema inicial de k ecuaciones a un problema similar con ecuaciones. Al iterar el proceso, finalmente se obtienen 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. Sin embargo, la interpolación de Lagrange es un caso especial de esta construcción, aplicada a polinomios en lugar de a números enteros.

Sea el producto de todos los módulos menos uno. Como son coprimos por pares y son coprimos. Por 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 ${\displaystyle i.}$

Cálculo

Considere 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 let En esta sección se describen varios métodos para calcular la solución única para , de modo 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 se vuelven muy ineficientes cuando el producto es grande. El tercero utiliza la prueba de existencia dada en § Existencia (prueba constructiva). Es más conveniente cuando el producto es grande o para cálculos por computadora. ${\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 encontrar la solución, basta con comprobar sucesivamente los números enteros del 0 al N hasta encontrar la solución.

Aunque es muy sencillo, este método es muy ineficaz. Para el ejemplo simple considerado aquí, se deben verificar 40 números enteros (incluido 0 ) para encontrar la solución, que es 39 . Este es 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 cálculos escritos a mano ni en computadoras.

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 encontradas usando un tamiz

La búsqueda de la solución puede acelerarse considerablemente mediante el tamizado. Para este método suponemos, sin pérdida de generalidad, que (si no fuera así, bastaría con sustituir 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 en módulo, finalmente se encuentra 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 }$

Probar los valores de estos números en módulo y continuar hasta que se haya probado cada módulo finalmente produce 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. Por ejemplo, esto proporciona el siguiente cálculo. Consideramos primero los números que son congruentes con 4 módulo 5 (el módulo mayor), que son 4, 9 = 4 + 5 , 14 = 9 + 5 , ... Para cada uno de ellos, calcula el resto por 4 (el segundo módulo más grande) hasta obtener un número congruente con 3 módulo 4. Luego se 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, continúa considerando los restos 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 mucho más rápido que la búsqueda sistemática, este método también tiene una complejidad temporal exponencial y, por tanto, no se utiliza en ordenadores.

Usando la construcción de existencia

La prueba de existencia constructiva muestra que, en el caso de dos módulos, la solución se puede obtener calculando los coeficientes de Bézout de los módulos, seguido de algunas multiplicaciones, sumas y reducciones de 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 la sustitución de dos congruencias cualesquiera por un único módulo de congruencia, 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 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 dividir los módulos en pares cuyos productos tengan tamaños comparables (en la medida de lo posible), aplicando, en paralelo, el método de dos módulos a cada par, e iterando con un número de módulos aproximadamente dividido 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álculo 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.}$

Poner 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 más pequeña (en valor absoluto ) y, por lo tanto, probablemente conduce 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 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 están los números enteros desconocidos y el Por lo tanto, todos los métodos generales para resolver tales sistemas pueden 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 utiliza 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 chino del resto se ha planteado de tres maneras diferentes: en términos de restos, de congruencias y de un isomorfismo de anillo . La afirmación en términos de restos no se aplica, en general, a dominios ideales principales , ya que los restos no están definidos en dichos anillos . Sin embargo , las otras dos versiones tienen sentido sobre un dominio ideal principal R : basta con sustituir "entero" por "elemento del dominio" y por R. Estas dos versiones del teorema son verdaderas en este contexto, porque las pruebas (excepto la primera prueba de existencia) se basan en el lema de Euclides y la identidad de Bézout , que son verdaderas en todos los dominios principales. ${\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 identidad de Bézout.

Sobre anillos polinomiales univariados y dominios euclidianos

El enunciado en términos de restos 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 campo 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 de un campo. Para obtener el teorema de 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 el siguiente: 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, existe uno y sólo 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 se puede realizar como en § Existencia (prueba constructiva) o § Existencia (prueba directa). Sin embargo, esta última construcción se puede simplificar utilizando, como sigue, la descomposición en fracciones parciales en lugar del algoritmo euclidiano extendido .

Por 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.}$

Considere 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 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 chino del resto para polinomios es la interpolación de Lagrange . Para esto, considere k polinomios mónicos de grado uno:

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

Son coprimos por pares si todos son 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, seamos constantes (polinomios de grado 0) en Tanto la interpolación de Lagrange como el teorema chino del resto afirman la existencia de un polinomio único 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 ${\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, dejemos

${\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 toma el valor uno para diferentes valores de ${\displaystyle k,}$ ${\displaystyle k}$ ${\displaystyle X.}$

Usando 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 unos puntos fijos.

Más precisamente, sean elementos del campo fundamental y, sean los valores de las primeras derivadas del polinomio buscado en (incluida la derivada 0, que es el valor del polinomio mismo). El problema es encontrar un polinomio tal que su j  -ésima derivada tome el valor en for 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 de orden es , es decir, resuelve el problema de interpolación inicial de Hermite. 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}$

Hay varias formas de calcular la solución. Se puede utilizar el método descrito al principio de § Sobre anillos polinomiales 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 un módulo de solución único . De lo 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 número entero, ya que g divide tanto a m como a n . Por lo demás, la demostración es muy similar a la de los módulos coprimos. ^[dieciséis]

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 identidad de Bézout en las pruebas relacionadas con esta generalización, que por lo demás son muy similares. La generalización puede formularse 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 ; eso es ${\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 por pares ; esto significa, en particular, que y para cada i y j . Además, uno 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 del resto chino generalizado es la equivalencia entre dar ideales bilaterales coprimos por pares con una intersección cero y dar idempotentes ortogonales centrales y por pares que suman 1 . ^[19]

Aplicaciones

Numeración secuencial

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

Transformada rápida de Fourier

El algoritmo FFT de factor primo (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}}$

Cifrado

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 chino del resto también se puede utilizar en el intercambio secreto , que consiste en distribuir un conjunto de acciones entre un grupo de personas que, todas juntas (pero ninguna sola), pueden recuperar un determinado secreto del conjunto de acciones dado. Cada una de las partes está representada en una congruencia, y la solución del sistema de congruencias utilizando el teorema chino del resto es el secreto a recuperar. El intercambio 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 acciones 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 medios pueden verse como 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 dicho mapa. 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}}}$

dónde . 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 desde para un par de números primos , las únicas sobreyección 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 estos mapas.

teorema de dedekind

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

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

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

Prueba. Primero suponga que k es un campo ; de lo contrario, reemplace el dominio integral k por su campo cociente y nada cambiará. Podemos extender linealmente los homomorfismos monoides f _i  : M → k a k - homomorfismos de á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 los dos k - mapas 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 tanto, iguales, ya que como homomorfismos monoides satisfacen: f _i  (1) = 1 =   f _j  (1) , lo que contradice la suposición de que son distintos.     

Por tanto, los núcleos Ker  F _i y Ker  F _j son distintos. Dado que k [ M ]/Ker  F _i ≅ F _i  ( k [ M ]) = k es un campo, Ker F _i es un ideal máximo de k [ M ] para cada i en I . Debido a que son distintos y maximales, los ideales Ker  F _i y Ker  F _j son coprimos siempre que i ≠ j . El teorema chino del resto (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 sobreyectivo. Bajo los isomorfismos k [ M ]/Ker  F _i → F _i  ( k [ M ]) = k , el 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}}}$

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 del mapa ψ . Dado que ψ es sobreyectivo, 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.

Ver también

• Sistema de cobertura
• principio de hasse
• Sistema de numeración de residuos

Notas

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

Referencias

• Dauben, Joseph W. (2007), "Chapter 3: Chinese Mathematics", en Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam: A Sourcebook , Princeton University Press, págs. 187–384, ISBN 978-0-691-11485-9
• Dence, José 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, "Propiedad de Helly", págs. 393–394.
• Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae, 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), Historia de las matemáticas / 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 : 365–370, doi : 10.2307/2306804, SEÑOR  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 elemental de números 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

Otras lecturas

• 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, 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 ed.), Addison-Wesley, ISBN 0-201-89684-2. Consulte 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