3.4: El teorema del resto chino

Última actualización
Guardar como PDF

Page ID: 114996

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

En esta sección, se discute la solución de un sistema de congruencias que tiene diferentes módulos. Un ejemplo de este tipo de sistemas es el siguiente; encontrar un número que deja un resto de 1 cuando se divide por 2, un resto de 2 cuando se divide por tres y un resto de 3 cuando se divide por 5. Este tipo de preguntas pueden traducirse al lenguaje de las congruencias. Como resultado, en este capítulo, presentamos una manera sistemática de resolver este sistema de congruencias.

El sistema de congruencias

\[\begin{aligned} && x\equiv b_1(mod \ n_1),\\&&x\equiv b_2(mod \ n_2),\\&&.\\&&.\\&&.\\&& x\equiv b_t(mod \ n_t),\end{aligned}\]

tiene un módulo de solución único\(N=n_1n_2...n_t\) si\(n_1,n_2,...,n_t\) son números enteros positivos primos relativamente por pares.

Vamos\(N_k=N/n_k\). Ya que\((n_i,n_j)=1\) para todos\(i\neq j\), entonces\((N_k,n_k)=1\). De ahí que por el Teorema 26, podemos encontrar una inversa\(y_k\) de\(N_k\) módulo\(n_k\) tal que\(N_ky_k\equiv 1(mod \ n_k)\). Considerar ahora

\[x=\sum_{i=1}^tb_iN_iy_i\]

Ya que\[N_j\equiv 0(mod \ n_k) \ \ \mbox{for all} \ \ j\neq k,\] así vemos eso\[x\equiv b_kN_ky_k(mod \ n_k).\] También notamos eso\(N_ky_k\equiv 1(mod \ n_k)\). De ahí\(x\) que sea una solución al sistema de t congruencias. Tenemos que demostrar ahora que dos soluciones cualesquiera son congruentes módulo\(N\). Supongamos ahora que tiene dos soluciones\(x_0,x_1\) al sistema de congruencias. Entonces\[x_0\equiv x_1(mod \ n_k)\] para todos\(1\leq k\leq t\). Así por el Teorema 23, vemos que\[x_0\equiv x_1(mod \ N).\] Así la solución del sistema es único módulo\(N\).

Presentamos ahora un ejemplo que mostrará cómo se utiliza el teorema del resto chino para determinar la solución de un sistema dado de congruencias.

Ejemplo\(\PageIndex{1}\):

Resuelve el sistema\[\begin{aligned} && x\equiv 1(mod \ 2)\\&& x\equiv 2(mod \ 3)\\&& x\equiv 3(mod \ 5).\end{aligned}\] que tenemos\(N=2.3.5=30\). También\[N_1=30/2=15, N_2=30/3=10 \mbox{and} \ \ N_3=30/5=6.\] Así que tenemos que resolver ahora\(15y_1\equiv 1(mod \ 2)\). Así\[y_1\equiv 1(mod \ 2).\] De la misma manera, encontramos que\[y_2\equiv 1(mod \ 3) \mbox{and} \ \ y_3\equiv 1(mod \ 5).\] Como resultado, obtenemos\[x\equiv 1.15.1+2.10.1+3.6.1\equiv 53\equiv 23 (mod \ 30).\]

Ejercicios

Encuentra un número entero que deja un resto de 2 cuando se divide por 3 o 5, pero que es divisible por 4.
Encuentra todos los enteros que dejan un resto de 4 cuando se divide por 11 y deja un resto de 3 cuando se divide por 17.
Encuentra todos los enteros que dejan un resto de 1 cuando se divide por 2, un resto de 2 cuando se divide por 3 y un resto de 3 cuando se divide por 5.

Colaboradores y Atribuciones

Template:ContribRaji