Teoremas de Euler, de Fermat y de Wilson

Contenido

Teoremas de Euler, de Fermat y de Wilson#

Introducción#

En este capítulo vamos a ver tres teoremas que nos ayudan a comprender un poco mas los números primos y que también son la base para desarrollos en criptografía.
El teorema de Wilson nos da una caracterización de los números primos en términos de factoriales. Aunque su aplicación directa en la práctica puede ser limitada debido a la complejidad de los cálculos factoriales, su importancia teórica es innegable.
El teorema de Fermat o el pequeño teorema de Fermat es uno de los resultados más importantes y utilizados en la teoría de números. Esta simple pero profunda afirmación tiene implicaciones en el campo de la criptografía.
El teorema de Euler, generaliza el resultado de Fermat. Veremos la demostración de estos teoremas y algunos ejercicios relacionados con éstos.

Teorema de Fermat#

Para la demostración del teorema de Fermat vamos a necesitar el siguiente lema que está relacionado con los sistemas de residuos completos.

Lema 10

Sean \(p\) un número primo y \(a\) un entero tales que \(p \nmid a\). Entonces los residuos mínimos de los enteros \(a,2a,3a, \ldots ,(p-1)a\) módulo \(p\) son una permutación de los enteros \(1,2,3, \ldots , p-1\).

Demostración. La demostración de este lema es la misma que la de la Proposición 27. Como \(p\) es un primo, sus únicos divisores son \(1\) y \(p\). Como \(p\nmid a\), sucede que el único divisor que tienen en común \(p\) y \(a\) es \(1\) y por lo tanto \((p,a) = 1\), es decir que son primos relativos. Luego, por la Proposición 26, sabemos que lo enteros \(a,2a,3a, \ldots ,(p-1)a\) dejan todos los posibles residuos, es decir, \(1,2,3, \ldots , p-1\) al dividirlos entre \(p\). \(\square\)

Ejemplo 99

Veamos un ejemplo del Lema 10.

Si tomamos \(p = 11\) y \(a = 16\), es claro que \(p \nmid a\). Entonces tendríamos lo siguiente,

\[\begin{align*} 1\cdot 16 = 16 &\equiv 5 \pmod{11}, & 6\cdot 16 = 96 &\equiv 8 \pmod{11}, \\ & \\ 2\cdot 16 = 32 &\equiv 10 \pmod{11}, & 7\cdot 16 = 112 &\equiv 2 \pmod{11}, \\ & \\ 3\cdot 16 = 48 &\equiv 4 \pmod{11}, & 8\cdot 16 = 128 &\equiv 7 \pmod{11}, \\ & \\ 4\cdot 16 = 64 &\equiv 9 \pmod{11}, & 9\cdot 16 = 144 &\equiv 1 \pmod{11}, \\ & \\ 5\cdot 16 = 80 &\equiv 3 \pmod{11}, & 10\cdot 16 = 160 &\equiv 6 \pmod{11}. \\ & \\ \end{align*}\]

Por lo tanto los residuos mínimos de los números \(1\cdot 16, 2\cdot 16, 3\cdot 16, 4\cdot 16, 5\cdot 16, 6\cdot 16, 7\cdot 16, 8\cdot 16, 9\cdot 16, 10\cdot 16\) módulo \(11\) son los mismos que \(1,2,3,4,5,6,7,8,9,10\) en algún orden.

Pasemos a enunciar el teorema de Fermat o también conocido como el pequeño teorema de Fermat.

Teorema 35 (Teorema de Fermat)

Sea \(p\) un número primo y \(a\) un entero tal que \(p\nmid a\). Entonces,

\[a^{p-1} \equiv 1 \pmod{p}.\]

Demostración. Gracias al Lema 10 tenemos que los residuos mínimos de los enteros \(a,2a,3a, \ldots , (p-1)a\) módulo \(p\) son los mismos que \(1,2,3, \ldots , p-1\) en algún orden. Entonces por la propiedad \(3\) del Teorema 32 aplicada repetidas veces tendríamos que

\[\begin{align*} a\cdot 2a\cdot 3a\cdot \ldots \cdot (p-1)a &\equiv 1\cdot 2\cdot 3\cdot \ldots \cdot (p-1) \pmod{p}, \\ & \\ [1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)]a^{p-1} &\equiv (p-1)! \pmod{p}, \\ & \\ (p-1)! a^{p-1} &\equiv (p-1)! \pmod{p}. \\ \end{align*}\]

Pero como \(((p-1)!, p) = 1\) por el Corolario 9 podemos concluir que \(a^{p-1} \equiv 1 \pmod{p}\). \(\square\)

Ejemplo 100

Aprovechemos las cuentas realizadas en el Ejemplo 99 para aclarar lo que sucede en la demostración del teorema de Fermat.

Recordemos que para \(p = 11\) y \(a = 16\), teníamos que

