Teorema del resto chino

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Teorema para resolver congruencias simultáneas

La formulación original de Sun-tzu: x (mod 3) 3 (mod 5) 2 (mod 7) con la solución x = 23 + 105k, con k un entero

En matemáticas, el teorema del resto chino establece que si uno conoce los restos de la división euclidiana de un entero n por varios enteros, entonces uno puede determinar exclusivamente el resto el resto de la división de n por el producto de estos enteros, bajo la condición de que los divisores sean de coprime por pares (no hay dos divisores que compartan un factor común que no sea 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, luego 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. Lo importante, esto nos dice que si n es un número natural inferior a 105, entonces 23 es el único valor posible de n .

La declaración más temprana conocida del teorema es por el matemático chino Sun-tzu en el Sun-tzu Suan-Ching en el siglo III CE.

El teorema del resto chino se usa ampliamente para calcular con 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 en enteros pequeños.

El teorema del resto chino (expresado en términos de congruencias) es cierto sobre cada dominio ideal principal. Se ha generalizado a cualquier anillo, con una formulación que involucra ideales de dos lados.

Historia

La declaración más temprana conocida del teorema, como un problema con números específicos, aparece en el libro del siglo IV Sun-tzu Suan-Ching por el matemático chino Sun-tzu:

Hay ciertas cosas cuyo número es desconocido. Si los contamos por tres, nos quedan dos; a las cinco nos quedan tres; y a las siete nos quedan dos. ¿Cuántas cosas hay?

El trabajo de Sun-Tzu no contiene una prueba ni un algoritmo completo. Lo que equivale a un algoritmo para resolver este problema fue descrito por Aryabhata (siglo VI). Brahmagupta (siglo VII) conocía casos especiales del teorema del resto chino (siglo VII), y aparecen en Liber Abaci de Fibonacci (1202). El resultado se generalizó más tarde con una solución completa llamada da-yan-shu ( 大衍術 ) en CH ' en Chiu-Shao ' s 1247 Tratado matemático en nueve secciones ( 數書九章章 , shu-shu chiu-chang ) que fue traducido al inglés a principios del siglo XIX por el misionero británico Alexander Wylie.

El teorema del resto chino aparece en el libro de Gauss 1801 Disquisición Arithmeticae.

La noción de congruencias fue introducida por primera vez y utilizada por Carl Friedrich Gauss en sus descrices arithmeticae de 1801. Gauss ilustra el teorema del resto chino sobre un problema que involucra calendarios, a saber, " para 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. " Gauss presenta un procedimiento para resolver el problema que ya había sido utilizado por Leonhard Euler, pero de hecho era un método antiguo que había aparecido varias veces.

Declaración

Let n ₁,..., n _k be enteros mayor que 1, que a menudo se llaman moduli o divisores . Denotemos por n el producto del n _i.

El teorema del resto chino afirma que si los n _i son coprime por pares, y si a ₁,..., a _k son enteros tal que 0 ≤ a _i & lt; n _i por cada i , entonces hay un solo entero x , tal que 0 ≤ x & lt; n y el resto de la división euclidiana de x por n _i es a _i por cada i .

Esto puede ser reiniciado como sigue en términos de congruencias: Si $n_{i}$ son pares coprime, y si a₁,... a_k son cualquier entero, entonces el sistema

{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 cualquier dos soluciones, digamos x ₁ y x ₂, son modulo congruentes n , es decir, $x 1 \equiv x 2 (mod n)$ .

En álgebra abstracta, el teorema a menudo se reforma como: si los n _i son coprime por pares, el mapa

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

Define un isomorfismo de anillo

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

entre el anillo de enteros modulo N y el producto directo de los anillos de enteros modulo el n_i. Esto significa que por hacer una secuencia de operaciones aritméticas en ${displaystyle mathbb {Z} /Nmathbb {Z}}$ uno puede hacer el mismo cálculo independientemente en cada ${displaystyle mathbb {Z} /n_{i}mathbb {Z} }$ y luego obtener el resultado aplicando el isomorfismo (de la derecha a la 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 es ampliamente utilizado, bajo el nombre computación multimodular, para álgebra lineal sobre los enteros o los números racionales.

El teorema también se puede reformular en el lenguaje de la combinatoria como el hecho de que las progresiones aritméticas infinitas de los enteros forman una familia helly.

prueba

La existencia y la singularidad de la solución pueden probarse de forma independiente. Sin embargo, la primera prueba de existencia, dada a continuación, usa esta singularidad.

singularidad

Suponga que $x$ y $y$ son ambas soluciones a todas las congruencias. Como $x$ y $y$ Dé el mismo resto, cuando se divide con $n i$ , su diferencia $X - y$ es un múltiplo de cada $n i$ . Como $n i$ son coprime por pares, su producto $n </$ también divide $x - y$ y, por lo tanto, $x$ y $y$ son modulo congruentes $n$ . If $x$ y $y$ se supone que no son negativos y menos que $n$ (como en la primera declaración 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},ldotsx{bmod {n}}_{k})}$

maps clases de congruencia modulo $n$ a secuencias de clases de congruencia modulo $n i <<i <i <<i <i <i <i <<i <i i$ . La prueba de singularidad 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 sujectivo, lo que demuestra la existencia de la solución.

Esta prueba es muy simple pero no proporciona ninguna forma directa para calcular una solución. Además, no se puede generalizar a otras situaciones donde la siguiente prueba puede.

existencia (prueba constructiva)

La existencia puede establecerse mediante una construcción explícita de $x$ . 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 mediante la inducción en 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 $n_{1}$ y $n_{2}$ son coprime.

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

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

Los enteros $m_{1}$ y $m_{2}$ puede ser calculado por el algoritmo de Euclidean extendido.

una solución está dada por

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

de hecho,

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

implicando que ${displaystyle xequiv a_{1}{pmod {n_{1}}}.}$ La segunda congruencia se prueba de manera similar, intercambiando los subscriptos 1 y 2.

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 $n_{i}$ son pares coprime. Las dos primeras ecuaciones tienen una solución ${displaystyle a_{1,2}}$ proporcionado 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 xequiv a_{1,2}{pmod {n_{1}n_{2}}}.}$

