1.24: Teoremas de Wilson, Euler y Fermat

Como lo ilustró el Teorema del resto chino en el último capítulo, algunos resultados útiles e interesantes de la teoría numérica tratan de congruencias. En este capítulo presentamos algunos teoremas más conocidos que involucran congruencias.

Teorema de Wilson

Por ejemplo, supongamos que tomó todos los enteros distintos de cero módulo\(m\) y los multiplicó juntos (módulo\(m\)). ¿Qué obtendrías? Examinemos algunos casos:

En\(\mathbb{Z}_2\),	\([1]\)	\(=\)	\([1]\).
En\(\mathbb{Z}_3\),	\([1][2]\)	\(=\)	\([2]\).
En\(\mathbb{Z}_4\),	\([1][2][3]\)	\(=\)	\([2]\).
En\(\mathbb{Z}_5\),	\([1][2][3][4]\)	\(=\)	\([4]\).
En\(\mathbb{Z}_6\),	\([1][2][3][4][5]\)	\(=\)	\([0]\).
En\(\mathbb{Z}_7\),	\([1][2][3][4][5][6]\)	\(=\)	\([6]\).
En\(\mathbb{Z}_8\),	\([1][2][3][4][5][6][7]\)	\(=\)	\([0]\).
En\(\mathbb{Z}_9\),	\([1][2][3][4][5][6][7][8]\)	\(=\)	\([0]\).
En\(\mathbb{Z}_{10}\),	\([1][2][3][4][5][6][7][8][9]\)	\(=\)	\([0]\).
En\(\mathbb{Z}_{11}\),	\([1][2][3][4][5][6][7][8][9][10]\)	\(=\)	\([10]\).
En\(\mathbb{Z}_{12}\),	\([1][2][3][4][5][6][7][8][9][10][11]\)	\(=\)	\([0]\).
En\(\mathbb{Z}_{13}\),	\([1][2][3][4][5][6][7][8][9][10][11][12]\)	\(=\)	\([12]\).

Parece estar surgiendo un patrón. Cuando\(m\) es compuesto, parece que\[\label{eq: nonprime Wilson} [1][2][3] \cdots [m-1] = [0],\] excepto en el caso\(m=4\). Cuando\(m\) es prime, parece\[\label{eq: Wilson in Zm} [1][2][3]\cdots[m-1] = [m-1].\]

Quizás puedas ver por qué al menos algo de esto es cierto; Ejercicio te\(\PageIndex{1}\) pide justificar el patrón en ecuación\(\eqref{eq: nonprime Wilson}\). La ecuación\(\eqref{eq: Wilson in Zm}\) se conoce como Teorema de Wilson, \(^{1}\)y la presentamos aquí en forma equivalente.

Teorema \(\PageIndex{1}\): Wilson's Theorem

Si\(p\) es un primo, entonces\[(p-1)! \equiv -1 \pmod p.\nonumber \]

Prueba

Presentamos un boceto de la prueba, que se basará en unas cuantas afirmaciones que son ciertas pero que aquí no se probarán.

Comenzando, recordemos eso\((p-1)! = 1\cdot 2 \cdot 3 \cdots \cdot (p-1)\), y el módulo de clase residuo\(p\) al que pertenece este número es la misma clase que\([1][2]\dots[p-1]\) equivale.