\[\begin{align*} 1\cdot 16 = 16 &\equiv 5 \pmod{11}, & 6\cdot 16 = 96 &\equiv 8 \pmod{11}, \\ & \\ 2\cdot 16 = 32 &\equiv 10 \pmod{11}, & 7\cdot 16 = 112 &\equiv 2 \pmod{11}, \\ & \\ 3\cdot 16 = 48 &\equiv 4 \pmod{11}, & 8\cdot 16 = 128 &\equiv 7 \pmod{11}, \\ & \\ 4\cdot 16 = 64 &\equiv 9 \pmod{11}, & 9\cdot 16 = 144 &\equiv 1 \pmod{11}, \\ & \\ 5\cdot 16 = 80 &\equiv 3 \pmod{11}, & 10\cdot 16 = 160 &\equiv 6 \pmod{11}. \\ & \\ \end{align*}\]

Entonces tenemos que

\[\begin{align*} (1\cdot 16)(2\cdot 16)(3\cdot 16)\cdot \ldots \cdot(8\cdot 16)(9\cdot 16)(10\cdot 16) &\equiv 1\cdot 2\cdot 3\cdot \ldots \cdot 8\cdot 9\cdot 10 \pmod{11}, \\ & \\ (1\cdot 2\cdot \ldots \cdot 9\cdot 10)16^{10} &\equiv 10! \pmod{11}, \\ & \\ 10!\cdot 16^{10} &\equiv 10! \pmod{11}, \\ & \\ 16^{10} &\equiv 1 \pmod{11}. \end{align*}\]

Veamos los siguientes resultados relacionados con el teorema de Fermat.

Teorema 36

Sea \(p\) un número primo y \(a\) cualquier entero tal que \(p \nmid a\). Entonces, \(a^{p-2}\) es un inverso de \(a\) módulo \(p\).

Demostración. Por el Teorema 35 de Fermat tenemos que \(a^{p-1} \equiv 1 \pmod{p}\). Entonces tendríamos que \(a\cdot a^{p-2} \equiv 1 \pmod{p}\), por lo tanto \(a^{p-2}\) es un inverso de \(a\) módulo \(p\). \(\square\)

Teorema 37

Sea \(p\) un número primo y \(a\) cualquier entero. Entonces, \(a^p \equiv a \pmod{p}\).

Demostración. Procedamos por casos.

Caso \(1\).

Supongamos que \(p \nmid a\). Entonces por el Teorema 35 de Fermat se cumple que \(^{p-1} \equiv 1 \pmod{p}\). Luego podemos multiplicar por \(a\) ambos lados de la congruencia y obtenemos que \(a^p \equiv a \pmod{p}\).

Caso \(2\).

Supongamos que \(p|a\). Entonces tenemos que \(p\equiv a \equiv 0 \pmod{p}\). Luego por el Teorema 33 tendríamos que \(a^p \equiv 0 \pmod{p}\).
Luego por el Teorema 29 tenemos la propiedad de reflexividad y transitividad para \(\equiv\). Entonces tenemos que \(a^p \equiv 0 \pmod{p}\) y \(0 \equiv a \pmod{p}\). Por lo tanto \(a^p \equiv a \pmod{p}\). \(\square\)

Teorema de Euler#

En la Definición 21 vimos la función \(\varphi(n)\) Euler, la cual nos dice el número de enteros positivos menores o iguales que \(n\) que son primos relativos con \(n\). En esta sección vamos a usar la función \(\varphi(n)\) en el enunciado del teorema de Euler.
Vamos a ver algunos resultados previos que nos servirán para la demostración del teorema de Euler.

Como vimos en la Definición 34, en un sistema de residuos reducido con respecto a \(n\) se cumple que para cada \(r_i\) en el sistema, \((r_i, n) = 1\). Si recordamos la Definición 21 de la función de Euler, entonces tendríamos que el número de elementos que tiene el sistema de residuos reducido con respecto a \(n\) es \(\varphi(n)\). Veamos un ejemplo para ilustrar.

Ejemplo 101

Recordemos que \(\varphi(9) = 6\) y los elementos que son primos relativos con \(9\) son \(1,2,4,5,7,8\).
El conjunto \(\{1,2,4,5,7,8\}\) es un sistema de residuos reducido módulo \(9\). Podemos notar que ningún par de ellos es congruente módulo \(9\).

Teorema 38

Si \(r_1, r_2, \ldots ,r_{\varphi(n)}\) es un sistema de residuos reducido módulo \(n\) y \(a\) es un entero positivo tal que \((a,n) = 1\), entonces el conjunto \(ar_1, ar_2, \ldots ,ar_{\varphi(n)}\) es también un sistema de residuos reducido módulo \(n\).

Demostración. Primero vamos a demostrar que cada entero \(ar_j\) es primo relativo con \(n\), donde \(1 \le j \le \varphi(n)\). Y luego veremos que ningún \(ar_j\) es congruente módulo \(n\) con algún \(ar_k\), donde \(1 \le k \le \varphi(n)\).