Como el otro $n_{i}$ son coprime con ${displaystyle n_{1}n_{2},}$ esto reduce la solución del problema inicial $k$ ecuaciones a un problema similar con $k-1$ ecuaciones. Iterando el proceso, uno consigue eventualmente las soluciones del problema inicial.

existencia (construcción directa)

Para construir una solución, no es necesario hacer una inducción en el número de módulos. Sin embargo, dicha construcción directa implica más cálculo con grandes cantidades, lo que lo hace menos eficiente y menos utilizado. Sin embargo, Lagrange Interpolation es un caso especial de esta construcción, aplicado a polinomios en lugar de enteros.

Vamos ${displaystyle N_{i}=N/n_{i}}$ ser el producto de todos los moduli pero uno. Como $n_{i}$ son pares coprime, $N_{i}$ y $n_{i}$ son coprime. Así se aplica la identidad de Bézout, y existen enteros $M_{i}$ y $m_{i}$ tales que

${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 $N_{j}$ es un múltiple de $n_{i}$ para ${displaystyle ineq j,}$ tenemos

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

para todos $i.$

Computation

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 $n_{i}$ son pares coprime, y dejar ${displaystyle N=n_{1}n_{2}cdots n_{k}.}$ En esta sección se describen varios métodos para calcular la solución única $x$ , tal que $<math alttext="{displaystyle 0leq x0\leq \leq x.N,{displaystyle 0leq x interpretadoN,} <img alt="{displaystyle 0leq x$ y estos métodos se aplican en el ejemplo

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

búsqueda sistemática

Es fácil verificar si un valor de $x$ es una solución: es suficiente calcular el resto de la división euclidiana de $x$ por cada $n i$ . Por lo tanto, para encontrar la solución, es suficiente verificar sucesivamente los enteros de $0$ a $n <$ Hasta que encuentre la solución.

Aunque es muy simple, este método es muy ineficiente. Para el ejemplo simple considerado aquí, $40$ enteros (incluido $0$ ) deben verificarse 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 usa, ni para el cálculo escrito a mano ni en las computadoras.

Búsqueda por tamizado

Las dos soluciones más pequeñas, 23 y 128, de la formulación original del problema del teorema de los restos chinos encontrado con un sieve

La búsqueda de la solución se puede hacer dramáticamente más rápido silenciando. Para este método, suponemos, sin pérdida de generalidad, que $<math alttext="{displaystyle 0leq a_{i}0≤ ≤ ai.ni{displaystyle 0leq a_{i}cantado<img alt="{displaystyle 0leq a_{i}$ (si no fuera el caso, sería suficiente reemplazar cada uno $a_{i}$ por el resto de su división por $n_{i}$ ). Esto implica que la solución pertenece a la progresión aritmética

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

Probando los valores de estos números modulo ${displaystyle n_{2},}$ uno finalmente encuentra una solución $x_{2}$ de las dos primeras congruencias. Entonces la solución pertenece a la progresión aritmética

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

Pruebas de los valores de estos números modulo ${displaystyle n_{3},}$ , y continuando hasta que se haya probado cada módulo da finalmente la solución.

Este método es más rápido si se ha ordenado el moduli disminuyendo el valor, es decir, $n_{2}>cdots >n_{k}.}" xmlns="http://www.w3.org/1998/Math/MathML">n1■n2■⋯ ⋯ ■nk.{displaystyle No. - No.n_{2}>cdots >n_{k}.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba4dd6fff3697e044c65ec36913cc6ceb4715d53" style="vertical-align: -0.671ex; width:20.047ex; height:2.176ex;"/>$ Por ejemplo, esto da la siguiente computación. Consideramos primero los números congruentes a 4 modulo 5 (el módulo más grande), que son 4, 9 = 4 + 5, 14 = 9 + 5,... Para cada uno de ellos, computar el resto por 4 (el segundo módulo más grande) hasta conseguir un número congruente a 3 modulo 4. Entonces uno puede proceder añadiendo 20 = 5 × 4 en cada paso, y computar sólo los restos por 3. Esto da

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. OK, continuar considerando los restos modulo 3 y añadir 5 × 4 = 20 cada vez

19 mod 3 → 1. Continuar

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

Este método funciona bien para el cálculo escrito 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 muy grandes de módulos. Aunque dramáticamente más rápido que la búsqueda sistemática, este método también tiene una complejidad de tiempo exponencial y, por lo tanto, no se usa en las computadoras.

Uso de la construcción de existencia

La prueba de existencia constructiva muestra que, en el caso de dos módulos, la solución puede ser obtenida por la computación de los coeficientes de Bézout del moduli, seguido de algunas multiplicaciones, adiciones y Modulo de reducción $n_{1}n_{2}$ (para obtener un resultado en el intervalo ${displaystyle (0,n_{1}n_{2}-1)}$ ). A medida que los coeficientes de Bézout se pueden computar con el algoritmo extenso de Euclidean, toda la computación, en su mayoría, tiene una complejidad cuadrática del tiempo ${displaystyle O((s_{1}+s_{2})^{2}),}$ Donde $s_{i}$ denota el número de dígitos de ${displaystyle n_{i}.}$

Para más de dos módulos, el método para dos módulos permite el reemplazo de dos congruencias por un solo modulo de congruencia el producto de los módulos. Iterando 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 del tiempo cuadrático no depende del orden en que se reagrupen los módulos. Uno puede 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álculo que involucre grandes números.

Otra estrategia consiste en dividir los módulos en pares cuyo producto tiene tamaños comparables (tanto como sea posible), aplicando, en paralelo, el método de dos módulos a cada par, e iterando con una serie de módulos aproximadamente divididos 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 cuasilíneo) 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 solo 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 1times 4+(-1)times 3=1.}$