Supongamos que\(p\) es primo; entonces el conjunto\(\{[1],[2],\dots,[p-1]\}\) de elementos distintos de cero en\(\mathbb{Z}_p\) es exactamente el conjunto de elementos en\(U_p\). Por Teorema 1.22.3 (4), cada elemento en\(U_p\) tiene una inversa. Un resultado básico en la teoría de grupos es que en cada grupo, incluyendo\(U_p\), no hay dos elementos distintos que tengan la misma inversa, y si un elemento de grupo es el inverso de otro, entonces el segundo elemento es el inverso del primero también. Esto significa que algunos de los elementos del producto se\([1][2]\cdots[p-1]\) pueden recolectar en pares de elementos que son inversos entre sí. Estos pares se “cancelarán” cada uno, dejando\([1]\) en su lugar (lo cual podemos ignorar en el producto, ya que no afectan ese resultado, por Teorema 1.22.3 (3)). ¿Qué queda en el producto? Los únicos términos de\([1][2]\cdots[p-1]\) eso no han sido cancelados de esta manera son aquellos que no pertenecen a un par inverso; por el Teorema 1.22.3 (4) la única forma en que esto puede suceder es cuando un elemento es su propio inverso. ¿Qué elementos\(U_p\) son sus propios inversos? Claramente\([1]\) y\([p-1]\) son sus propios inversos, por lo que permanecen cuando\([1][2]\cdots[p-1]\) se simplifica. No obstante, cualquier elemento que sea su propio inverso satisface\([x]^2 = [1]\), lo que equivale a la declaración\(p \mid (x^2-1)=(x+1)(x-1)\). Por Lema de Euclides (Lema 1.11.2) esto implica que\(p \mid (x+1)\) o\(p \mid (x-1)\), que significa\(x \equiv -1 \pmod p\) o\(x \equiv 1 \pmod p\). De ahí que no haya otras soluciones para\([x]^2=[1]\) además\([1]\) y\([p-1]\). De ahí sólo\([1]\) y\([p-1]\) son sus propios inversos, y\[[1][2]\cdots[p-1] = [1][p-1] = [p-1].\nonumber \] Desde\(-1 \in [p-1]\), nuestra prueba es completa.

Usemos un ejemplo para ilustrar la prueba del Teorema de Wilson. Supongamos que\(p=11\), y considerar el producto\[10! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10\nonumber \] módulo 11. En\(U_{11}\), encontramos los pares de elementos inversos, ilustrados por

\([1][1] = [1]\),	\([2][6] = [1]\),	\([3][4]=[1]\),
[6pt]\([5][9]=[1]\),	\([7][8] = [1]\),	\([10][10] = [1]\).

Ahora\[\begin{aligned} 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 &\equiv 1 \cdot (2 \cdot 6) \cdot (3 \cdot 4) \cdot (5 \cdot 9) \cdot (7 \cdot 8) \cdot 10 \pmod{11}\\ &\equiv 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 10 \pmod{11}\\ &\equiv 10 \pmod {11}\\ &\equiv -1 \pmod {11}.\end{aligned}\]

El pequeño teorema de Fermat y el teorema de Euler

Iniciamos esta sección introduciendo el Pequeño Teorema de Fermat. \(^{2}\)Este teorema tiene consecuencias de largo alcance para las aplicaciones a la criptografía y la transmisión segura de datos en Internet.

Teorema \(\PageIndex{2}\): Fermat's Little Theorem

Si\(p\) es primo y\(a\) es relativamente primo para\(p\) entonces\[a^{p-1}\equiv 1 \pmod p.\nonumber \]

Veamos algunos ejemplos.

Ejemplo \(\PageIndex{1}\)

Cuando\(p=2\), el Pequeño Teorema de Fermat dice que para cualquier entero\(a\) relativamente primo a 2 es congruente a 1 módulo 2; en otras palabras,\(a\) es extraño (¡no es sorprendente!).

