Congruencias (módulos)

Versión para impresión

El conocimiento de este tema hace la diferencia entre un estudiante preparado para la olimpiada y uno que sólo domina las matemáticas escolares.

Este tema es fundamental en la olimpiadas de matemáticas, no conocerlo es como no haber estado en la olimpiada.

En el ámbito de la teoría de los números, la teoría de clases residuales ( o de modulos) es el segundo paso hacia el estudio de teoría de número.

El algoritmo de la división

El algoritmo de la división es el que todos conocemos, es el que nos han enseñado desde la primaria para calcular divisones. Por ejemplo, la imagen de la izquierda muestra cómo hago yo para calcular la división 2841÷17.

En estas cuentas se pueden observar dos números importantes, el de arriba de la casita (el 167) y el de hasta abajo (el 2).  Estos dos números son llamados repectivamente cociente y residuo.

También nos dijeron desde la primaria, cómo interpretar estos dos números.  El cociente (en el ejemplo es el 167) es el número de veces que el divisor (el 17) cabe en el dividento (el 2841) y el residuo (el 2) es lo que sobra. Aritméticamente, esto se expresa así: $2841 = 17 \times167 + 2$.

Es importante señalar que el residuo obtenido en una división siempre es menor que el divisor y pude ser cero en el caso que el divisor divida al dividendo.

Estas observaciones respecto al algoritmo de la división se pueden resumir matemáticamente así:

Dados dos números $n$ (dividendo) y $d$ (divisor), exiten dos únicos número enteros $q$ (cociente) y $r$ (residuo) tales que $n = d \cdot q + r$ y $0 \leq r< d$.

Residuos iguales

Ahora bien, ¿qué importancia tienen los residuos en la teoría de los números?

Pues una de las aplicaciones más importantes de los residuos es la siguiente equivalencia

Dos números tienen el mismo residuo al dividerse por un número m si y sólo si su resta es divisible por m.

Veamos un ejemplo.

Como vimos en la sección anterior el número 2841 tiene residuo 2 al dividirse por 17. Y por otro lado, el número 36 también tiene residuo 2 al dividirse por 17. Entonces, por la afirmación del párrafo anterior, sabemos que 2841-36 será divisible por 17. Si lo desean, pueden hacer las cuentas.

Y de manera reciproca, 2841 - 2807 = 34 y 34 es divisible por 17 entonces, el residuo de 2807 deber ser el mismo que el de 2841. Por lo tanto, el residuo de 2807 es 2 al dividirse por 17.

Actividad. Busca un número que tenga el mismo residuo que 2008 al ser divididos por 15. Verifica que la resta efectivamente sea divisible por 15.

La demostración de la ida

Ahora bien, la razón por la que la resta de dos números con el mismo residuo es divisible por el número es muy simple. Sean n y n' dos números con residuo r al dividirse por m, es decir, existe q y q' tales que:

n & = m(q)+r \\ n' & = m(q')+r \\
Entonces, al restar las dos ecuaciones obtenemos: \[ n -n' =(mq+r) -(mq'+r) = m(q-q')\]

De la ecuación se desprende inmediatamente que m divide a n - n'.

La demostración del regreso

Para demostrar por completo la afirmación, faltaría demostrar que si m divide a n-n' entonces, n y n' tienen el mismo residuo.

Usando el algoritmo de la división sabemos que deben existir q, q', r y r' tales que:

n =& mq + r\\ n' =&mq'+r'

Además r,r' < m y r,r'≥0 . Ahora bien, sabemos que n-n' es divisibles por m, por lo que existe un número p tal que n-n' = mp.

Entonces, poniendo todo junto se observa:

\[mp= n-n' = (mq+r) - (mq' +r')\]

En consecuencia:

\[m(p-q+q') = r-r'\]

De donde se observa que m debe dividir a r-r'. Sin perdida de generalidad, supongamos que r≥r', es decir r-r'≥0. Como m > r ≥ r-r', se sigue que r-r' es un número entre 0 y m-1 (pues m es estrictamente mayor que r-r'). Pero el único número entre 0 y m-1 que es divisible por m es el cero, por lo tanto, r-r' = 0, es decir, r = r'. O lo que es lo mismo, n y n' tienen el mismo residuo al dividirse por m.