Archivo de la etiqueta: teorema chino

Álgebra Superior II: Problemas de sistemas de congruencias y teorema chino del residuo

Un ejercicio de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio distinto de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio de resolver un sistema de 3 ecuaciones lineales:

Resolviendo un sistema de tres ecuaciones lineales

Seminario de Resolución de Problemas: Aritmética modular

Introducción

En la entrada anterior hablamos de divisibilidad, máximo común divisor y combinaciones lineales enteras. Cuando hablamos de trabajar en artimética modular nos referimos a que tomamos un entero n y realizamos todas las operaciones «sólo en el mundo de n«, es decir, aplicando las operaciones únicamente en los residuos que deja un número al ser dividido entre n.

Cuando estamos trabajando módulo n, dos enteros a y b «son los mismos» si n divide a a-b. En este caso decimos que a\equiv b \pmod n, que se lee «a es congruente con b módulo n«.

En esta entrada de blog discutimos la relación «ser congruente con» y cómo se puede enunciar en términos de anillos. Ahí damos las demostraciones de varias de las propiedades que no probaremos aquí. Es recomendable por lo menos echarle un ojo.

Aritmética modular

Para recordar los principios básicos de la aritmética modular, comencemos con el siguiente problema.

Problema. Determina cuál es el residuo obtenido de dividir 1305\cdot 1302+1314\cdot 1311 al dividirse entre 11.

Sugerencia pre-solución. Intenta resolver este problema trabajando módulo 11.

Solución. Tenemos que 1305, 1302, 1314 y 1311 los podemos poner como un múltiplo de 13 más un residuo como sigue: 1300+5, 1300+2 y 1313+1, 1300+11. Así, 1305\equiv 5\pmod {13}, 1302\equiv 2 \pmod {13}, 1314\equiv 1 \pmod {13} y 1311\equiv 11 \pmod {13}. Así, trabajando módulo 1 tenemos que:

    \begin{align*}1305\cdot 1302+1314\cdot 1311 &\equiv 5\cdot 2 + 1\cdot 11 \\&\equiv 10 + 11 \equiv 21 \\&\equiv 8 \pmod {13}\end{align*}


De esta forma, 1305\cdot 1302+1314\cdot 1311 deja residuo 8 al dividirse entre 13.

\square

Utilizando el algoritmo de la división, que vimos en la entrada anterior, se puede probar el siguiente resultado.

Proposición. Para cada entero a y entero positivo n, existe un único número r en \{0,1,\ldots,n-1\} tal que a\equiv r\pmod n, que es justo el residuo obtenido al dividir a entre n.

Dicho en otras palabras, sólo hay n posibles residuos al dividir entre n. Esto nos permite que las operaciones módulo n siempre las hagamos con números chiquitos, y que afirmaciones sencillas de divisibilidad entre n dependen sólo de n casos. Esto lo podemos aprovechar para resolver problemas como el siguiente.

Problema. Se tienen 13 números enteros. Muestra que hay tres de ellos a,b,c que satisfacen que

    \[1331\mid (a-b)(b-c)(c-a).\]

Sugerencia pre-solución. Notemos que 1331=11^3, así que trabajamos módulo 11. Encuentra todas las posibilidades que pueden tener los números cuadrados.

Solución. Un entero n sólo puede ser congruente con alguno de los números 0,1,2,3,4,5,6,7,8,9,10 módulo 11. Los cuadrados tienen entonces las siguientes posibilidades:

nn^2 \pmod {11}
00
11
24
39
416\equiv 5
525\equiv 3
636\equiv 3
7(-4)^2\equiv 5
89
94
101

A partir del 6 estamos aprovechando que ya conocemos los del 1 al 6 y que a \equiv a-11 \pmod {11}. Notemos que sólo hay 6 residuos posibles para los cuadrados módulo 11, que son 0, 1, 4, 9, 5 y 3.

Ahora sí, resolvamos el problema. Como tenemos 13 números enteros y sólo hay 6 posibles residuos para los cuadrados módulo 11, entonces por principio de las casillas hay tres de estos enteros cuyo cuadrado deja el mismo residuo al dividirse entre 11, digamos a,b,c. Como dejan los tres el mismo residuo, tenemos 11\mid a-b, 11\mid b-c y 11\mid c-a, de donde se sigue la conclusión que queremos.

\square

Últimos dígitos

Los últimos m dígitos de un entero n corresponden con el residuo de dividir n entre 10^m. Por esta razón, en este tipo de problemas es conveniente usar módulos.