Cuando\(p=3\), el Teorema dice que si no\(a\) es un múltiplo de 3, entonces\(a^2\) es uno más que un múltiplo de tres. Podemos verificar esto directamente anotando eso\[(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\quad\text{and}\nonumber\]\[(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1\nonumber\] para todos los enteros\(k\).

Cuando\(p=11\), el Pequeño Teorema de Fermat dice que cualquier número\(a\) no divisible por 11 satisface\(a^{10} \equiv 1 \pmod {11}\). Por ejemplo,\[\begin{aligned} 2^{10} &= 1024 = 11\cdot 93 + 1;\\ 6^{10} &= 60466176 = 11\cdot 5496925 + 1; \text{ and of course}\\ 10^{10} &= 10000000000 = 9999999999+1 = 11\cdot 909090909 + 1.\end{aligned}\]

De los registros disponibles para nosotros, parece que el pequeño teorema de Fermat se declaró originalmente (sin pruebas) en una carta que Fermat escribió en 1640. Una prueba fue presentada por Euler en 1736, y más tarde Euler publicó un teorema que sostiene no solo para primos sino para todos los módulos enteros positivos: \(^{3}\)

Teorema \(\PageIndex{3}\): Euler's Theorem

Si\(m>0\) y\(a\) es relativamente primo para\(m\) entonces\[a^{\phi(m)}\equiv 1\pmod m.\nonumber \]

Ejemplo \(\PageIndex{2}\)

Toma\(m=12\); luego\[\phi(m)=\phi\left(2^2\cdot3\right)=\left(2^2-2\right)(3-1)=4.\nonumber \] Los enteros positivos\(a<m\) con\(\gcd(a,m)=1\) son\(1\),\(5\),\(7\) y\(11\). \[\begin{aligned} 1^4 &\equiv 1\pmod{12}\quad\text{is clear} \\ 5^2 &\equiv 1\pmod{12}\quad\text{since }12\mid (25-1) \\ \therefore\left(5^2\right)^2 &\equiv 1^2\pmod{12} \\ \therefore 5^4 &\equiv 1\pmod{12}. \end{aligned}\]

Ahora\(7\equiv -5\pmod{12}\), y como\(4\) es par,\[\begin{aligned} 7^4 &\equiv (-5)^4 \equiv 5^4\pmod{12} \\ \therefore 7^4 &\equiv 1\pmod{12}. \end{aligned}\]

Por último,\(11\equiv -1\pmod{12}\) y otra vez, ya que\(4\) es parejo, tenemos\[11^4\equiv (-1)^4\pmod{12}\nonumber \] y\[11^4\equiv 1\pmod{12}.\nonumber \] Esto completa la verificación del Teorema de Euler para el caso\(m=12\).

El ejercicio\(\PageIndex{7}\) al final del capítulo te pide explicar por qué el pequeño teorema de Fermat puede derivarse como consecuencia del Teorema de Euler. Trabajemos ahora para probar el teorema de Euler.

Definición\(\PageIndex{1}\): Powers of Residue Classes

Si\([a]\in U_m\) define\([a]^1=[a]\) y para\(n>1\),\([a]^n=[a][a]\dotsm[a]\) donde hay\(n\) copias de\([a]\) a la derecha.

Teorema \(\PageIndex{4}\)

Si\([a]\in U_m\), entonces\([a]^n\in U_m\) para\(n\ge 1\) y\([a]^n=[a^n]\).

Prueba

Lo demostramos\([a]^n=[a^n]\in U_m\)\(n\ge 1\) por inducción en\(n\).

Si\(n=1\),\([a]^1=[a]=\left[a^1\right]\) y por suposición\([a]\in U_m\). Supongamos\[[a]^k=\left[a^k\right]\in U_m\nonumber \] para algunos\(k\ge 1\). Entonces\[\begin{split} [a]^{k+1} &=[a]^k[a] \\ &=\left[a^k\right][a]\quad\text{by the induction hypothesis} \\ &=\left[a^ka\right]\quad\text{by Definition 21.1.4} \\ &=\left[a^{k+1}\right]\quad\text{since }a^ka=a^{k+1}. \end{split}\] Así por el PMI, el teorema se sostiene para\(n\ge 1\).

Tenga en cuenta que para fijo\(m>0\) si\(\gcd(a,m)=1\) entonces\([a]\in U_m\). Y usando Teorema\(\PageIndex{4}\) tenemos\[a^n\equiv 1\pmod m \quad \Longleftrightarrow \quad \left[a^n\right]=[1] \quad \Longleftrightarrow \quad [a]^n=[1].\nonumber \]

De ello se deduce que el Teorema de Euler (Teorema\(\PageIndex{3}\)) es equivalente al siguiente teorema.

Teorema \(\PageIndex{5}\)

Si\(m>0\) y\([a]\in U_m\) entonces\[[a]^{\phi(m)}=[1].\nonumber \]

Una prueba de teorema\(\PageIndex{5}\) se esboza\(\PageIndex{6}\) en el Ejercicio al final del capítulo.

También el Teorema\(\PageIndex{5}\) es una consecuencia fácil del Teorema de Lagrange, sobre el cual los alumnos que tomen (o hayan tomado) un curso de álgebra abstracta aprenderán (o ya conocerán).

Para finalizar este capítulo, observamos que el pequeño teorema de Fermat se puede utilizar para simplificar el cálculo de\(a^n\bmod p\) en el caso especial que\(p\) es primo. Recordemos que si\(a^n\equiv r\pmod p\) donde\(0\le r<p\), entonces\(a^n\bmod p=r\). Podemos hacer dos cosas para simplificar el cálculo:

1. Reemplazar\(a\) por\(a\bmod p\).
2. Reemplazar\(n\) por\(n\bmod(p-1)\).

Ilustramos la técnica con un ejemplo.

Ejemplo \(\PageIndex{3}\)

Supongamos que\[\label{comp_mod_11} 1234^{7865435}\bmod{11}.\nonumber \] queremos calcular Primero reemplazamos\(1234\) por\(1234 \bmod{11}\). Dado que el módulo es 11, nuestro trabajo se hace más fácil por el Teorema 1.18.1 (e), y podemos escribir\(1234\equiv (4 - 3 + 2 - 1)\pmod{11}\), es decir,\(1234\equiv 2\pmod{11}\). Ya\(\gcd(2,11)=1\) que tenemos\(2^{10}\equiv1\pmod{11}\). Ahora\(7865435=(786543)\cdot 10+5\) así\[\begin{split} 2^{7865435} &\equiv 2^{(786543)\cdot10+5}\pmod{11} \\ &\equiv\left(2^{10}\right)^{786543}\cdot 2^5\pmod{11} \\ &\equiv 1^{786543}\cdot 2^5\pmod{11} \\ &\equiv 2^5\pmod{11}, \end{split}\] y\(2^5=32\equiv10\pmod{11}\). De ahí, De\[1234^{7865435}\equiv10\pmod{11}.\nonumber \] ello se deduce que\[1234^{7865435}\bmod 11=10.\nonumber \]

Ejercicios

Ejercicio \(\PageIndex{1}\)

Explique por qué cuando\(m\) es compuesto y no igual a 4, la ecuación se\(\eqref{eq: nonprime Wilson}\) mantiene, es decir,\[[1][2][3] \cdots [m-1] = [0]\nonumber \] en\(\mathbb{Z}_m\).

(Pista: manejar el caso donde\(m\) es de la forma\(p^2\), donde\(p\) es primo, por separado. Cuando maneje este caso, piense en por qué\(m=4\) es una excepción en la declaración anterior.)

Ejercicio\(\PageIndex{2}\)

\(p\)Déjese ser un prime.

1. Usa el Teorema de Wilson para mostrar que si\(p \equiv 3 \pmod 4\), entonces\[\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv 1 \pmod p.\nonumber \] (Pista: mostrar que la expresión de la izquierda es congruente con\(-(p-1)!\) módulo\(p\).)
2. Demuestre que si\(p \equiv 1 \pmod 4\), entonces\[\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod p.\nonumber \]

Ejercicio\(\PageIndex{3}\)

Que\(p\) sea un prime tal que\(p \equiv 3 \pmod 4\).

1. Mostrar eso\[(p-1)! \equiv -(1\cdot 3 \cdot 5 \cdots (p-2))^2 \pmod p.\nonumber \] (Pista: reemplazar todos los multiplicandos pares en\((p-1)!\) por números negativos congruentes.)
2. Demostrar que\[(1 \cdot 3 \cdot 5 \cdot \cdots \cdot (p-2))^2 \equiv 1 \pmod p.\nonumber \]
3. Explicar por qué\[1 \cdot 3 \cdot 5 \cdot \cdots \cdot (p-2) \equiv \pm 1 \pmod p.\nonumber \] (Use una idea de la prueba del Teorema de Wilson, o el resultado del Ejercicio 1.21.11.)
4. Demostrar que si\(p \equiv 3 \pmod 4\), entonces\[2 \cdot 4 \cdot 6 \cdot \cdots \cdot (p-1) \equiv \mp 1 \pmod p.\nonumber \]

Ejercicio \(\PageIndex{4}\)

Let\(f\) Ser la función definida en los enteros positivos por\[f(n) = \left \lfloor \frac{n! \bmod (n+1)}{n}\right\rfloor(n-1)+2.\nonumber \]

1. Calcular\(f(1),f(2),\dots,f(10)\) y registrar los valores.
2. \(f(n)\)Explique por qué siempre es un número primo, sin importar lo que sea el entero\(n\) positivo.
3. ¿Qué opinas? ¿Qué tan buena es esta función como medio para generar números primos?

Ejercicio\(\PageIndex{5}\)

Verificar que el Teorema se\(\PageIndex{2}\) mantenga si\(p=5\) por cálculo directo (como Teorema\(\PageIndex{3}\) se verificó para\(m=12\) en Ejemplo\(\PageIndex{2}\)).

Ejercicio \(\PageIndex{6}\)

En este ejercicio demostrarás Teorema\(\PageIndex{5}\). Vamos\(U_m = \{X_1, X_2, \dots, X_{\phi(m)} \}\). Aquí escribimos\(X_i\) para una clase de residuo en\(U_m\) para simplificar la notación.

1. Demuestre que si\(X \in U_m\) entonces\[\{XX_1, XX_2, \cdots, XX_{\phi(m)} \} = U_m.\nonumber \]
2. Explique por qué si\(X \in U_m\) entonces\[(XX_1)(XX_2)\cdots(XX_{\phi(m)}) = X_1X_2 \cdots X_{\phi(m)}.\nonumber \]
3. Vamos\(A = X_1X_2 \cdots X_{\phi(m)}\). Demuestre que si\(X \in U_m\) entonces\(X^{\phi(m)}A = A.\)
4. Concluir desde el último paso que\(X^{\phi(m)} = [1]\) y por lo tanto el Teorema\(\PageIndex{5}\) es cierto.

Ejercicio \(\PageIndex{7}\)

Demostrar que el pequeño teorema de Fermat sigue rápidamente del teorema de Euler.

Ejercicio\(\PageIndex{8}\)

Mostrar que si\(p\) es primo entonces\(a^p \equiv a \pmod p\) para todos los enteros\(a\).

(Pista: Considerar dos casos: i)\(\gcd(a,p) = 1\) y ii)\(\gcd(a,p) > 1\). Tenga en cuenta que en el segundo caso\(p \mid a\).)

