Teorema chino del resto para Niños

El teorema chino del resto es un resultado sobre congruencias en teoría de números y sus generalizaciones en álgebra abstracta. Fue publicado por primera vez en el siglo III por el matemático chino Sun Tzu.

Contenido

Enunciado del teorema
Demostración del teorema
- Existencia de la solución
- Unicidad de la solución
Historia
Aplicaciones en criptografía
Véase también

Enunciado del teorema

Supongamos que n₁, n₂, …, n_k son enteros positivos coprimos dos a dos. Entonces, para enteros dados a₁,a₂, …, a_k, existe un entero x que resuelve el sistema de congruencias simultáneas

\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto $N = n_1 n_2 ... n_k$ .

De manera más general, las congruencias simultáneas pueden ser resueltas si los n_i's son coprimos a pares. Una solución x existe si y solo si:

a_i \equiv a_j \pmod{\operatorname{mcd}(n_i,n_j)} \qquad \text{para todo } i \ \text{y } j . \,\!

Todas las soluciones x son entonces congruentes módulo el mínimo común múltiplo de los n_i.

Un enunciado moderno en lenguaje algebraico es que para cada entero positivo con factorización en números primos

n = p_1^{r_1}\cdots p_k^{r_k},

se tiene un isomorfismo entre un anillo y la suma directa de sus potencias primas

\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_1^{r_1}\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/p_k^{r_k}\mathbb{Z}.

Demostración del teorema

Existencia de la solución

Sea N=n₁n₂...n_k y sea $N_i=\frac{N}{n_i}$ para i=1,...,k. Como todos los módulos n_i son coprimos entre sí, N_i y n_i son a su vez coprimos entre sí, luego por la Identidad de Bezout se asegura la existencia de dos enteros r_i y s_i tales que $r_in_i+s_iN_i=1$ . En tales condiciones, tomando las clases de equivalencia en ambos lados de la identidad, se tiene que para cada i, y para cada j ≠ i:

\begin{align} s_iN_i\equiv1\pmod{n_i} \\ s_iN_i\equiv0\pmod{n_j} \\ \end{align}

Por tanto, definiendo

x:=\sum_{i=1}^{k}a_is_iN_i=a_1s_1N_1+a_2s_2N_2+\ldots+a_ks_kN_k,

es claro que x es la solución buscada, debido a que al tomar clases de equivalencia en cada n_i, todos los sumandos se anulan a excepción del propio a_is_iN_i, y por tanto, $x\equiv a_i\pmod{n_i}$ para todo i =1,...,k. De esta manera, queda demostrado que x es solución del sistema.

Unicidad de la solución

En el caso de que todos los n_i sean coprimos, esa solución es la única existente módulo N. Para demostrarlo, supongamos que existiesen dos números enteros x e y que son soluciones distintas, entonces para i =1,2,...,k:

\begin{align} x\equiv a_i\pmod{n_i}\\ y\equiv a_i\pmod{n_i}\\ \end{align}

Esto implica que $x-y\equiv 0 \pmod{n_i}$ , y por ser todos los n_i coprimos, se sigue que el producto de los módulos N=n₁n₂...n_k también divide a x - y, es decir, $x \equiv y \pmod{N}$ .

Por tanto, toda solución del sistema es congruente con x en módulo N, tal y como se había establecido previamente en la formulación del teorema.

Historia

La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu y posteriormente publicado en 1247 por Qin Jiushao, es un enunciado sobre congruencias simultáneas (ver aritmética modular).

Versiones del teorema chino del resto fueron también conocidas por Brahmagupta, y aparecen en el Liber Abaci de Fibonacci (1202).

Aplicaciones en criptografía

El teorema del resto chino tiene importantes aplicaciones en criptografía, en especial para reducir operaciones con números enormes mediante el paso a congruencias. En el algoritmo RSA, por ejemplo, los cálculos se hacen módulo $n$ , donde $n$ es un producto de dos primos $p$ y $q$ . Tamaños habituales para $n$ son 1024, 2048 o 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo $\mathbf{Z}_n$ al anillo $\mathbf{Z}_p \times \mathbf{Z}_q$ . La suma de las longitudes de bit de $p$ y $q$ es la longitud de bit de $n$ , haciendo $p$ y $q$ considerablemente menor que $n$ . Esto acelera mucho los cálculos. Nótese que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de "fault injection".

Véase también

En inglés: Chinese remainder theorem Facts for Kids

Obtenido de «https://ninos.kiddle.co/index.php?title=Teorema_chino_del_resto&oldid=3888790»

Todo el contenido de los artículos de la Enciclopedia Kiddle (incluidas las imágenes) se puede utilizar libremente para fines personales y educativos bajo la licencia Atribución-CompartirIgual a menos que se indique lo contrario. Citar este artículo:

Teorema chino del resto para Niños. Enciclopedia Kiddle.

Teorema chino del resto para niños