3.5: Teoremas de Fermat, Euler y Wilson
- Page ID
- 114972
En esta sección presentamos tres aplicaciones de congruencias. El primer teorema es el teorema de Wilson que afirma que\((p-1)!+1\) es divisible por\(p\), para\(p\) prime. A continuación, presentamos el teorema de Fermat, también conocido como pequeño teorema de Fermat que lo establece\(a^p\) y\(a\) tienen los mismos restos cuando se dividen por\(p\) dónde\(p \nmid a\). Finalmente presentamos el teorema de Euler que es una generalización del teorema de Fermat y establece que para cualquier entero positivo\(m\) que sea relativamente primo a un entero\(a\),
\[a^{\phi(m)}\equiv 1(mod \ m)\]
donde\(\phi\) está la\(\phi\) función -de Euler. Comenzamos probando un teorema sobre la inversa de enteros módulo primos.
Teorema
\(p\)Déjese ser un prime. Un entero positivo\(m\) es su propio módulo inverso\(p\) si y solo si\(p\) divide\(m+1\) o\(p\) divide\(m-1\).
Supongamos que\(m\) es su propio inverso. Así pues, de\[m.m\equiv 1(mod \ p).\] ahí\(p\mid m^2-1\). Como consecuencia de ello,
\[p\mid (m-1) \mbox{or} \ \ p\mid (m+1).\]Lo conseguimos\(m\equiv 1(mod\ p)\) o\(m\equiv -1 (mod \ p)\).
Por el contrario, supongamos que
\[m\equiv 1(mod\ p) \mbox{or} \ \ m\equiv -1 (mod \ p).\]
Así
\[m^2\equiv 1(mod \ p).\]
Teorema de Wilson
Si\(p\) es un número primo, entonces\(p\) divide\((p-1)!+1\).
Cuando\(p=2\), la congruencia se sostiene. Ahora vamos\(p>2\). Usando el Teorema 26, vemos que para cada uno\(1\leq m\leq p\), hay una inversa\(1\leq \bar{m}\leq p\) tal que\(m\bar{m}\equiv 1(mod \ p)\). Así, por el Teorema 28, vemos que los dos únicos enteros que tienen sus propios inversos son\(1\) y\(p-1\). De ahí que después de acoplar los enteros de 2 a\(p-2\) cada uno con su inversa, obtenemos\[2.3.....(p-2)\equiv 1(mod \ p).\] Así obtenemos\[1.2.3.....(p-2)(p-1)\equiv (p-1)(mod \ p)\] Como resultado, tenemos\((p-1)!\equiv -1(mod \ p)\).
Obsérvese también que lo contrario del teorema de Wilson también sostiene. Lo contrario nos dice si un entero es primo o no.
Si\(m\) es un entero positivo con\(m\geq 2\) tal que\[(m-1)!+1\equiv 0 \ (mod \ m)\] entonces\(m\) es primo.
Supongamos que\(m\) tiene un divisor adecuado\(c_1\) y\[(m-1)!+1\equiv 0(mod \ m).\] que\(m=c_1c_2\) ahí es donde\(1<c_1<m\) y\(1<c_2<m\). Así\(c_1\) es un divisor de\((m-1)!\). También, ya que\[m\mid ((m-1)!+1),\] obtenemos\[c_1\mid ((m-1)!+1).\] Como resultado, por el Teorema 4, obtenemos\[c_1\mid ((m-1)!+1-(m-1)!),\] lo que da eso\(c_1\mid 1\). Esto es una contradicción y por lo tanto\(m\) es primordial.
Presentamos ahora el Teorema de Fermat o lo que también se conoce como Pequeño Teorema de Fermat. Afirma que el resto de\(a^{p-1}\) cuando se divide por un primo\(p\) que no divide\(a\) es 1. Luego declaramos el teorema de Euler que establece que el resto de\(a^{\phi(m)}\) cuando se divide por un entero positivo\(m\) que es relativamente primo a\(a\) es 1. Demostramos el teorema de Euler sólo porque el teorema de Fermat no es más que un caso especial del teorema de Euler. Esto se debe a que para un número primo\(p\),\(\phi(p)=p-1\).
Teorema de Euler
Si\(m\) es un entero positivo y\(a\) es un entero tal que\((a,m)=1\), entonces\[a^{\phi(m)}\equiv 1(mod \ m)\]
Tenga en cuenta que\(3^4=81 \equiv 1(mod \ 5)\). También,\(2^{\phi(9)}=2^6=64\equiv 1(mod \ 9)\).
Presentamos ahora la prueba del teorema de Euler.
Prueba
Dejar\(k_1,k_2,...,k_{\phi(m)}\) ser un módulo de sistema de residuos reducidos\(m\). Por Teorema 25, el conjunto\[\{ak_1,ak_2,...,ak_{\phi(m)}\}\] también forma un módulo de sistema de residuos reducidos\(m\). Así
\[ak_1ak_2...ak_{\phi(m)}=a^{\phi(m)}k_1k_2...k_{\phi(m)}\equiv k_1k_2...k_{\phi(m)}(mod \ m).\]
Ahora ya que\((k_i,m)=1\) para todos\(1\leq i\leq \phi(m)\), tenemos\((k_1k_2...k_{\phi(m)},m)=1\). De ahí que por el Teorema 22 podamos cancelar el producto de\(k\)'s en ambos lados y obtenemos
\[a^{\phi(m)}\equiv 1(mod \ m).\]
Una consecuencia inmediata del teorema de Euler es:
Teorema de Fermat
Si p es un primo y\(a\) es un entero positivo con\(p\nmid a\), entonces\[a^{p-1}\equiv 1(mod\ p).\]
Presentamos ahora un par de teoremas que son consecuencias directas del teorema de Fermat. El primero afirma el teorema de Fermat de una manera diferente. Dice que el resto de\(a^{p}\) cuando se divide por\(p\) es lo mismo que el resto de\(a\) cuando se divide por\(p\). El otro teorema determina la inversa de un\(a\) módulo entero\(p\) donde\(p\nmid a\).
Si\(p\) es un número primo y\(a\) es un entero positivo, entonces\(a^p\equiv a(mod \ p)\).
Si\(p\nmid a\), por teorema de Fermat sabemos que\[a^{p-1}\equiv 1(mod \ p).\] Así, obtenemos\[a^{p}\equiv a(mod \ p).\] Ahora si\(p\mid a\), tenemos
\[a^p\equiv a\equiv 0 (mod \ p).\]
Si\(p\) es un número primo y\(a\) es un entero tal que\(p\nmid a\), entonces\(a^{p-2}\) es la inversa de un módulo\(p\).
Si\(p\nmid a\), entonces el teorema de Fermat dice que\[a^{p-1}\equiv 1(mod\ p).\] De ahí\[a^{p-2}a\equiv 1(mod\ p).\] Como resultado,\(a^{p-2}\) es la inversa del\(a\) módulo\(p\).
Ejercicios
- ¡Demuestre que 10! +1 es divisible por 11.
- ¿Cuál es el resto cuando 5! ¡25! se divide por 31?
- ¿Cuál es el resto cuando\(5^{100}\) se divide por 7?
- Mostrar que si\(p\) es un primo impar, entonces\(2(p-3)!\equiv -1(mod \ p)\).
- Encuentre un módulo de sistema de residuos reducido\(2^m\), donde\(m\) es un entero positivo.
- Mostrar que si\(a_1,a_2,...,a_{\phi(m)}\) es un módulo de sistema de residuo reducido\(m\), donde\(m\) es un entero positivo con\(m\neq 2\), entonces\(a_1+a_2+...+a_{\phi(m)}\equiv 0 (mod \ m)\).
- Mostrar que si\(a\) es un entero tal que no\(a\) es divisible por 3 o tal que\(a\) es divisible por 9, entonces\(a^7\equiv a (mod \ 63)\).