Demostremos que cada entero \(ar_j\) es primo relativo con \(n\).

Para ello supongamos que \((ar_j, n) > 1\). Entonces por el Lema 1, tendríamos que existe un número primo \(p\) divisor de \((ar_j, n)\). De lo anterior tendríamos que \(p|ar_j\) y \(p|n\). Observemos que si \(p|ar_j\) pueden suceder dos cosas que \(p|a\) o \(p|r_j\).

Que \(p|a\) es imposible puesto que \((a,n) = 1\).

Por otro lado \(p|r_j\) y \(p|n\), tampoco podría suceder. Esto se debe a que \(r_j\) pertenece al conjunto del sistema de residuos reducido módulo \(n\), entonces debe suceder que \((r_j, n)= 1\).

Así, podemos concluir que \(ar_j\) y \(n\) son primos relativos, es decir que \((ar_j,n) = 1\) para \(j = 1,2,\ldots , \varphi(n)\).

Ahora demostremos que ningún \(ar_j\) es congruente módulo \(n\) con algún \(ar_k\).

Supongamos que \(ar_j \equiv ar_k \pmod{n}\), tales que \(j\) y \(k\) son enteros positivos distintos, donde \(1 \le j \le \varphi(n)\) y \(1 \le k \le \varphi(n)\). Luego, como \((a,n) = 1\), por el Corolario 9 tendríamos que \(r_j \equiv r_k \pmod{n}\). Esto es una contradicción ya que \(r_j\) y \(r_k\) pertenecen al conjunto del sistema de residuos reducido módulo \(n\). Por lo tanto \(ar_j \not\equiv ar_k \pmod{n}\). \(\square\)

Ejemplo 102

Siguiendo con la idea del Ejemplo 101 teníamos que el conjunto \(\{1,2,4,5,7,8\}\) es un sistema de residuos reducido módulo \(9\). Entonces por el Teorema 38 como \((2,9) = 1\) tendríamos que el conjunto \(\{1\cdot 2,2 \cdot 2 ,4 \cdot 2,5\cdot 2,7\cdot 2,8\cdot 2\} = \{2,4,8,10,14,16\}\) también es un sistema de residuos reducido módulo \(9\).

Pasemos a enunciar y demostrar el teorema de Euler.

Teorema 39 (Teorema de Euler)

Sea \(n\) un número entero positivo y \(a\) un entero tal que \((n,a)=1\). Entonces,

\[a^{\varphi(n)}\equiv 1\pmod n.\]

Demostración. Denotemos como \(r_1,r_2, \ldots , r_{\varphi(n)}\) al sistema de residuos reducido conformado por los enteros positivos menores que \(n\) y que son primos relativos con \(n\). Por el Teorema 38, como \((n,a) = 1\), entonces el conjunto \(ar_1,ar_2, \ldots , ar_{\varphi(n)}\) es también un sistema de residuos reducido módulo \(n\). Por lo tanto los residuos mínimos módulo \(n\) de los enteros \(ar_1,ar_2, \ldots , ar_{\varphi(n)}\) deben de ser los mismos que los enteros \(r_1,r_2, \ldots , r_{\varphi(n)}\) pero en algún orden diferente.
Entonces aplicamos la propiedad \(3\) del Teorema 32 repetidas veces y tendríamos que

\[\begin{align*} ar_1\cdot ar_2\cdot \ldots \cdot ar_{\varphi(n)} &\equiv r_1\cdot r_2\cdot \ldots \cdot r_{\varphi(n)} \pmod{n} \\ & \\ [r_1\cdot r_2\cdot \ldots \cdot r_{\varphi(n)}] a^{\varphi(n)} &\equiv r_1\cdot r_2\cdot \ldots \cdot r_{\varphi(n)} \pmod{n}. \end{align*}\]

Finalmente, como cada uno de los \(r_j\) es primo relativo con \(n\), tendríamos que \((r_1\cdot r_2\cdot \ldots \cdot r_{\varphi(n)},n) = 1\). Por lo tanto, por el Corolario 9 podemos concluir que \(a^{\varphi(n)} \equiv 1 \pmod{n}\). \(\square\)

Ejemplo 103

Veamos un ejemplo para aclarar la demostración del teorema de Euler.

En el Ejemplo 102 teníamos que los conjuntos \(\{1,2,4,5,7,8 \}\) y \(\{1\cdot 2,2 \cdot 2 ,4 \cdot 2,5\cdot 2,7\cdot 2,8\cdot 2\}\) son sistemas de residuos reducidos módulo \(9\). Comprobemos que sus elemento son congruentes módulo \(9\), en algún orden.

\[\begin{align*} 1\cdot 2 = 2 &\equiv 2 \pmod{9}, & 5\cdot 2 = 10 &\equiv 1 \pmod{9}, \\ & \\ 2\cdot 2 = 4 &\equiv 4 \pmod{9}, & 7\cdot 2 = 14 &\equiv 5 \pmod{9}, \\ & \\ 4\cdot 2 = 8 &\equiv 8 \pmod{9}, & 8\cdot 2 = 16 &\equiv 7 \pmod{9}. \\ \end{align*}\]

