Introducción
En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo y vimos algunos problemas. La gran ventaja de trabajar en
, o bien, de trabajar módulo
, es que para
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 al dividirse entre
.
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:
De esta forma,



Trabajando de esta forma, podemos encontrar el residuo al dividirse por 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 en cierto módulo
.
Ejemplo. Imagina que tomamos al número y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre
. Tenemos, trabajando módulo
:
Nota que podríamos seguir, poniendo . Pero podemos ahorrarnos trabajo pues
, en donde usamos que ya sabíamos que
. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener
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: . Notemos que si la potencia es múltiplo de
, entonces el residuo será
, es decir,
. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos,
entre
, basta ver que módulo
tenemos
en donde estamos usando lo que mencionamos para y que ya hicimos
módulo
.
A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo , 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
. Dice que la potencia
funciona para esto.
Teorema. Si es un número primo y
no divide a
, entonces
divide a
o, dicho en otras palabras
.
Demostración. Afirmamos que los números ,
,
,
,
dejan todos ellos residuos distintos al dividirse entre
y, además, que ninguno de esos residuos es
. Probemos esto. Tomemos
. En una entrada anterior vimos que
tiene inverso en
. Sea
su inverso. Si
, entonces multiplicando por
de ambos lados tendríamos
Pero como y
están entre
y
, esto implica que
. Ninguno es cero pues si
, entonces al multiplicar por
tendríamos la contradicción
. Esto muestra la afirmación.
Así, usando la afirmación en el segundo paso de la siguiente cadena módulo , tenemos:
El número no es divisible entre
, pues es producto de puros números menores que
, de modo que
, así que tiene inverso módulo
, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos:
Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.
Problema. Demuestra que divide a
Solución. Notemos primero que es primo y que no divide ni a
ni a
. Por el pequeño teorema de Fermat, tenemos módulo
que
y que
. Así, módulo
tenemos que
De esta forma, , es decir,
divide a
Teorema de Wilson
En la demostración del teorema de Fermat aparece la expresión . ¿Qué residuo dejará al dividirse entre
? Hagamos una prueba.
Problema. Encuentra el residuo que se obtiene al dividir entre
.
Solución. Para no trabajar con números tan grandes, notemos que en







es decir, el residuo que deja al dividirse entre
es
.
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 . Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.
Proposición. Sea un número primo. Los únicos elementos en
que son inversos de sí mismos son
y
.
Demostración. Claramente y
son inversos multiplicativos de sí mismos, pues
. Ahora, si tenemos
tal que
es inverso multiplicativo de sí mismo, tenemos que
, que por definición quiere decir que
divide a
. Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces
divide a
o a
, y obtenemos, respectivamente, que
o que
, como queríamos.
Estamos listos para enunciar y demostrar el teorema de Wilson.
Teorema. Si es un número primo, entonces
divide a
o, dicho en otras palabras,
.
Demostración. Si , el resultado es inmediato. Supongamos que
. En
aparecen todos los números de
a
. Todos ellos son primos relativos con
, así que tienen inverso módulo
. Ese inverso también aparece en
. Así, podemos agrupar esos números en
parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el
y el
. De esta forma,
en donde en la expresión intermedia tenemos un , un
y
unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.
Veamos una posible aplicación.
Problema. Determina el residuo que se obtiene al dividir entre
.
Solución. Notemos que divide a
, así que
. Por el teorema de Wilson,
. Podemos multiplicar esa igualdad por
para obtener módulo
que

Una solución alternativa es darse cuenta de que