Problema. Determina los últimos dos dígitos de 7^{25}+25^7.

Sugerencia pre-solución. Trabajamos módulo 100, así que todas las congruencias son módulo 100. Hay muchas formas de proceder para encontrar 7^{21}. Notemos que 7^{2}\equiv 49. y que

    \[7^4\equiv 49\times 49 = 2401 \equiv 1.\]

Esto es una gran ventaja, pues entonces 7^{24}\equiv (7^4)^6 \equiv 1^6 \equiv 1, así que 7^{25}\equiv 7.

Para 25^7, nos conviene notar que 25=20+5, de modo que

    \begin{align*}25^2&=(20+5)^2\\&=20^2+2\cdot 20 \cdot 5 + 25\\&\equiv 25,\end{align*}

pues los primeros dos sumandos son múltiplos de 100. De esta forma, 25^7\equiv 25. Así, 7^{25}+25^7\equiv 7+25\equiv 32, por lo que los dos últimos dígitos de la expresión son 32.

\square

Veamos otro ejemplo en el que además combinamos un poco de la teoría mencionada en la entrada anterior.

Problema. Demuestra que existe un entero que es múltiplo de 2002 y que tiene por lo menos 2002 dígitos iguales a 7.

Sugerencia pre-solución. Intenta hacer que los 2002 dígitos 7 que se necesitan aparezcan hacia el final. Esto te permitirá usar congruencias. Además, necesitarás el resultado de la entrada anterior que dice que el máximo común divisor de dos números se puede expresar como combinación lineal entera de ellos.

Solución. Tomemos el número N=777\cdots770, en donde hay 2002 dígitos iguales a 7.

El máximo común divisor de 2002 y 10^{2003} es 2, de modo que existen enteros m y n tales que 2002m+10^{2003}n=2.

Multiplicando esta igualdad por el entero N/2, obtenemos que 2002\cdot \frac{mN}{2}+10^{2003}\frac{nN}{2}=N. Aplicando módulo 10^{2003} obtenemos que 2002\cdot \frac{mN}{2} \equiv N \pmod {10^{2003}}.

Como N<10^{2003}, esto nos dice que 2002\cdot \frac{mN}{2} es un múltiplo de 2002 cuyos últimos 2003 dígitos son los de N, es decir, que tiene por lo menos 2002 dígitos iguales a 7.

\square

Teorema chino del residuo

En algunos problemas necesitamos construir un entero que satisfaga un conjunto de congruencias. El teorema chino del residuo nos da una condición bajo la cual podemos garantizar la existencia de dicho número.

Teorema. Sea n\geq 2 un entero, b_i enteros para i\in\{1,2,\ldots,n\} y m_i enteros positivos para i\in\{1,\ldots,n\}. Supongamos además que cada par m_i, m_j de enteros (i\neq j) son primos relativos. Entonces el sistema lineal de congruencias

    \begin{align*}x&\equiv b_1\pmod {m_1}\\ x&\equiv b_2\pmod {m_2}\\&\vdots\\ x&\equiv b_n\pmod {m_n}\end{align*}


tiene una y sólo una solución módulo m_1m_2\ldots m_n.

El teorema tiene muchas aplicaciones tanto en resolución de problemas, como en matemáticas en general. Veamos un ejemplo.

Problema. ¿Será posible encontrar 5 enteros consecutivos tales que cada uno de ellos sea divisible entre un cubo distinto de 1?

Sugerencia pre-solución. Intenta construir el ejemplo usando el teorema chino del residuo con 5 módulos y en donde los b_i son consecutivos.

Solución. Por el teorema chino del residuo, existe un entero positivo n tal que

    \begin{align*}n&\equiv 0 \pmod{2^3}\\n&\equiv -1\pmod{3^3}\\n&\equiv -2\pmod{5^3}\\n&\equiv -3\pmod{7^3}\\n&\equiv -4\pmod{11^3}\end{align*}

Para este entero, se tiene que 2^3 divide a n, 3^3 divide a n+1, 5^3 divide a n+2, 7^3 divide a n+3 y 11^3 divide a n+4.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.2 del libro Problem Solving through Problems de Loren Larson.

Hay otros dos teoremas que sirven cuando estamos trabajando módulo n, de los cuales hemos escrito aquí en el blog. Para empezar, aquí hay una entrada con videos de ejercicios de trabajar módulo n.

El teorema de Fermat y el de Wilson ayudan a entender potencias y factoriales, respectivamente. En la entrada sobre el teorema chino del residuo damos una demostración al teorema.