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(\mathrm{mod}7)$, $702\equiv 2(\mathrm{mod}7)$, $714\equiv 0(\mathrm{mod}7)$ y $711\equiv 4(\mathrm{mod}7)$. Así, trabajando módulo $7$ tenemos que:

$$\begin{array}{r}705\cdot 702+714\cdot 711\equiv 5\cdot 2+0\cdot 4\equiv 10+0\equiv 10\equiv 3(\mathrm{mod}7)\end{array}$$
De esta forma, $705\cdot 702+714\cdot 711$ deja residuo $3$ al dividirse entre $7$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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{array}{r}{3}^0\equiv 1\\ 3^1\equiv 3\\ 3^2\equiv 9\equiv 2\\ 3^3=27\equiv 21+6\equiv 6\end{array}$$

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{array}{r}{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{array}$$

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\dots$. Notemos que si la potencia es múltiplo de $6$, entonces el residuo será $1$, es decir, $3^{6k}\equiv 1(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}p)$.

Demostración. Afirmamos que los números $a$, $2a$, $3a$, $\dots$, $(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{array}{rl}(p-1)!a^{p-1}& =(a)(2a)(3a)\cdots ((p-1)a)\\ & \equiv 1\cdot 2\cdot \dots \cdot (p-1)\\ & =(p-1)!.\end{array}$$

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(\mathrm{mod}p).$$

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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(\mathrm{mod}13)$, es decir, $13$ divide a ${25}^{181}-{181}^{25}$

$\mathrm{△}$

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(\mathrm{mod}11)$ y que $2\cdot 5=10\equiv -1(\mathrm{mod}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(\mathrm{mod}11),$$

es decir, el residuo que deja $10!$ al dividirse entre $11$ es $10$.

$\mathrm{△}$

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.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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(\mathrm{mod}p)$.

Demostración. Si $p=2$, el resultado es inmediato. Supongamos que $p\ge 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 \dots \cdot 1)\equiv -1(\mathrm{mod}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.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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(\mathrm{mod}17)$. Por el teorema de Wilson, $16!\equiv -1(\mathrm{mod}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(\mathrm{mod}17)$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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!

Más adelante…

Tarea moral

Entradas relacionadas

• Ir a: Álgebra Superior II
• Entrada anterior del curso: Problemas de congruencias y \mathbb{Z}_n
• Entrada siguiente del curso: Problemas que usan teoremas de Fermat y Wilson

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»