Álgebra Superior II: Teoremas de Fermat y de Wilson

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!

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Álgebra Superior II: Teoremas de Fermat y de Wilson

Introducción

Pequeño teorema de Fermat

Teorema de Wilson

Deja una respuesta Cancelar la respuesta

Introducción

Pequeño teorema de Fermat

Teorema de Wilson

Comparte esto:

Deja una respuesta Cancelar la respuesta