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 [2] 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 [3] y pude ser cero en el caso que el divisor divida al dividendo [4].
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$.
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 [5]
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.
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:
De la ecuación se desprende inmediatamente que m divide a n - n'.
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:
\begin{eqnarray*} n &=& mq + r\\ n'& =&mq'+r' \end{eqnarray*}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.
Como vimos anteriormente [6], la resta de dos números, del mismo residuo al dividir entre $m$ , es divisible por $m$ . Es por ello, que se inventó la notación de módulos:
$a \equiv b$ $(\textrm{mod}$ $m) $ significa que a y b tienen el mismo residuo al dividirse por m. |
Esta notación se lee así: a congruente con b módulo m.
En principio puede parecer una definición sin sentido, pero la gran ventaja de esta notación es la clara forma de expresar los siguientes resultados tan valiosos:
Propiedades | |
---|---|
$a \equiv b$ $(\textrm{mod}$ $m)$ y $c \equiv d$ $(\textrm{mod}$ $m) \Rightarrow$ $a+c \equiv b+d$ $(\textrm{mod}$ $m)$ | Conservación de la suma. |
$a \equiv b$ $(\textrm{mod}$ $m)$ y $c \equiv d$ $(\textrm{mod}$ $m) \Rightarrow$ $ac \equiv bd$ $(\textrm{mod}$ $m)$ | Conservación del producto. |
Estos resultados se dejan como actividad para el lector. Pero, es mejor calentar primero con la siguientes propiedades básicas.
Propiedades básicas | |
---|---|
$a \equiv a$ $(\textrm{mod}$ $m)$ | Reflexión. Un número siempre es congruente consigo mismo. |
$a \equiv b$ $(\textrm{mod}$ $m) \Rightarrow$ $b \equiv a$ $(\textrm{mod}$ $m)$ | Simétrica. a congruente con b , es lo mismo que b congruente con a |
$a \equiv b$ $(\textrm{mod}$ $m)$ y $b \equiv c$ $(\textrm{mod}$ $m) \Rightarrow$ $a \equiv c$ $(\textrm{mod}$ $m)$ | Transitividad. a congruente con b y este congruente con c, entonces a y c son congruentes. |
Cabe señalar, aunque caiga fuera de los objetivos de esta página, que las propiedades de la tabla anterior convierten a la congruencia en una relación de equivalencia.
Bueno, nada más por no dejar presentamos las pruebas de la preservación de la suma y del producto.
Deseamos probar:
\[a \equiv b \pmod{m} \textrm{ y } c \equiv d \pmod{m} \Rightarrow a+c \equiv b+d \pmod{m} \]
Entonces, por hipótesis, se tiene que a y b tienen el mismo residuo al dividir entre n y, de la misma manera, c y d. Traducido en términos algebraicos, esto significa que existe $ p $ y $ q $ tales que: $a-b = mp$ y $c-d = mq$. Ahora bien, al sumar estas dos últimas igualdades se obtiene que $(a-b) +(c-d) = mp+mq =m(p+q)$. Reagrupando, $(a+c) -(b+d) = m(p+q)$. Lo anterior significa que la resta de (a+c) y de (b+d) es divisible por m, o lo que es lo mismo, tienen el mismo residuo. Por lo tanto $a+c \equiv b+d$ $(\textrm{mod}$ $m)$.
Es un buen ejercicio dejar esta prueba para los alumno, pero se presenta aquí para aquél que deseé consultarla. Bueno, pues deseamos probra que:
$a \equiv b$ $(\textrm{mod}$ $m)$ y $c \equiv d$ $(\textrm{mod}$ $m) \Rightarrow$ $ac \equiv bd$ $(\textrm{mod}$ $m)$ |
Entonces, sabemos que existen $ p $ y $ q $ tales que:
\begin{eqnarray}\label{equation_1} a-b&=&mp\\ \label{equation_2} c-d&=&mq \end{eqnarray}Ahora bien, multiplicando la ecuación (\ref{equation_1}) por $ c $ y la ecuación (\ref{equation_2}) por $ b $, se obtienen las siguientes igualdades:
\begin{eqnarray*} ac-bc &=& mpc\\ bc-bd &=& mqb \end{eqnarray*}Sumando ambas ecuaciones se obtiene que $ac -bd = m(pc+qb)$, es decir, $ac \equiv bd$ $(\textrm{mod}$ $m)$ .
Algunas consecuencias inmediatas de la preservación de la suma y del producto en las congruencias son las siguientes tres:
$a \equiv b \pmod{m}$ implica que $a + c \equiv b+c \pmod{m}$ para cualquier entero $c$.
Esto es evidentemente cierto, pues $c \equiv c \pmod{m}$ (propiedad reflexiva), y por la preservación de la suma llegamos al resultado.
$a \equiv b \pmod{m}$ implica que $c\cdot a \equiv c \cdot b \pmod{m}$ para cualquier entero $c$.
Es igual de evidente que la anterior, se usa la propiedad reflexiva junto con la preservación del producto.
$a \equiv b \pmod{m}$ implica que $a^{n} \equiv b^{n} \pmod{m}$ para cualquier entero $n \geq 0$.
Esta observación es menos obvia que la anteriores, pero es igualmente cierta y fácil de probar. Primero que nada, el caso $n=0$ es evidentemente cierto pues $a^n =1 = b^n$. Entonces, lo interesante es probar para $n \geq 1$,
Para la demostración formal debe procederse por inducción, pero en esta ocasión sólo vamos a convencernos de ello, analizando los pasos de dicha demostración.
Primero que nada, observemos que como $a \equiv b \pmod{m}$ y $a \equiv b \pmod{m}$ (sí... dos veces lo mismo), podemos multiplicar ambas congruencias por la regla de preservación del producto y obtener que $a^2 \equiv b^2 \pmod{m}$.
Podemos repetir esta regla del producto, pero ahora para $a^2 \equiv b^2 \pmod{m}$ y $a \equiv b \pmod{m}$, y de esta manera obtener que $a^3 \equiv b^3 \pmod{m}$.
Entonces, no es muy difícil convencerse que este proceso nos lleva a que $a^n \equiv b^n \pmod{m}$ para cualquier entero positivo $n$, como queríamos probar.
Ejemplo: Prueba que 6 divide a 20112000+5.
La solución con congruencias es muy fácil. Como queremos ver si algo es divisible entre 6 pues usaremos modulo 6.
Sin mucho trabjo se puede calcular el residuo de 2011, que es 1. Es decir:
Ahora bien, también se tiene la siguiente congruencia:
¡Pero si es la misma! 8-o
Sí es la misma, pero lo importante es que viendola escrita dos veces queda claro que se pueden usar las propiedades de conservación del producto (sólo que a=c y b=d). Entonces, por la conservación del producto se tiene que:
O lo que es lo mismo:
Ahora, si aplicamos nuevamente la conservación del producto se obtiene:
Que es lo mismo que:
De esto se observa que podermos seguir así hasta probar que:
Por último, se sabe que:
Y usando la conservación de la suma se obtiene:
Peo como 6 es congruentre con 0 modulo 6, entonces se tiene que:
O lo que es lo mismo: $2011^n + 5 $ es divisble por 6 para todo valor de n.
Una aplicación clásica de los módulos es en la prueba de los criterios de divisibilidad, y en particular en la prueba de los criterio del 9 y del 11.
Bueno, para entender con exactitud los criterios de divisibilidad hay que recordar el significado de la notación decimal que usamos hoy en día. Que no es más que la notación decimal es posicional y de base 10. Esto se ve en la secundaria (y también algo en la primaria), para los que no se acuerden, esto significa únicamente que, por ejemplo, $$2457 = 2 \times 10 ^3 + 4 \times 10^2 + 5 \times 10 +7$$
En términos más abstractos, pero es exactamente lo mismo, se dice así:
Teorema. Para cualquier entero positivo $N$ existe una sucesión (lista) finita de enteros única $a_0, a_1, a_2, \ldots, a_n$ entre 0 y 9, tales que $$N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$$,
El teorema, en otras palabra, dice que todo entero positivo se puede escribir en base 10.
Una función polinomial, es una función de la forma $f(x) = c_nx^n+c_{n-1}x^{n-1} + \cdots + c_1x+c_0$.
Por ejemplo, $p(x) = 5x^2+2x+9$ es una función polinomial de grado 2. No es muy difícil de convencerse de que $p(10) = 529$.
De esta manera, si $N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$, es la notación decimal de $N$, entonces, $N=f(10)$ donde $f(x) =a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 $
Ahora bien, recordemos que si $b \equiv d \pmod{m}$ entonces $b^k \equiv d^k \pmod{m}$ para todo entero positivo $k$, por lo que, $a_kb^k \equiv a_kd^k \pmod{m}$, y sumando todas estas congruencias obtenemos que $$a_nb^n + a_{n-1}b^{n-1} + \cdots + a_1b + a_0 \equiv a_nxd^n + a_{n-1}d^{n-1} + \cdots + a_1d + a_0 \pmod{m}$$ Que es lo mismo que decir que $$f(b) \equiv f(d) \pmod{m}.$$ Hemos probado entonces que:
Teorema. Si $b\equiv d \pmod{m}$ entonces $f(b) \equiv f(d) \pmod{m}$ para toda función polinomial $f$ con coeficientes enteros.
Como $10 \equiv 1 \pmod{9}$, entonces, $f(10) \equiv f(1) \pmod{9}$.
Si $N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$ es la expansión decimal del número N, entonces, $f(10)=N$, y $f(1) = a_0+a_1+ \cdots a_n$ donde $f(x) =a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 $ . Por lo tanto, $$N \equiv a_0+a_1+ \cdots a_n \pmod{9}.$$
Ejemplo. Con el número $N= 12756$ se tiene que $12756 \equiv 1+2+7+5+6 \pmod{9}$, es decir, $22756 \equiv 21 \equiv 2+1 \equiv 3 \pmod{9}$. Por lo que el residuo de dividir a 12, 756 entre 9 es 3.
Ahora bien, en este ejemplo se ve que $9$ no divide a 12,756. Pero como 3 divide a 9, podemos cambiar el módulo por módulo 3. Esto nos da que $12756 \equiv 0 \pmod{3}$, por lo tanto, 3 sí divide a 12,756.
Como $10 \equiv -1 \pmod{11}$ podemos ahora usar el mismo argumento y obtener que si $N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$ entonces $N \equiv a_0 - a_1 +a_2-a_3 + \cdots+ (-1)^{n}a_n \pmod{11}$
Ejemplo. Con el número $N= 12756$ se tiene que $12756 \equiv 6-5+7-2+1 \equiv 7 \pmod{11}$, por lo que el residuo de dividir 12,756 entre 11 es 7.
En los ejemplos, se observa que estos criterio no sólo nos determinan si el número es o no divisible por el divisor en cuestión, si no que además nos ayuda a encontrar el residuo de la división sin tener que hacer la división.
Pare motivar la definición que veremos más adelante resolvamos primero los siguientes problema ejemplos.
Problema 1. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 1 \pmod{5}$.
Solución. Como sabemos $x \equiv 0,1,2,3 \textrm{ o } 4 \pmod{5}$ para cualquier número $x$. Entonces, al multiplicar por 2 obtenemos que $2x \equiv 0, 2,4,1 \textrm{ o } 3 \pmod {5}$, en consecuencia, sólo cuando $x \equiv 3 \pmod{5}$ se satisfacerá la congruencia $2x \equiv 1 \pmod{5}$. Esto nos determina por completo las soluciones, que serán los números $x$ que dejan residuo 3 al dividirse entre 5.
Problema 2. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 4 \pmod{6}$.
Solución. De manera similar, sabemos que $x \equiv 0,1,2,3, 4, \textrm{ o } 5 \pmod{6}$ para todo número $x$. Lo que significa que $2x \equiv 0, 2,4,0, 2, \textrm{ o } 4 \pmod {6}$, en consecuencia, las únicas posibilidad se dan cuando $x \equiv 2 \textrm{ o } 5 \pmod{6}$. Entonces las soluciones son los números que dejan residuo 2 o 5 al dividirse entre 6.
Problema 3. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 3 \pmod{6}$.
Solución. Por el análisis del problema anterior, los residuos posibles de $2x$ son sólo 0, 2 y 4. Entonces esta ecuación no tiene solución.
Al leer con cuidado estos ejercicios, se observa que para dar las soluciones de una ecuación de la forma $ax \equiv b \pmod{m}$ basta con encontrar todos los residuos módulo $m$ que satisfacen la ecuación.
Por cuestiones prácticas de argumentación en demostraciones, es conveniente permitir que los residuos sean dados por números no necesariamente menores al módulo, por ejemplo, en lugar de decir que 2 y 5 son las soluciones de la ecuación $2x \equiv 4 \pmod{6}$, podríamos decir, que 8 y -1 son las soluciones de esta ecuación, pues finalmente $8 \equiv 2 \pmod{6}$ y $5 \equiv -1 \pmod{6}$.
Más formalmente, decimos que $x_1, x_2, \ldots, x_k$ son las soluciones de la ecuación $ax \equiv b \pmod{m}$, si se satisface que:
La primera condición dice que los números $x_1, x_2, \ldots, x_k$ son soluciones de la ecuación y la segunda que cualquier otra solución es congruente a una y sólo una de éstas.
Bueno, ahora pasaremos al teorema principal
Teorema. La ecuación diofantina $ax \equiv b \pmod{m}$ tiene solución si y sólo si $(a,m) | b$. Más aun, si $(a,m) | b$ entonces la ecuación tendrá $(a,m)$ soluciones no congruentes.
Demostración: Supongamos que existe solución $x_0$, entonces $ax_0 -b$ será un múltiplo de $m$, es decir, $ax_0 -b = km$ para algún entero $k$. Luego tenemos que $ax_0 - ḱm = b$ y de aquí se sigue que $(a,m) | b$.
Ahora probemos en la otra dirección, supongamos que $(a,m) | b$ y tratemos de demostrar que existe solución. Llamemos $g = (a,m)$ y por la identidad de Bezout [7] existen enteros $x_0$ y $y_0$ tales que $ax_0 + my_0 = g$. Como $b$ es múltiplo de $g$ tendremos que existe $k$ tal que $b = kg$, entonces multiplicando la expresión del enunciado anterior por $k$ tendremos que: $$a(kx_0) + m(k y_0) = b.$$
Aplicando módulo $m$ tendremos que $a(kx_0) \equiv b \pmod{m}$ y por lo tanto $kx_0$ es solución de la ecuación de $ax \equiv b \pmod{m}$.
Esto termina la primera parte, ahora sólo nos falta demostrar que son exactamente $(a,m)=g$. Denotemos con $x_1$ una solución cualquiera, demostraremos primero que $x_1 + (m/g)*t$ con $t=0,1, \dots, g-1$ son todas las solución. Efectivamente son soluciones, pues $a(x_1+(m/g)t) = ax_1 + (a/g)mt \equiv ax_1 \equiv b \pmod{m}$.
Ahora verifiquemos que cualquier solución tiene que tener dicha forma. Denotemos con $x$ una solución genérica, deberá satisfacer que $ax \equiv ax_1 \pmod{m}$, es decir que, $a(x_1 -x) \equiv 0 \pmod{m}$. Ahora, dividiendo entre $g$ obtenemos $a/g(x_1 -x) \equiv 0 \pmod{m/g}$. Como $a/g$ y $m/g$ son primos relativos (pues les quitamos el máximo común divisor) , podemos cancelar $a/g$ y resulta entonces que $x \equiv x_1 \pmod{m/g}$. La anterior ecuación es equivalente a decir que $x$ tiene la forma $x = x_1 + t(m/g)$ para alguna $t$
El parámetro $t$ se debe reducir módulo $g$, pues $t \equiv t_0 \pmod{g}$ si y sólo si $x_1 + t(m/g) \equiv x_1 + t_0(m/g) \pmod{m}$. Ésto termina la prueba
Enlaces:
[1] http://matetam.homelinux.org/dokuwiki/lib/exe/detail.php?id=numeros%3Atemas%3Adivisibilidad%3Acongruencias&cache=cache&media=numeros:temas:topicos_sobre_divisibilidad:division.png
[2] https://www.matetam.com/glosario/definicion/algoritmo-division-inexacta
[3] https://www.matetam.com/glosario/definicion/divisor
[4] https://www.matetam.com/glosario/definicion/dividendo
[5] http://www.matetam.homelinux.org/dokuwiki/doku.php?id=glosarios:logica:index#equivalencia
[6] https://www.matetam.com/de-consulta/books/teoremas-basicos-divisibilidad/congruencias-modulos
[7] https://www.matetam.com/../../../../../../glosario/teorema/identidad-bezout