Entonces tenemos lo siguiente,

\[\begin{align*} (1 \cdot 2)\cdot (2 \cdot 2) \cdot (4 \cdot 2)\cdot (5 \cdot 2) \cdot (7 \cdot 2)\cdot (8 \cdot 2) \cdot &\equiv 1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8 \pmod{9} \\ & \\ (1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8)\cdot 2^6 &\equiv 1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8 \pmod{9}. \\ \end{align*}\]

Luego, como \((1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8,9) = 1\), concluimos que

\[2^6 = 2^{\varphi(9)} \equiv 1 \pmod{9}.\]

Teorema 40

Sea \(n\) un entero positivo y \(a\) cualquier entero tal que \((a,n) = 1\). Entonces \(a^{\varphi(n) - 1}\) es un inverso de \(a\) módulo \(n\).

Demostración. Como \((a,n) = 1\) por el Teorema 39 de Euler tenemos que \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Entonces tendríamos que \(aa^{\varphi(n) -1} \equiv 1 \pmod{n}\). Por lo tanto \(a^{\varphi(n) - 1}\) es un inverso de \(a\) módulo \(n\). \(\square\)

Código para implementar el teorema de Euler#

Vamos a necesitar el código que hicimos en el capítulo de la función de Euler, el cual calculaba el valor de la función \(\varphi(n)\).

def factorizar_en_primos(n):
    lst = []
    for i in range(2, n+1):
        while n % i == 0:
            lst.append(i)
            n //= i
        if n == 1:
            break
    return lst

def phi_euler(n):
    resultado = n
    sin_repetir = list(set(factorizar_en_primos(n)))
    for i in sin_repetir:
        resultado *= (1 - 1/ i)
    return int(resultado)

Además, como tenemos que calcular el máximo común divisor de dos números, usaremos el código que hicimos en la sección del algoritmo de Euclides para calcular el máximo común divisor.

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return b

Ahora que tenemos lo necesario, lo que haremos será un código que nos calcule si dado \(a\) y \(n\) enteros positivos se cumple que \(a^{\varphi(n)} \equiv 1 \pmod{n}\).

def thm_euler(a,n):
    d = algoritmo_euclides(a,n)
    if d == 1:
        print(f"Se cumple que {a}^{phi_euler(n)} ≡ {pow(a,phi_euler(n),n)} (mod {n})")
    else:
        print(f"No se cumple que {a} y {n} sean primos relativos ya que ({a},{n}) = {d}")

thm_euler(2,9)

Se cumple que 2^6 ≡ 1 (mod 9)

thm_euler(34,1973)

Se cumple que 34^1972 ≡ 1 (mod 1973)

thm_euler(45,87520724)

Se cumple que 45^42251328 ≡ 1 (mod 87520724)

thm_euler(14,87654)

No se cumple que 14 y 87654 sean primos relativos ya que (14,87654) = 14

Teorema de Wilson#

Vamos a probar un lema relacionado con la Definición 39, que nos será de ayuda para la demostración del teorema de Wilson.

Lema 11

Sea \(p\) un número primo. Un entero positivo \(a\) es inverso de sí mismo módulo \(p\) si y sólo si \(a \equiv 1 \pmod{p}\) o \(a \equiv -1 \pmod{p}\).

Demostración. Demostremos las dos implicaciones.

Primero supongamos que \(a\) es inverso de sí mismo módulo \(p\).

Por la Definición 39 tenemos que \(a^2 \equiv 1 \pmod{p}\), es decir que \(p|(a^2 -1)\). En otras palabras \(p|(a+1)(a-1)\). Luego por el Lema 3 tenemos que \(p|(a+1)\) o \(p|(a-1)\).

En el primer caso, como \(p|(a+1)\) tenemos que \(p|a-(-1)\) y concluimos que \(a \equiv -1 \pmod{p}\).

Análogamente, si \(p|(a-1)\), entonces \(a \equiv 1 \pmod{p}\).

Por lo tanto \(a \equiv 1 \pmod{p}\) o \(a \equiv -1 \pmod{p}\).

Ahora supongamos que \(a \equiv \pm 1 \pmod{p}\).

Por el Teorema 33 podemos tomar \(a \equiv 1 \pmod{p}\) y aplicamos el teorema con \(k=2\) entonces tendríamos que \(a^2 \equiv 1 \pmod{p}\). De la misma manera, si tenemos que \(a \equiv -1 \pmod{p}\) y aplicamos el teorema con \(k=2\) también obtendríamos el mismo resultado \(a^2 \equiv 1 \pmod{p}\).

Por lo tanto, en cualquiera de los dos casos tenemos que \(a\) es inverso de sí mismo. \(\square\)

