Congruencias · Definición

Teorema chino del resto

teoría de números elementalcongruencias

Antes de empezar necesitas conocer

Muchos problemas de conteo y de calendario se reducen a resolver varias congruencias a la vez. El teorema chino del resto permite combinar esas condiciones en una sola congruencia equivalente.

Definición

El teorema chino del resto afirma que un sistema de congruencias lineales con módulos primos entre sí tiene solución única módulo el producto de esos módulos.

\[x \equiv a_i \pmod{m_i},\ i=1,\dots,k \Rightarrow x \equiv x_0 \pmod{m_1\cdots m_k}\]

Si \(m_1,\dots,m_k\) son primos entre sí dos a dos, el sistema \(x\equiv a_i \pmod{m_i}\) tiene una solución y todas las demás son congruentes con ella módulo \(M=m_1\cdots m_k\). La prueba construye la solución mediante \(M_i=M/m_i\) y un inverso \(y_i\) de \(M_i\) módulo \(m_i\), de modo que \(x=\sum a_i M_i y_i\). La existencia del inverso depende de que \(\mathrm{mcd}(M_i,m_i)=1\), que se deduce de la coprimalidad.

Para resolver \(x\equiv 2 \pmod 3\) y \(x\equiv 3 \pmod 5\), se toma \(M=15\). Con \(M_1=5\), el inverso de \(5\) módulo \(3\) es \(2\), y con \(M_2=3\), el inverso de \(3\) módulo \(5\) es \(2\). Así \(x\equiv 2\cdot5\cdot2+3\cdot3\cdot2=38\equiv 8 \pmod{15}\), que se verifica dividiendo \(8\) entre \(3\) y \(5\).

Un error típico es aplicar el teorema a módulos que no son primos entre sí, como \(x\equiv 0 \pmod 4\) y \(x\equiv 1 \pmod 6\), donde no hay solución porque \(x\) sería par e impar a la vez. Antes de usar el teorema hay que comprobar que \(\mathrm{mcd}(m_i,m_j)=1\) para todo par de módulos.

Para pensar

¿Por qué basta con que los módulos sean primos entre sí dos a dos?

Porque cada \(M_i=M/m_i\) es primo con \(m_i\), así que tiene inverso módulo \(m_i\).

Ejercicios 10

  1. ¿Qué condición deben cumplir los módulos \(m_1,\dots,m_k\) para aplicar el teorema chino del resto?
  2. ¿Cuál es el módulo del sistema \(x\equiv 1 \pmod 2\), \(x\equiv 2 \pmod 3\), \(x\equiv 4 \pmod 5\)?
  3. Si \(x\equiv a \pmod{m}\) y \(x\equiv b \pmod{n}\) con \(\mathrm{mcd}(m,n)=1\), ¿qué congruencia describe todas las soluciones?
  4. ¿Qué número cumple \(x\equiv 1 \pmod 3\) y \(x\equiv 0 \pmod 4\) dentro de los enteros entre \(0\) y \(11\)?
  5. ¿Cuántas soluciones distintas módulo \(M=m_1m_2\) tiene el sistema con módulos primos entre sí \(m_1\) y \(m_2\)?
  6. Resuelve \(x\equiv 2 \pmod 3\) y \(x\equiv 3 \pmod 4\). ¿Cuál es el residuo mínimo positivo de \(x\) módulo \(12\)?
  7. Resuelve \(x\equiv 1 \pmod 5\) y \(x\equiv 2 \pmod 7\). ¿Cuál es el menor entero positivo \(x\) que cumple ambas?
  8. Resuelve \(x\equiv 3 \pmod 4\) y \(x\equiv 4 \pmod 5\). ¿Cuál es el residuo de \(x\) módulo \(20\)?
  9. Un sistema con \(x\equiv 0 \pmod 6\) y \(x\equiv 1 \pmod 4\). ¿Tiene solución? Elige la afirmación correcta.
  10. Resuelve el sistema \(x\equiv 2 \pmod 3\), \(x\equiv 3 \pmod 5\), \(x\equiv 2 \pmod 7\). ¿Cuál es el residuo de \(x\) módulo \(105\)?

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 4
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2