Un ejercicio de dos ecuaciones lineales:
Un ejercicio distinto de dos ecuaciones lineales:
Un ejercicio de resolver un sistema de 3 ecuaciones lineales:
Un ejercicio de dos ecuaciones lineales:
Un ejercicio distinto de dos ecuaciones lineales:
Un ejercicio de resolver un sistema de 3 ecuaciones lineales:
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 y realizamos todas las operaciones «sólo en el mundo de
«, es decir, aplicando las operaciones únicamente en los residuos que deja un número al ser dividido entre
.
Cuando estamos trabajando módulo , dos enteros
y
«son los mismos» si
divide a
. En este caso decimos que
, que se lee «
es congruente con
módulo
«.
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.
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 al dividirse entre
.
Sugerencia pre-solución. Intenta resolver este problema trabajando módulo .
Solución. Tenemos que ,
,
y
los podemos poner como un múltiplo de
más un residuo como sigue:
,
y
,
. Así,
,
,
y
. Así, trabajando módulo
tenemos que:
Utilizando el algoritmo de la división, que vimos en la entrada anterior, se puede probar el siguiente resultado.
Proposición. Para cada entero y entero positivo
, existe un único número
en
tal que
, que es justo el residuo obtenido al dividir
entre
.
Dicho en otras palabras, sólo hay posibles residuos al dividir entre
. Esto nos permite que las operaciones módulo
siempre las hagamos con números chiquitos, y que afirmaciones sencillas de divisibilidad entre
dependen sólo de
casos. Esto lo podemos aprovechar para resolver problemas como el siguiente.
Problema. Se tienen números enteros. Muestra que hay tres de ellos
que satisfacen que
Sugerencia pre-solución. Notemos que , así que trabajamos módulo
. Encuentra todas las posibilidades que pueden tener los números cuadrados.
Solución. Un entero sólo puede ser congruente con alguno de los números
módulo
. Los cuadrados tienen entonces las siguientes posibilidades:
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
![]() | ![]() |
A partir del estamos aprovechando que ya conocemos los del
al
y que
. Notemos que sólo hay
residuos posibles para los cuadrados módulo
, que son
,
,
,
,
y
.
Ahora sí, resolvamos el problema. Como tenemos números enteros y sólo hay
posibles residuos para los cuadrados módulo
, entonces por principio de las casillas hay tres de estos enteros cuyo cuadrado deja el mismo residuo al dividirse entre
, digamos
. Como dejan los tres el mismo residuo, tenemos
,
y
, de donde se sigue la conclusión que queremos.
Los últimos dígitos de un entero
corresponden con el residuo de dividir
entre
. Por esta razón, en este tipo de problemas es conveniente usar módulos.
Problema. Determina los últimos dos dígitos de .
Sugerencia pre-solución. Trabajamos módulo , así que todas las congruencias son módulo
. Hay muchas formas de proceder para encontrar
. Notemos que
. y que
Para , nos conviene notar que
, de modo que
pues los primeros dos sumandos son múltiplos de . De esta forma,
. Así,
, por lo que los dos últimos dígitos de la expresión son
.
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 y que tiene por lo menos
dígitos iguales a
.
Sugerencia pre-solución. Intenta hacer que los dígitos
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 , en donde hay
dígitos iguales a
.
El máximo común divisor de y
es
, de modo que existen enteros
y
tales que
.
Multiplicando esta igualdad por el entero , obtenemos que
. Aplicando módulo
obtenemos que
.
Como , esto nos dice que
es un múltiplo de
cuyos últimos
dígitos son los de
, es decir, que tiene por lo menos
dígitos iguales a
.
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 un entero,
enteros para
y
enteros positivos para
. Supongamos además que cada par
de enteros (
) son primos relativos. Entonces el sistema lineal de congruencias
El teorema tiene muchas aplicaciones tanto en resolución de problemas, como en matemáticas en general. Veamos un ejemplo.
Problema. ¿Será posible encontrar enteros consecutivos tales que cada uno de ellos sea divisible entre un cubo distinto de
?
Sugerencia pre-solución. Intenta construir el ejemplo usando el teorema chino del residuo con módulos y en donde los
son consecutivos.
Solución. Por el teorema chino del residuo, existe un entero positivo tal que
Para este entero, se tiene que divide a
,
divide a
,
divide a
,
divide a
y
divide a
.
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 , de los cuales hemos escrito aquí en el blog. Para empezar, aquí hay una entrada con videos de ejercicios de trabajar módulo
.
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.