Antes de pasar a enunciar y demostrar el teorema de Wilson, veamos un ejemplo que nos ayudará a entender la demostración.

Ejemplo 104

Tomemos \(p = 13\), queremos ver cuál es el residuo cuando \((p-1)!\) es dividido entre \(p\).

Tenemos que \((p-1)! = (13-1)! = 12! = 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\).

Sabemos por el Teorema 34 que los números \(2,3,4,5,6,7,8,9,10,11,12\) tienen inverso, ya que como \(13\) es primo, todos ellos son primos relativos con \(13\). Por otro lado, por el Lema 11 tenemos que \(12 \equiv -1 \pmod{13}\) y \(1 \equiv 1 \pmod{13}\) por lo tanto el inverso de \(12\) es él mismo y el inverso de \(1\) también es él mismo.

Notemos que los inversos son:

\[\begin{align*} 2 \cdot 7 = 14 &\equiv 1 \pmod{13}, \\ & \\ 3 \cdot 9 = 27 &\equiv 1 \pmod{13}, \\ & \\ 4 \cdot 10 = 40 &\equiv 1 \pmod{13}, \\ & \\ 5 \cdot 8 = 40 &\equiv 1 \pmod{13},\\ & \\ 6 \cdot 11 = 66 &\equiv 1 \pmod{13}. \\ \end{align*}\]

Reordenemos los números en el factorial para simplificar las cuentas:

\[\begin{align*} (p-1)! &= (13-1)! = 12! \\ & \\ &= 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12 \\ & \\ &= 1 \cdot (2 \cdot 7) \cdot (3 \cdot 9) \cdot (4 \cdot 10) \cdot (5 \cdot 8) \cdot (6 \cdot 11) \cdot 12 \\ & \\ &\equiv 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot (12) \pmod{13} \\ & \\ &\equiv 12 \pmod{13} \\ & \\ &\equiv -1 \pmod{13}. \end{align*}\]

Entonces tenemos que \((13 - 1)! \equiv -1 \pmod{13}\).

Teorema 41 (Teorema de Wilson)

Si \(p\) es un número primo, entonces

\[(p-1)!\equiv -1\pmod p.\]

Demostración. Primero veamos que para \(p=2\), tenemos que \((p-1)! = (2-1)! = 1! = 1 \equiv -1 \pmod{2}\), por lo tanto el teorema se cumple para \(p=2\).

Entonces tomemos \(p>2\). Luego por el Teorema 34 sabemos que los números \(2,3,4, \ldots , p-2, p-1\) son invertibles ya que todos ellos son primos relativos con \(p\). Además por el Lema 11 tenemos que \(1\) y \(p-1\) son inversos de sí mismos.
Entonces si tomamos los números desde el \(2\) hasta \(p-2\) podemos formar \(\frac{p-3}{2}\) parejas de inversos, es decir que para cada \(a \in \{2,3, \ldots , p-2 \}\) existe \(b \in \{2,3, \ldots , p-2 \}\) tal que \(ab \equiv 1 \pmod{p}\), en donde \(a \neq b\).

Así, tenemos lo siguiente

\[2\cdot 3 \cdot \ldots \cdot (p-2) \equiv 1 \pmod{p}.\]

Luego por la propiedad \(3\) del Teorema 30 multiplicamos \(1\cdot (p-1)\) en ambos lados de la congruencia

\[\begin{align*} 1 \cdot 2\cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) &\equiv 1\cdot 1 \cdot (p-1) \pmod{p}, \\ & \\ (p-1)! &\equiv (p-1) \pmod{p}, \\ & \\ (p-1)! &\equiv -1 \pmod{p}. \end{align*}\]

Por lo tanto, se cumple que \((p-1)!\equiv -1\pmod p\). \(\square\)

Vamos a ver que el inverso del Teorema 41 también es cierto.

Teorema 42

Si \(n\) es un entero positivo tal que \((n-1)! \equiv -1 \pmod{n}\), entonces \(n\) es un número primo.

Demostración. Procedamos por contradicción.

Supongamos que \(n\) es un número compuesto, es decir que \(n = ab\), donde \(1 < a,b < n\).

Como \(n = ab\) y \(b\) es un entero, tenemos que \(a|n\). Luego, como \((n-1)! \equiv -1 \pmod{n}\), por definición tendríamos que \(n|[(n-1)! + 1]\). Por la propiedad \(2\) de la Proposición 2 tenemos la transitividad, por lo tanto \(a|[(n-1)! + 1]\).
Ahora, como tenemos que \(1<a<n\), entonces \(a\) debe de ser alguno de los enteros entre \(2\) y \(n-1\), por lo cual debe suceder que \(a|(n-1)!\).

Finalmente como \(a|(n-1)!\) y \(a|[(n-1)! + 1]\), por la propiedad \(4\) de la Proposición 2 tenemos que \(a|[(n-1)! + 1 - (n-1)!]\) esto es que \(a|1\). Para que suceda lo anterior \(a\) debería ser igual a \(1\), lo cual es una contradicción. Por lo tanto, \(n\) debe ser un número primo. \(\square\)