Poner esto en la fórmula dada para probar que la existencia da

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

Para una solución de las dos primeras congruencias, las otras soluciones se obtienen al agregar a −9 cualquier múltiplo de 3 × 4 = 12 . Uno 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, conduce probablemente a un cálculo más fácil

Bézout Identity para 5 y 3 × 4 = 12 es

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

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

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

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

Como un sistema diófantino lineal

El sistema de congruencias resuelto por el teorema del resto chino puede reescribirse como un sistema de ecuaciones diofantinas 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 $x$ y el $x_{i}.$ Por lo tanto, todo método general para resolver tales sistemas puede ser utilizado para encontrar la solución del teorema de restante chino, como la reducción de la matriz del sistema a la forma normal Smith o la forma normal Hermite. Sin embargo, como es habitual al utilizar 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.

sobre dominios ideales principales

En § Declaración, el teorema restante chino se ha declarado de tres maneras diferentes: en términos de restos, de congruencias, y de un isomorfismo anillo. La declaración en términos de restos no se aplica, en general, a los principales dominios ideales, ya que los restos no se definen en dichos anillos. Sin embargo, las otras dos versiones tienen sentido sobre un dominio ideal principal $R$ : basta reemplazar "integer" por "elemento del dominio" y $mathbb {Z}$ por $R$ . Estas dos versiones del teorema son verdaderas en este contexto, porque las pruebas (excepto la primera prueba de existencia), se basan en la lema de Euclid y la identidad de Bézout, que son verdaderas sobre cada dominio principal.

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

