Si has seguido las lecciones anteriores de Teoría de Números, habrás observado que el quid de la divisibilidad se halla en la división euclídea ya que un número entero $a$ es divisible entre otro número entero $b$ si el resto de la división euclídea es exactamente cero. Es por ello interesante saber calcular el resto de la división y, de alguna forma ver como se comporta éste respecto a ciertas operaciones. Por ejemplo, sabemos que el resto de dividir $1003$ entre $9$ es igual a $4$, luego si restamos $4$ al número $1003$, resulta $999$, que tiene resto cero al dividirlo entre $9$. Como veremos más adelante, el resto de la diferencia estará muy relacionado con la diferencia de los restos.
Para empezar, vamos a observar la siguiente tabla donde escribimos los restos de 16 enteros consecutivos al dividirlos entre $2$, $3$ y $5$, respectivamente:
\[\begin{array}{r|rrrrrrrrrrrrrrrr} &-6&-5&-4&-3&-2&-1&0&1&2&3&4&5&6&7&8&9\\ \text{resto entre 2}&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1\\ \text{resto entre 3}&0&1&2&0&1&2&0&1&2&0&1&2&0&1&2&0\\ \text{resto entre 5}&4&0&1&2&3&4&0&1&2&3&4&0&1&2&3&4 \end{array}\]Si nos fijamos, en cada fila los restos se van repitiendo periódicamente y el resto oscila entre $0$ y una unidad menos que el divisor. Recuerda cómo hay que dividir un número negativo para preservar esta regla del resto (por ejemplo, para dividir $-6$ entre $5$, el cociente es $-2$ y el resto $4$ porque el resto nunca puede ser negativo).
Entonces, generalizando este resultado, los posibles restos de dividir entre $m$ son $0,1,2,\ldots,m-1$ y son cíclicos pues cuando sumamos una unidad a un número de resto $m-1$ vuelve a aparecer el resto $0$, es decir, los restos se repiten de $m$ en $m$. Es por ello que dos números tienen el mismo resto al dividirlos entre $m$ si su diferencia es un múltiplo de $m$. En tal caso diremos que son congruentes módulo $m$.
Es importante que te pares un momento a pensar bien la definición y, una vez lo hayas hecho, intentes demostrar que las siguientes congruencias son ciertas:
Observa que todos los números enteros son congruentes con uno de los números $0,1,\ldots,m-1$ al dividirlos entre $m$ (¡con su propio resto!) luego siempre podremos simplificar los resultados cuando trabajemos con congruencias a un número de este conjunto. Ahora es fácil ver que un número $a$ es divisible entre $m$ si, y sólo si, $a\equiv 0\ (\text{mod }m)$.
Es usual encontrarse con expresiones del tipo un número de la forma $4k+3$ ó el número es de la forma $8n+5$. Esto es, como bien puede entenderse, una forma de hablar pues en el primer caso estamos diciendo que existe $k\in\mathbb{Z}$ tal que el número en cuestión se escribe como $4k+3$ y en el segundo caso se puede hacer algo similar. Sin embargo, con congruencias se puede escribir estas expresiones de otra forma: en el primer caso podríamos decir un número congruente con $3$ módulo $4$ y en la segunda el número es congruente con $5$ módulo $8$. Lo importante es darse cuenta de que las dos formas de escribirlo son equivalentes.
Nuestra intención ahora es desarrollar reglas con las que podamos hacer cálculos con congruencias mucho más rápidos que hacer la división para hallar el resto. Vamos a ellas directamente.
Antes de pasar a la demostración, veamos un ejemplo. Supongamos que queremos hallar el resto de dividir $1234\cdot 6789$ entre $7$. Como el resto de dividir $1234$ es $2$ y el resto de dividir $6789$ es $6$, tenemos que $1234\cdot 6789\equiv 2\cdot 6=12\equiv 5\ (\text{mod }7)$. Si queremos hallar el resto de dividir $1+2+\ldots+9999$ entre $9$, observemos que los restos de los números naturales se van repitiendo en ciclos de $9$ luego tendremos que \[1+2+\ldots+9999\equiv 1111\cdot(1+2+\ldots+8+0)=1111\cdot 36\equiv 4\cdot 0\equiv 0\ (\text{mod } 9),\] lo que demuestra que $1+\ldots+9999$ es múltiplo de $9$, aunque esto es también fácil de ver usando la suma de los términos de una progresión aritmética.
Para ver lo que pasa con la multiplicación, hacemos el siguiente truco: $ac-bd=ac-bc+bc-bd=(a-b)c+b(c-d)=qmc+bhm$, que también es múltiplo de $m$ luego $ac\equiv bd\ (\text{mod }m)$.
Es interesante fijarse que si tomamos $a=c$ y $b=d$, la regla del producto nos dice que $a^2\equiv b^2\ (\text{mod }m)$. Esto se puede repetir indefinidamente, dando lugar a la siguiente regla para la potencia.
En otras palabras, estamos diciendo que podemos sustituir la base por otra congruente con ella, pero en general el exponente no puede sustituirse. Veamos algunos ejercicios resueltos donde se ve la potencia de cálculo que ofrecen las congruencias y cómo dar una solución al problema de los exponentes.
Se deja como ejercicio comprobar que $5555^{2222}\equiv 2\ (\text{mod }7)$ lo que termina de probar el enunciado.
Hemos visto cómo simplificar un exponente siempre que encontremos una potencia que sea congruente con $1$. El problema es cómo encontrarla porque en el ejercicio resuelto hemos ido probando caso por caso y hemos tenido suerte porque el módulo era pequeño. El siguiente teorema ofrece una respuesta al problema de encontrar la potencia en el caso muy particular de que el módulo sea primo, que generalizaremos en el Teorema de Euler más adelante.
Si pudiéramos simplificar $a$ en cada uno de los miembros de la congruencia del teorema, tendríamos una potencia del número congruente con $1$, pero la simplificación no es siempre posible; por ejemplo, $2\cdot 3\equiv 2\cdot 0\ (\text{mod }6)$ pero $3\not\equiv 0\ (\text{mod }6)$. En el siguiente apartado, veremos qué números se pueden simplificar y cuáles no y veremos una demostración alternativa del Teorema pequeño de Fermat.
También es importante darse cuenta de que la congruencia $a^p\equiv a\ (\text{mod }p)$ puede ser cierta sin cumplirse las condiciones del teorema. Por ejemplo, consideremos $p=341$ y $a=2$, que cumplen que $2^{341}-2=2((2^{10})^{34}-1)$ es múltiplo de $2^{10}-1=1023=3\cdot 341$. ¿Sabrías demostrar por qué es múltiplo $2^{10}-1$? (más adelante, responderemos a esta pregunta de forma más general).
Si $a\cdot c\equiv b\cdot c\ (\text{mod }m)$, nos preguntamos cuándo podemos eliminar $c$ y deducir que $a\equiv b\ (\text{mod }m)$. Como acabamos de ver esto no es cierto en general, pero será cierto siempre que exista un número entero $d$ tal que $c\cdot d\equiv 1\ (\text{mod }m)$ ya que bastará multiplicar la congruencia inicial por este número para obtener la simplificación deseada. A un número $d$ que cumpla esta condición se le llama inverso de $c$ módulo $m$.
Por tanto, si $ab\equiv ac\ (\text{mod }m)$ y $\mathrm{mcd}(a,m)=1$, entonces $b\equiv c\ (\text{mod }m)$.
Esto nos permite dar una segunda versión del Teorema pequeño de Fermat para cuanado $\mathrm{mcd}(a,p)=1$, es decir, cuando $a$ no es múltiplo de $p$ porque en tal caso la caracterización anterior nos permite simplificar $a$. No obstante, vamos a dar una demostración alternativa.
Hemos visto cómo manejar bastante bien las congruencias en lo que se refiere a los números involucrados, pero ¿qué ocurre si queremos hacer operaciones con los módulos? La respuesta no es tan fácil como en el otro caso pero algo se puede hacer.
Comencemos respondiendo a una pregunta: ¿Qué nos da más información, decir que $a\equiv 7\ (\text{mod }15)$ o decir que $a\equiv 7\ (\text{mod }30)$? Si lo piensas un momento, los números positivos congruentes con $7$ módulo $15$ son $7$, $22$, $37$, $52$, $67$,... mientras que los congruentes con $7$ módulo $30$ son $7$, $37$, $67$, $97$,... Por tanto, hay menos números que verifiquen la segunda afirmación en el sentido de que todos lo que verifican la segunda, también verifican la primera. Es por ello que la afirmación $a\equiv 7\ (\text{mod }30)$ da más información que la misma con módulo $15$. Veamos esto con más rigor en el siguiente resultado.
Este truco es muy cómodo pues siempre podemos sustituir el módulo por un divisor suyo (¡pero también perdemos información!). El proceso contrario (sustituirlo por un múltiplo) no es válido en general pues, siguiendo con los ejemplos anteriores, $22\equiv 7\ (\text{mod }15)$ pero $22\not\equiv 7\ (\text{mod }30)$.
Veamos otro ejemplo. Supongamos que $a\equiv 1\ (\text{mod }3)$ y queremos estudiar qué ocurre con $a$ módulo $12$. Que $a\equiv 1\ (\text{mod }3)$ quiere decir que existe $k\in\mathbb{Z}$ tal que $a=3k+1$ y ahora $k$ será de la forma $4h+j$, donde $j$ es uno de los números $\{0,1,2,3\}$, luego $a=3k+1=12h+3j+1$. Tomando módulo $12$ llegamos a que $a\equiv 3j+1\ (\text{mod }12)$ y, sustituyendo por $j$ por los valores $0,1,2,3$, tenemos que $a\equiv 1\ (\text{mod }12)$ ó $a\equiv 4\ (\text{mod }12)$ ó $a\equiv 7\ (\text{mod }12)$ ó $a\equiv 10\ (\text{mod }12)$. Estas son las cuatro posibilidades de $a$ módulo $12$. El ejemplo es suficiente para entenderlo pero vamos a intentar expresarlo de forma rigurosa (la demostración la dejamos al lector).
Para fijar ideas, veamos un ejemplo donde puede aplicarse. Cuando estudiemos más adelante ecuaciones con congruencias y el Teorema Chino del Resto, veremos una generalización de todas estas ideas.
Utilizando las ideas anteriores y viendo que $30=2\cdot 3\cdot 5$, intentemos calcular el resto de dividir $p^2$ entre $2$, $3$ y $5$. Como $p^2$ es impar, se tiene que $p^2\equiv 1\ (\text{mod } 2)$ y, como no es múltiplo de $3$, se tiene que $p^2\equiv 1\ (\text{mod } 3)$. La primera congruencia nos lleva a que, módulo $6$, $p^2$ es congruente con $1$, $3$ ó $5$ y la segunda a que lo es con $1$ ó con $4$ luego la única posibilidad es que $p^2\equiv 1\ (\text{mod } 6)$ de donde, módulo $30$, $p^2$ puede ser congruente con $1$, $7$, $13$, $19$ ó $25$. Finalmente, como $p^2$ no es múltiplo de $5$, deducimos que $p^2\equiv 1$ ó $p^2\equiv 4\ (\text{mod } 5)$ y, de las posibilidades anteriores, sólo quedan $1$ y $19$, como queríamos probar.
En primer lugar, vamos a utilizar las congruencias para obtener criterios de divisibilidad. Todo el mundo sabe que un número es múltiplo de $2$ cuando su última cifra es par, o es múltiplo de $5$ cuando su última cifra es $0$ ó $5$. Aquí vamos a ver criterios para decidir rápidamente si un número es múltiplo de $9$ y de $11$ y dejaremos algunos ejercicios propuestos para otros números.
En cualquier caso, si tomamos un número natural $N$ y lo expresamos en base $10$ (en el sistema decimal), podremos escribirlo como \[N=a_0+10\cdot a_1+100\cdot a_2+\cdots+10^n\cdot a_n.\] En otras palabras, $a_0$ es la cifra de las unidades, $a_1$ la de las decenas, $a_2$ la de las centenas, y así sucesivamente.
Para dar otra aplicación vamos a intentar usar las congruencias para calcular las últimas cifras de un número. Está claro que la última cifra de un número es su resto módulo $10$, las dos últimas su resto módulo $100$ y, en general, las $k$ últimas cifras su resto módulo $10^k$. Veamos un ejemplo en el que se usa esta técnica.