Con este teorema se logra tener una condición suficiente para probar si un número entero positivo es primo o no. Lo único que debemos hacer es revisar si \((n-1)! \equiv -1 \pmod{p}\). Desafortunadamente no es muy práctico ya que el valor de \((n-1)!\) comienza a ser muy grande, cuando \(n\) es grande.

Código para implementar el teorema de Wilson#

Dado un entero positivo \(n\), el siguiente código nos va a calcular \((n-1)!\) y además nos dirá si es o no congruente con \(-1\) módulo \(n\).

def thm_wilson(n):
    fact = 1
    for i in range(2,n):
        fact *= i
    if fact%n == n-1:
        print(f"({n}-1)! = {fact} ≡ {fact%n - n} (mod {n}) , además {n} es un número primo")
    else:
        print(f"({n}-1)! = {fact} ≡ {fact%n} (mod {n})")

thm_wilson(7)

(7-1)! = 720 ≡ -1 (mod 7) , además 7 es un número primo

thm_wilson(8)

(8-1)! = 5040 ≡ 0 (mod 8)

thm_wilson(55)

(55-1)! = 230843697339241380472092742683027581083278564571807941132288000000000000 ≡ 0 (mod 55)

thm_wilson(101)

(101-1)! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ≡ -1 (mod 101) , además 101 es un número primo

Algunos problemas resueltos#

Podemos emplear el teorema de Fermat para encontrar el residuo cuando un entero \(a^n\) es dividido por un primo \(p\) donde \(p\nmid a\) y \(n \ge p-1\).

Ejemplo 105

Encuentra el residuo cuando \(25^{1764}\) es dividido por \(11\).

Solución.

Tenemos que \(p = 11\) y \(a = 25\). Primero veamos que

\[25 \equiv 3 \pmod{11}.\]

Por lo tanto

\[25^{1764} \equiv 3^{1764} \pmod{11}.\]

Luego, como \(11 \nmid 25\) por el Teorema de Fermat (Teorema 35), \(3^{10} \equiv 1 \pmod{11}\). Entonces tenemos lo siguiente

\[\begin{align*} 3^{1764} &= 3^{10\cdot 176 + 4} \\ & \\ &= (3^{10})^{176} \cdot 3^4 \\ & \\ &\equiv (1)^{160} \cdot 3^4 \pmod{11} \\ & \\ &\equiv 3^4 \pmod{11} \\ & \\ &\equiv 81 \pmod{11}\\ & \\ &\equiv 4 \pmod{11}. \end{align*}\]

Por lo tanto el residuo cuando \(25^{1764}\) es dividido por \(11\) es \(4\).

También el teorema de Euler nos sirve para encontrar residuos de un entero \(a^n\), pero tiene un poco más de libertad ya que no necesita que el módulo sea un número primo, pero sí es necesario que \((a,n) = 1\).

Ejemplo 106

Encuentra el residuo cuando \(123^{1043}\) es dividido por \(16\).

Solución.

Primero veamos que \(123 \equiv 11 \pmod{16}\), entonces tendríamos que

\[123^{1043} \equiv 11^{1043} \pmod{16}.\]

Ahora, por el Teorema de Euler (Teorema 39), como \((11,16) = 1\) tenemos que

\[11^{\varphi(16)} \equiv 11^8 \equiv 1 \pmod{16}.\]

Entonces tenemos que

\[\begin{align*} 11^{1043} &= 11^{8\cdot 130}\cdot 11^3 \\ & \\ &= (11^8)^{130} \cdot 1331 \\ & \\ &\equiv 1^{130} \cdot 3 \pmod{16} \\ & \\ &\equiv 3\pmod{16}. \end{align*}\]

Por lo tanto el residuo cuando \(123^{1043}\) es dividido por \(16\) es \(3\).

Ejemplo 107

Sea \(p\) un número primo. Prueba que \(p\) divide a \(ab^p - ba^p\) para todos los enteros \(a\) y \(b\).

Solución.

Primero notemos que \(ab^p - ba^p = ab(b^{p-1} - a^{p-1})\).

Si sucediera que \(p|ab\), por las propiedades de divisibilidad ya tendríamos que \(p|(ab^p - ba^p)\).

Si \(p\nmid ab\), entonces tendríamos que \((p,a) = 1\) y \((p,b) = 1\). Luego, como se cumplen las condiciones del Teorema de Fermat (Teorema 35), tendríamos que

\[a^{p-1} \equiv 1 \pmod{p} \quad \text{y} \quad b^{p-1} \equiv 1 \pmod{p}.\]

Por la propiedad \(3\) del Teorema 29 tenemos la transitividad, por lo cual se cumple que \(a^{p-1} \equiv b^{p-1} \pmod{p}\). Es decir, que \(p|(a^{p-1} - b^{p-1})\). Lo anterior implica que \(p|(ab^p - ba^p)\).