sobre anillos polinomiales univariados y dominios euclidianos

La declaración en cuanto a los restos dados en § Theorem no puede ser generalizada a ningún dominio ideal principal, pero su generalización a los dominios Euclidean es directa. Los polinomios univariados sobre un campo son el ejemplo típico de un dominio euclidiano que no son los enteros. Por lo tanto, declaramos el teorema para el caso del anillo ${displaystyle R=K[X]}$ para un campo $K.$ Para obtener el teorema para un dominio Euclideano general, basta reemplazar el grado por la función Euclideana del dominio Euclidean.

El teorema de los restos chinos para los polinomios es así: ${displaystyle P_{i}(X)}$ (el moduli) ser, ${displaystyle i=1,dotsk}$ , polinomios coprime pareados en ${displaystyle R=K[X]}$ . Vamos ${displaystyle d_{i}=deg P_{i}}$ ser el grado de ${displaystyle P_{i}(X)}$ , y $D$ ser la suma de la ${displaystyle d_{i}.}$ Si ${displaystyle A_{i}(X),ldotsA_{k}(X)}$ son polinomios tales que ${displaystyle A_{i}(X)=0}$ o $<math alttext="{displaystyle deg A_{i}deg⁡ ⁡ Ai.di{displaystyle deg A_{i}cantado_{i}<img alt="{displaystyle deg A_{i}$ para todos $i$ , entonces, hay uno y sólo un polinomio $P(X)$ , tal que $<math alttext="{displaystyle deg Pdeg P.D{displaystyle deg P interpretadoD} <img alt="{displaystyle deg P$ y el resto de la división de Euclides $P(X)$ por ${displaystyle P_{i}(X)}$ es ${displaystyle A_{i}(X)}$ para todos $i$ .

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, de la siguiente manera, descomposición de fracción parcial en lugar del algoritmo euclidiano extendido.

Así, queremos encontrar un polinomio $P(X)$ , que satisface las congruencias

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

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

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 parcial de la fracción ${displaystyle 1/Q(X)}$ da $k$ polinomios ${displaystyle S_{i}(X)}$ con grados $<math alttext="{displaystyle deg S_{i}(X)deg⁡ ⁡ Si()X).di,{displaystyle deg S_{i}(X)traducido_{i}<img alt="{displaystyle deg S_{i}(X)$ tales que

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

y así

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

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

${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 1leq ileq k.}$

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

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

Lagrange Interpolation

Un caso especial del teorema del resto chino para polinomios es la interpolación de Lagrange. Para esto, considere $k$ polinomios monic de grado uno:

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

Son pares coprime si $x_{i}$ son todos diferentes. El resto de la división por ${displaystyle P_{i}(X)}$ de un polinomio $P(X)$ es $P(x_i).$

Ahora, vamos. $A_{1},ldotsA_{k}$ ser constantes (polinomios de grado 0) in $K.$ Tanto la interpolación de Lagrange como el teorema del resto chino afirman la existencia de un polinomio único ${displaystyle P(X),}$ de grado inferior a $k$ tales que

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

para todos $i.$

Lagrange Interpolation Formula es exactamente el resultado, en este caso, de la construcción anterior de la solución. Más precisamente, deja

${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 parcial de la fracción ${displaystyle {frac {1}{Q(X)}}}$ es

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

De hecho, reduciendo el lado derecho a un denominador común que 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, como ser un polinomio de grado menos que $k,$ que toma el valor uno para $k$ diferentes valores de $X.$

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

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

Hermite Interpolation

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

El problema consiste en encontrar un polinomio del menor grado posible, de modo que el polinomio y sus primeros derivados toman valores dados en algunos puntos fijos.

Más precisamente, dejemos $x_{1},ldotsx_{k}$ Ser $k$ elementos del terreno $K,$ y, para ${displaystyle i=1,ldotsk,}$ Deja ${displaystyle a_{i,0},a_{i,1},ldotsa_{i,r_{i}-1}}$ ser los valores de la primera $r_{i}$ derivados del polinomio buscado $x_{i}$ (incluido el derivado 0, que es el valor del propio polinomio). El problema es encontrar un polinomio $P(X)$ tal que jth derivative toma el valor $a_{i,j}$ a ${displaystyle x_{i},}$ para $i=1,ldotsk$ y ${displaystyle j=0,ldotsr_{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 orden Taylor ${displaystyle r_{i}-1}$ a $x_{i}$ , del polinomio desconocido ${displaystyle P(X).}$ Por lo tanto, debemos tener

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

Por el contrario, cualquier polinomio ${displaystyle P(X)}$ que satisface estos $k$ congruencias, en particular verifica, para cualquier ${displaystyle i=1,ldotsk}$

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

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

Hay varias maneras de calcular la solución ${displaystyle P(X).}$ Se puede utilizar el método descrito al comienzo de § Sobre anillos polinomios univariados y dominios Euclidesanos. También se puede utilizar las construcciones dadas en § Existencia (prueba constructiva) o § Existencia (prueba directa).

Generalización a módulos no de forma no de forma

El teorema restante chino puede ser generalizado a moduli no coprime. Vamos ${displaystyle m,n,a,b}$ ser cualquier entero, dejar ${displaystyle g=gcd(m,n)}$ ; ${displaystyle M=operatorname {lcm} (m,n)}$ , y considerar el sistema de congruencias:

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

Si ${displaystyle aequiv b{pmod {g}}}$ , entonces este sistema tiene un modulo de solución único ${displaystyle M=mn/g}$ . De lo contrario, no tiene soluciones.

Si usamos la identidad de Bézout para escribir ${displaystyle g=um+vn}$ , entonces la solución es

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

Esto define un entero, como $g$ divide ambos $m$ y n . De lo contrario, la prueba es muy similar a la de los módulos de Coprime.

Generalización a anillos arbitrarios

El teorema restante chino se puede generalizar a cualquier anillo, utilizando ideales coprime (también llamados ideales comaximal). Dos ideales $I$ y $J$ son coprime si hay elementos $iin I$ y $jin J$ tales que ${displaystyle i+j=1.}$ Esta relación desempeña el papel de la identidad de Bézout en las pruebas relacionadas con esta generalización, que de otro modo son muy similares. La generalización puede indicarse como sigue.

Vamos $I 1,... I k$ ser dos caras ideales de un anillo $R$ y dejar $I$ ser su intersección. Si los ideales son coprime pares, tenemos el 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 el anillo de cociente $R/I$ y el producto directo del ${displaystyle R/I_{i},}$ Donde ${displaystyle x{bmod {I}}}$ "denota la imagen del elemento $x$ en el anillo de referencia definido por el ideal ${displaystyle I.}$ Además, si $R$ es conmutativa, entonces la intersección ideal de los ideales pares coprime es igual a su producto; es

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

if $i i$ y $i j$ son Coprime para todos $i \neq j .$

Interpretación en términos de idempotentes

Vamos ${displaystyle I_{1},I_{2},dotsI_{k}}$ ser pareja coprime dos caras ideales con ${displaystyle bigcap _{i=1}^{k}I_{i}=0,}$ y

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

sea el isomorfismo definido arriba. Vamos ${displaystyle f_{i}=(0,ldots1,ldots0)}$ ser el elemento de ${displaystyle (R/I_{1})times cdots times (R/I_{k})}$ cuyos componentes son todos $0$ excepto el $i$ que $1$ , y ${displaystyle e_{i}=varphi ^{-1}(f_{i}).}$

El $e_{i}$ son idempotentes centrales que son ortogonales pares; esto significa, en particular, que ${displaystyle e_{i}^{2}=e_{i}}$ y ${displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$ para todos $i$ y $j$ . Además, uno tiene ${textstyle e_{1}+cdots +e_{n}=1,}$ y ${displaystyle I_{i}=R(1-e_{i}).}$

En resumen, este teorema del resto chino generalizado es la equivalencia entre dar ideales de dos lados de Coprime por pares con una intersección cero, y dar idempotentes ortogonales centrales y por pares que suman $1$ .

aplicaciones

Numeración de secuencia

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

Fast Fourier Transform

El algoritmo FFT de primer factor (también llamado algoritmo Good-Thomas) utiliza el teorema de restante chino para reducir la computación de una rápida transformación Fourier de tamaño $n_{1}n_{2}$ a la computación de dos rápidos transformaciones Fourier de tamaños más pequeños $n_{1}$ y $n_{2}$ (proporcionando que $n_{1}$ y $n_{2}$ son coprime).

Cifrado

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

El teorema del resto chino también se puede usar en el intercambio secreto, que consiste en distribuir un conjunto de acciones entre un grupo de personas que, todos juntos (pero nadie solo) pueden recuperar un cierto secreto del conjunto dado de acciones. Cada una de las acciones está representada en una congruencia, y la solución del sistema de congruencias utilizando el teorema del resto chino es el secreto que se recuperará. Compartir en secreto utilizando los usos del teorema del resto chino, junto con el teorema del resto chino, secuencias especiales de enteros que garantizan la imposibilidad de recuperar el secreto de un conjunto de acciones con menos de cierta cardinalidad.

Resolución de ambigüedad de rango

Las técnicas de resolución de ambigüedad de rango utilizadas con el radar de frecuencia de repetición de pulso medio pueden verse como un caso especial del teorema del resto chino.

Descomposición de las superficies de grupos abelianos finitos

Dada la superjección ${displaystyle mathbb {Z} /nto mathbb {Z} /m}$ de grupos abelianos finitos, podemos utilizar el teorema de restos chinos para dar una descripción completa de cualquier mapa de este tipo. En primer lugar, el teorema da isomorfismos

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

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

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

de la surjección original, tenemos ${displaystyle a_{k}geq b_{l}}$ y ${displaystyle p_{n_{k}}=p_{m_{l}},}$ desde para un par de primos $p,q$ , las únicas subjeciones no cero

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

puede definirse si $p=q$ y $ageq b$ .

Estas observaciones son fundamentales para construir el anillo de enteros perfinados, que se da como un límite inverso de todos estos mapas.

teorema de Dedekind ' s

teorema de Dedekind &#39 en la independencia lineal de los caracteres. LET $m$ be a a monoide y $k$ un dominio integral, visto como un monoide al considerar la multiplicación en $k$ . Entonces cualquier familia finita $(f i) i \in i$ de homomorfismos monoides distintos $f i : m \to k$ es linealmente independiente. En otras palabras, cada familia $(α i) i \in i$ de elementos $α i \in k$ satisfactorio

$sum_{i in I}alpha_i f_i = 0$

debe ser igual a la familia $(0) i \in i$ .

prueba. primero suponga que $k$ es un campo, de lo contrario, reemplace el dominio integral $k$ por su campo de cociente, y nada cambiará. Podemos extender linealmente los homomorfismos monoide $f i : m \to k <$ to $k$ -algebra homomorfisss $f i : k [m] \to k$ , donde $k [m]$ es el anillo monoide de $m$ sobre $k$ . Entonces, por linealidad, la condición

$sum_{iin I}alpha_i f_i = 0,$

rendimientos

$sum_{i in I}alpha_i F_i = 0.$

A continuación, para $i, j \in i; i \neq j$ los dos $k$ -linear maps $f i : k [m] \to k$ y $f j : k [m] \to k$ no son proporcionales entre sí. De lo contrario $f i$ y $f j$ también sería proporcional, y por lo tanto igual, 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 kernels $ker f i$ y $ker f J$ son distintos. Desde $k [m]/ker f i ≅ f i (k [m]) = k$ es un campo, $ker f i$ es un ideal máximo de $k [[m]$ por cada $i$ en $i$ . Porque son distintos y máximos los ideales $ker f i$ y $ker F J$ son Coprime cuando $i \neq j$ . El teorema del resto chino (para anillos generales) produce un isomorfismo:

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

donde

$K = prod_{i in I}mathrm{Ker} F_i = bigcap_{i in I}mathrm{Ker} F_i.$

En consecuencia, el mapa

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

es surjetivo. Bajo los isomorfismos $k [m]/ker f i \to F I (k [m]) = k,$ el mapa $φ$ corresponde a:

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

ahora,

$sum_{i in I}alpha_i F_i = 0$

rendimientos

$sum_{i in I}alpha_i u_i = 0$

Para cada vector $(u i) i \in i$ en la imagen del mapa $ψ$ . Dado que $ψ$ es sujectivo, esto significa que

$sum_{i in I}alpha_i u_i = 0$

por cada vector

$left(u_iright)_{i in I} in prod_{i in I}k.$

En consecuencia, $(α i) i \in i </i = (0) i \in i$ . Qed.

Contenido relacionado

Covarianza y contravarianza de vectores
En física, especialmente en álgebra multilineal y análisis tensorial, la covarianza y la contravarianza describen cómo cambia la descripción cuantitativa...
Extensión algebraica
En matemáticas, una extensión algebraica es una extensión de campo L/K tal que cada elemento del campo más grande L es algebraico sobre el campo más...
Raíz primitiva módulo n
En aritmética modular, un número g es un módulo raíz primitivo n si cada número a coprimos a n es congruente con una potencia de g módulo n. Es decir, g...
Más resultados...
Te puede interesar