Ejercicio \(\PageIndex{9}\)

Vamos\(m>0\). Vamos\(\gcd(a,m)=1\). Demostrar que\(a^{\phi(m)-1}\) es una inversa para\(a\) módulo\(m\). (Ver Teorema 1.20.1.)

Ejercicio\(\PageIndex{10}\)

Para todos\(a\in\{1,2,3,4,5,6\}\) encontrar una inversa\(a^\ast\) de\(a\) módulo\(7\) mediante el uso de Ejercicio\(\PageIndex{9}\). Elige\(a^\ast\) en cada caso para que\(1\le a^\ast \le 6\).

Ejercicio\(\PageIndex{11}\)

1. Usa la técnica en Ejemplo\(\PageIndex{3}\) para calcular\[28^{1202}\bmod 13\nonumber \] (Dado que el módulo no es 11, no puedes usar el mismo truco mod 11 (Teorema 1.18.1 (e)), por supuesto.)
2. ¿Puedes usar el Teorema de Euler y razonamiento similar al del Ejemplo\(\PageIndex{3}\) para simplificar\[29^{1202}\bmod 12?\nonumber \] Si es así, computa la respuesta; si no, explica por qué no.

Ejercicio\(\PageIndex{12}\)

El teorema de Wilson implica que para cada primo\(p\), el número\((p-1)!+1\) es divisible por\(p\). Llamamos\(p\) a Wilson prime si aún más es cierto, si el número\((p-1)!+1\) es divisible por\(p^2\). Encuentra los dos primos Wilson más pequeños (cada uno es menos de 20), y escribe algunas oraciones informando sobre lo que se sabe y no se sabe actualmente sobre Wilson primos, en base a lo que encuentres a través de algunas investigaciones en línea.

Notas al pie

[1] Después de John Wilson (1741 {1793), aunque los historiadores han identificado obra del matemático y científico árabe Abu Ali al-Hasan ibn al-Haytham (también conocido como Alházen, 965-1040) que demuestra que estaba consciente de este hecho y aprovechó. [7]

[2] El pequeño teorema de Fermat no es el único teorema que lleva el nombre de Fermat. Su teorema “grande”, o, como es más conocido, el último teorema de Fermat, afirma que no\(x^n + y^n = z^n\) tiene soluciones en enteros positivos\(x,\: y,\: z\) cuando\(n > 2\). Esto fue probado por Andrew Wiles en 1995 más de 350 años después de que fuera mencionado por primera vez por Fermat. Se trata de una historia interesante que ha sido tema de libros y de un especial de PBS (Nova, “The Proof”), y te animan a aprender más sobre ella.

[3] Observe la aparición aquí de la función totiente de Euler\(\phi\).