Por lo tanto \(p|(ab^p - ba^p)\) para cualquier valor de \(p\) y enteros \(a\) y \(b\). \(\square\)

Para el siguiente problema necesitamos probar que el inverso del inciso \(4\) de la Proposición 2 es cierto pero con una pequeña restricción.

Proposición 29

Sea \(n\) un entero positivo tal que \(n|(a\alpha + b\beta)\) para cualesquiera enteros \(\alpha\) y \(\beta\). Si \(d|n\) entonces \(d|a\) y \(d|b\).

Demostración. Como \(n|(a\alpha + b\beta)\) para cualesquiera enteros \(\alpha\) y \(\beta\) en particular se cumple para los siguientes casos.

Si \(\alpha = 0\) y \(\beta = 1\).

Tendríamos que \(n|(a\cdot 0 + b\cdot 1)\), es decir que \(n|b\) y como \(d|n\) por el inciso \(2\) de la Proposición 2 tenemos que \(d|b\).

Si \(\alpha = 1\) y \(\beta = 0\).

Tendríamos que \(n|(a\cdot 1 + b\cdot 0)\), es decir que \(n|a\) y como \(d|n\) por el inciso \(2\) de la Proposición 2 tenemos que \(d|a\). \(\square\)

Ejemplo 108

Sean \(a\) y \(n\) enteros positivos tales que \(n \ge 2\) y \((a,n) = 1\). Demuestra que \(a^{n-1} + (n-1)! \equiv 0 \pmod{n}\) si y sólo si \(n\) es un número primo.

Solución.

Empecemos demostrando que si \(n\) es un número primo entonces \(a^{n-1} + (n-1)! \equiv 0 \pmod{n}\).

Por el Teorema de Wilson (Teorema 41), tenemos que

\[(p-1)!\equiv -1\pmod p.\]

Luego por el Teorema de Fermat (Teorema 35), tenemos que

\[a^{p-1} \equiv 1 \pmod{p}.\]

Finalmente si aplicamos la propiedad \(1\) del Teorema 32 tendríamos que

\[a^{p-1} + (p-1)! \equiv (-1) + 1 \pmod{p}.\]

Por lo tanto

\[a^{p-1} + (p-1)! \equiv 0 \pmod{p}.\]

Ahora demostremos que si \(a^{n-1} + (n-1)! \equiv 0 \pmod{n}\) entonces \(n\) es un número primo.

Procedamos por contradicción y supongamos que \(n\) no es un número primo, es decir que \(n = n_1n_2\), donde \(2 \le n_2 \le n_1\).

Por la Definición 35 de congruencia, tendríamos que \(n|[a^{n-1} + (n-1)!]\) y como \(n_1|n\), podemos concluir que \(n_1|[a^{n-1} + (n-1)!]\) gracias al inciso \(2\) de la Proposición 2. Luego por la Proposición 29 tendríamos que \(n_1|a^{n-1}\) y \(n_1|(n-1)!\). Como \(n_1 \ge 2\), por el Lema 1 tendríamos que \(n_1\) tiene un factor primo digamos \(p\). Por otro lado tendríamos la descomposición en primos de \(a\), es decir que \(a = p_1\cdot p_2 \cdot \ldots \cdot p_k\).

Entonces como \(n_1|a^{n-1}\) tendríamos que \(p|a^{n-1}\), es decir que \(p|(p_1^{n-1}\cdot p_2^{n-1} \cdot \ldots \cdot p_k^{n-1})\). Pero como son factores primos, tiene que suceder que \(p = p_i\) para alguna \(1 \le i \le k\).
Finalmente tenemos que \(p|a\) y además \(p|n\), entonces tendríamos que \((a,n) = p\) y esto contradice la hipótesis de que \((a,n) = 1\). Por lo tanto \(n\) debe ser un número primo. \(\square\)

Explicación del código#

En este capítulo no presentamos un código para el teorema de Fermat debido a su complejidad de potencias y a que el teorema de Euler lo generaliza.
Sin embargo, en este capítulo presentamos un herramienta para calcular potencias de una manera mas práctica. Introducimos la función pow la cual utiliza un algoritmo de exponenciación binaria modular lo cual le permite calcular las potencias de números de una manera más eficiente.
En otras palabras es más rápido para python calcular pow(x,y,z) en lugar de (x**y)%z.
La sintaxis de la función es la siguiente pow(base,exponente,módulo).

pow(3,5,7)

El código anterior hace el siguiente cálculo \(3^5 \pmod{7}\).

Pasemos a ver cómo funcionan los códigos. Sólo explicaremos los códigos que no han aparecido a lo largo de las notas. Los demás códigos ya fueron explicados en secciones anteriores.

El primer código que usamos fue para verificar que dados los enteros \(a\) y \(n\) se satisfacía el teorema de Euler.

