Introducción
En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo $n$ y vimos algunos problemas. La gran ventaja de trabajar en $\mathbb{Z}_n$, o bien, de trabajar módulo $n$, es que para $n$ pequeña hay una cantidad pequeña de elementos y entonces las operaciones se vuelven muy sencillas.
Problema. Determina cuál es el residuo obtenido de dividir $705\cdot 702+714\cdot 711$ al dividirse entre $7$.
Solución. Tenemos que $705$, $702$, $714$ y $711$ los podemos poner como un múltiplo de $7$ más un residuo como sigue: $700+5$, $700+2$ y $714=714+0$, $711=707+4$. Así, $705\equiv 5\pmod 7$, $702\equiv 2 \pmod 7$, $714\equiv 0 \pmod 7$ y $711\equiv 4 \pmod 7$. Así, trabajando módulo $7$ tenemos que:
\begin{align*}
705\cdot 702+714\cdot 711 \equiv 5\cdot 2 + 0\cdot 4 \equiv 10 + 0 \equiv 10 \equiv 3 \pmod 7
\end{align*}
De esta forma, $705\cdot 702+714\cdot 711$ deja residuo $3$ al dividirse entre $7$.
$\square$
Trabajando de esta forma, podemos encontrar el residuo al dividirse por $n$ de expresiones que involucran sumas y productos. El objetivo de esta entrada es entender qué sucede cuando queremos encontrar el residuo de expresiones que tienen potencias y factoriales.
Pequeño teorema de Fermat
Intentemos entender qué sucede con las potencias de un número $a$ en cierto módulo $n$.
Ejemplo. Imagina que tomamos al número $3$ y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre $7$. Tenemos, trabajando módulo $7$:
\begin{align*}
3^0\equiv 1\\
3^1\equiv 3\\
3^2\equiv 9 \equiv 2\\
3^3=27\equiv 21+6\equiv 6
\end{align*}
Nota que podríamos seguir, poniendo $3^4=81$. Pero podemos ahorrarnos trabajo pues $3^4\equiv 3\cdot 3^3 \equiv 3 \cdot 6 \equiv 18\equiv 4$, en donde usamos que ya sabíamos que $3^3\equiv 6$. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener
\begin{align*}
3^5\equiv 3\cdot 4\equiv 12\equiv 5\\
3^6\equiv 3\cdot 5 = 15\equiv 1\\
3^7\equiv 3\cdot 1 = 3\\
3^8\equiv 3\cdot 3 = 9 \equiv 2
\end{align*}
Podríamos seguir y seguir, pero ya no tiene mucho caso. A partir de aquí es fácil convencerse de que los residuos se ciclan: $1,3,2,6,4,5,1,3,2,6,4,5,1\ldots$. Notemos que si la potencia es múltiplo de $6$, entonces el residuo será $1$, es decir, $3^{6k}\equiv 1 \pmod 7$. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos, $3^{605}$ entre $7$, basta ver que módulo $7$ tenemos $$3^{605}=3^{600}\cdot 3^5 \equiv 1\cdot 5 \equiv 5,$$
en donde estamos usando lo que mencionamos para $k=100$ y que ya hicimos $3^5$ módulo $7$.
A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo $a^m\equiv 1\pmod n$, pues en ese momento las potencias “se empiezan a ciclar”. El pequeño teorema de Fermat es un resultado que podemos aplicar cuando trabajamos módulo un número primo $p$. Dice que la potencia $p-1$ funciona para esto.
Teorema. Si $p$ es un número primo y $p$ no divide a $a$, entonces $p$ divide a $a^{p-1}-1$ o, dicho en otras palabras $a^{p-1}\equiv 1 \pmod p$.
Demostración. Afirmamos que los números $a$, $2a$, $3a$, $\ldots$, $(p-1)a$ dejan todos ellos residuos distintos al dividirse entre $p$ y, además, que ninguno de esos residuos es $0$. Probemos esto. Tomemos $0<i<j<p-1$. En una entrada anterior vimos que $[a]_p$ tiene inverso en $Z_p$. Sea $[b]_p$ su inverso. Si $[ia]_p=[ja]_p$, entonces multiplicando por $[b]_p$ de ambos lados tendríamos $$[i]_p=[i(ab)]_p=[j(ab)]_p=[j]_p.$$
Pero como $i$ y $j$ están entre $1$ y $p-1$, esto implica que $i=j$. Ninguno es cero pues si $[ia]_p=[0]_p$, entonces al multiplicar por $b$ tendríamos la contradicción $[i]_p=[i(ab)]_p=[0b]_p=[0]_p$. Esto muestra la afirmación.
Así, usando la afirmación en el segundo paso de la siguiente cadena módulo $p$, tenemos:
\begin{align*}
(p-1)! a^{p-1} &= (a)(2a)(3a)\cdots((p-1)a)\\
&\equiv 1\cdot 2 \cdot \ldots \cdot (p-1)\\
&= (p-1)!.
\end{align*}
El número $(p-1)!$ no es divisible entre $p$, pues es producto de puros números menores que $p$, de modo que $\text{MCD}(p, (p-1)!)=1$, así que tiene inverso módulo $p$, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos: $$a^{p-1}\equiv 1 \pmod p.$$
$\square$
Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.
Problema. Demuestra que $13$ divide a $25^{181}-181^{25}$
Solución. Notemos primero que $13$ es primo y que no divide ni a $25$ ni a $181$. Por el pequeño teorema de Fermat, tenemos módulo $13$ que $25^{12}\equiv 1$ y que $181^{12}\equiv 1$. Así, módulo $13$ tenemos que $$25^{181}\equiv 25^{15\cdot 12}\cdot 25 \equiv 25 \equiv 12,$$ y que $$181^{25}\equiv 181^{2\cdot 12}\cdot 181\equiv 181 \equiv 12.$$
De esta forma, $25^{181}-181^{25}\equiv 12-12\equiv 0\pmod {13}$, es decir, $13$ divide a $25^{181}-181^{25}$
$\square$
Teorema de Wilson
En la demostración del teorema de Fermat aparece la expresión $(p-1)!$. ¿Qué residuo dejará al dividirse entre $p$? Hagamos una prueba.
Problema. Encuentra el residuo que se obtiene al dividir $10!$ entre $11$.
Solución. Para no trabajar con números tan grandes, notemos que en $$10!=1\cdot 2\cdot 3\cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10$$ podemos cambiar a $6,7,8,9,10$ por $-5, -4, -3, -2, -1$ al trabajar módulo $11$, así que basta encontrar $-(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2$ módulo $11$. Notemos que $3\cdot 4\equiv 12 \equiv 1 \pmod {11}$ y que $2\cdot 5 =10 \equiv -1 \pmod {11}$. Así, $$10!\equiv -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 \equiv -(1\cdot 1 \cdot -1)^2 \equiv -1 \equiv 10 \pmod {11},$$
es decir, el residuo que deja $10!$ al dividirse entre $11$ es $10$.
$\square$
El teorema de Wilson ayuda a cuando queremos encontrar el residuo de un factorial al dividirse entre un número primo. Una de las ideas del ejercicio anterior fue buena: nos conviene agrupar a números del factorial en productos sencillos. Lo más conveniente es que agrupemos a cada número con su inverso multiplicativo, pues así obtendremos un $1$. Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.
Proposición. Sea $p$ un número primo. Los únicos elementos en $\mathbb{Z}_p$ que son inversos de sí mismos son $[1]_p$ y $[p-1]_p$.
Demostración. Claramente $[1]_p$ y $[p-1]_p=[-1]_p$ son inversos multiplicativos de sí mismos, pues $1\cdot 1=1=(-1)\cdot(-1)$. Ahora, si tenemos $a$ tal que $a$ es inverso multiplicativo de sí mismo, tenemos que $[a^2]_p\equiv [1]_p$, que por definición quiere decir que $p$ divide a $a^2-1=(a+1)(a-1)$. Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces $p$ divide a $a+1$ o a $a-1$, y obtenemos, respectivamente, que $[a]_p=[-1]_p=[p-1]_p$ o que $[a]_p=[1]_p$, como queríamos.
$\square$
Estamos listos para enunciar y demostrar el teorema de Wilson.
Teorema. Si $p$ es un número primo, entonces $p$ divide a $(p-1)!+1$ o, dicho en otras palabras, $(p-1)!\equiv -1 \pmod p$.
Demostración. Si $p=2$, el resultado es inmediato. Supongamos que $p\geq 3$. En $(p-1)!$ aparecen todos los números de $1$ a $p-1$. Todos ellos son primos relativos con $p$, así que tienen inverso módulo $p$. Ese inverso también aparece en $(p-1)!$. Así, podemos agrupar esos números en $(p-3)/2$ parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el $1$ y el $-1$. De esta forma, $$(p-1)!\equiv (1)(-1)(1\cdot 1\cdot \ldots\cdot 1) \equiv -1 \pmod p,$$
en donde en la expresión intermedia tenemos un $1$, un $-1$ y $(p-3)/2$ unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.
$\square$
Veamos una posible aplicación.
Problema. Determina el residuo que se obtiene al dividir $15!+16!+17!$ entre $17$.
Solución. Notemos que $17$ divide a $17!$, así que $17!\equiv 0 \pmod {17}$. Por el teorema de Wilson, $16!\equiv -1 \pmod {17}$. Podemos multiplicar esa igualdad por $-1$ para obtener módulo $17$ que $$15! = 15! (-1)(-1) \equiv 15! \cdot 16 \cdot (-1) \equiv 16! (-1)\equiv (-1)(-1)\equiv 1.$$ Así, $15!+16!+17!\equiv 1 + (-1) + 0 \equiv 0 \pmod {17}$.
$\square$
Una solución alternativa es darse cuenta de que $$15!+16!+17!=15!(1+16)+17\cdot 16!=17\cdot (15!+16!)$$ y por lo tanto es múltiplo de $17$. Aunque tengamos herramientas fuertes, ¡siempre hay que recordar los básicos!