def thm_euler(a,n):
    d = algoritmo_euclides(a,n)
    if d == 1:
        print(f"Se cumple que {a}^{phi_euler(n)} ≡ {pow(a,phi_euler(n),n)} (mod {n})")
    else:
        print(f"No se cumple que {a} y {n} sean primos relativos ya que ({a},{n}) = {d}")

Definimos una función llamada «thm_euler» la cual recibe como argumentos dos enteros positivos \(a\) y \(n\).

def thm_euler(a,n):

Creamos una variable \(d\) en la cual guardamos el valor del máximo común divisor entre \(a\) y \(n\) el cual es calculado con la función realizada en la sección del algoritmo de Euclides.

    d = algoritmo_euclides(a,n)

Creamos un condicional if el cual ejecuta el código dentro de él si se cumple que el valor de \(d = 1\). Si lo anterior es cierto el código nos imprime en la consola el cálculo de \(a^{\varphi(n)}\equiv 1\pmod n\). Por un lado expresamos lo que se va a calcular es decir, {a}^{phi_euler(n)} y por otro lado se calcula el residuo al dividir \(a^{\varphi(n)}\) entre \(n\) es decir, pow(a,phi_euler(n),n). Con esto logramos verificar que el residuo efectivamente sea igual a \(1\).

    if d == 1:
        print(f"Se cumple que {a}^{phi_euler(n)} ≡ {pow(a,phi_euler(n),n)} (mod {n})")

Por último si el condicional if no se cumple, entonces pasaría al condicional else, el cual nos imprime una advertencia de que el máximo común divisor entre \(a\) y \(n\) es mayor que \(1\) y por lo tanto no se cumpliría el teorema de Euler.

    else:
        print(f"No se cumple que {a} y {n} sean primos relativos ya que ({a},{n}) = {d}")

El segundo código que hicimos es para verificar que se cumple el teorema de Wilson dado un entero \(n\).

def thm_wilson(n):
    fact = 1
    for i in range(2,n):
        fact *= i
    if fact%n == n-1:
        print(f"({n}-1)! = {fact} ≡ {fact%n - n} (mod{n}) , además {n} es un número primo")
    else:
        print(f"({n}-1)! = {fact} ≡ {fact%n} (mod{n})")

Definimos una función llamada «thm_wilson» la cual recibe como argumento un entero positivo \(n\).

def thm_wilson(n):

Luego creamos una variable \(fact\) la cual iniciamos con un valor de \(1\). Empezamos un ciclo for y recorremos los valores desde \(2\) hasta \(n-1\). Estos valores se van a ir multiplicando a la variable \(fact\) para al final obtener el valor de \((n-1)!\).

    fact = 1
    for i in range(2,n):
        fact *= i

Luego creamos un condicional if en el cual se revisa si el residuo de la variable \(fact\) al dividirla entre \(n\) es \(n-1\). Esto se hace ya que Python nos regresa el mínimo residuo positivo, que en este caso es \(n-1\), pero tenemos que \(n-1 \equiv -1 \pmod{n}\). Si la condición anterior es cierta, el código nos imprime en la consola un mensaje en donde nos muestra el valor final de la variable \(fact\) y hace la cuenta para mostrarnos que el residuo de la variable \(fact\) al dividirla entre \(n\) es igual a \(n-1\). A este valor le restamos \(n\), ya que con eso obtendríamos el valor de \(-1\).

    if fact%n == n-1:
        print(f"({n}-1)! = {fact} ≡ {fact%n - n} (mod{n}) , además {n} es un número primo")

Por último si la condición anterior es falsa, el código pasa a la siguiente parte que es el condicional else el cual nos imprime un mensaje que nos muestra que el teorema de Wilson no se cumple, ya que el residuo al dividir la variable \(fact\) entre \(n\) no es \(-1\).

    else:
        print(f"({n}-1)! = {fact} ≡ {fact%n} (mod{n})")

Ejercicios de práctica#

Sea \(a\) un entero positivo. Prueba que cualquier factor primo mayor que \(2\) de \(a^2 + 1\) es de la forma \(4m + 1\).
Pista: utiliza el teorema de Fermat para llegar a una contradicción.
Usa el Teorema de Fermat para resolver el siguiente problema. ¿Para cuáles números primos \(p\), \(2^p + 1\) es divisible por \(p\)?
Usa el Teorema de Euler para encontrar los últimas \(2\) dígitos de \(7^{209}\).
Usa el Teorema de Euler para encontrar lo siguiente. ¿Cuál es el residuo cuando \({29^{31}}^{109}\) es dividido por \(9\)?
Demuestra que si \(p\) es un número primo impar tal que \(p \ge 5\), entonces \(6(p-4)! \equiv 1 \pmod{p}\).
Sea \(p\) un número primo impar, Demuestra los siguientes dos incisos.
- \(1^2\cdot 3^2 \cdot 5^2 \cdot \ldots \cdot (p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod{p}\).
- \(2^2\cdot 4^2 \cdot 6^2 \cdot \ldots \cdot (p-1)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod{p}\).