Sección 3.6 Función \(\varphi\) de Euler y Teorema de Euler - Fermat
¿Es posible "mejorar" el Pequeño Teorema de Fermat? La respuesta es afirmativa, pero será importante considerar la función \(\varphi\) de Euler.
Definición 3.6.1.
(Función de Euler) Sea \(n\in \mathbb{N}\text{.}\) Se define la función \(\varphi\) de Euler como
\begin{equation*}
\varphi: \mathbb{Z}^{+} \to \mathbb{Z}
\end{equation*}
\begin{equation*}
n\to \varphi(n)=\left| \left\lbrace m \in \mathbb{N} : m\le n \land
(n,m)=1\right\rbrace \right|\text{.}
\end{equation*}
Ejemplo 3.6.3.
\(\varphi(10)=4\text{.}\) ¿Por qué? Sólo \(1,3,7,9\) son números coprimos con \(10\text{.}\) Adicionalmente, las clases \(\left[ 1\right]_{10}\text{,}\) \(\left[ 3\right]_{10}\text{,}\) \(\left[ 7\right]_{10}\) y \(\left[ 9\right]_{10}\) son invertibles en \(\mathbb{Z}/10\mathbb{Z}\text{.}\)
¿Que pasa si \(n\) es un número muy extenso? La función \(\varphi\) posee las siguientes propiedades que permitirán simplificar los calculos.
Proposición 3.6.4.
(Propiedades de la función \(\varphi\))
- Si \(n\) es un número primo, entonces \(\varphi(n)=n-1\text{.}\)
- Si \(n=a\cdot b\) tal que \((a,b)=1\text{,}\) entonces \(\varphi(n)=\varphi(a)\cdot \varphi(b)\text{.}\)
- Si \(n\) es un número primo y \(k\in \mathbb{N}\text{,}\) entonces \(\varphi(n^{k})=n^{k}-n^{k-1}\text{.}\)
- Si \(n=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot ...\cdot
p_{r}^{k_{r}}\text{,}\) entonces
\begin{equation*}
\varphi(n)=n\cdot \left(1-\dfrac{1}{p_{1}}
\right)\cdot\left(1-\dfrac{1}{p_{2}}
\right)\cdot...\cdot\left(1-\dfrac{1}{p_{r}} \right)\text{.}
\end{equation*}
Ejemplo 3.6.5.
Queremos calcular \(\varphi(391)\text{.}\) Note que \(391=17 \cdot 23\) y \((17,23)=1\text{.}\) Por Propiedad 2 de la Proposición 3.6.4
\begin{equation*}
\varphi(391)=\varphi(17) \cdot \varphi(23)\text{.}
\end{equation*}
Como \(17\) y \(23\) son números primos, por Propiedad 1 de la Proposición 3.6.4, \(\varphi(17)=16\) y \(\varphi(23)=22\text{.}\) Finalmente
\begin{equation*}
\varphi(391)=16 \cdot 22=352.
\end{equation*}
Ejemplo 3.6.6.
Queremos calcular \(\varphi(3675)\text{.}\) Note que \(3675=3 \cdot 5^{2} \cdot 7^{2}\text{.}\) Por Propiedad 4 de la Proposición 3.6.4
\begin{equation*}
\varphi(3675)=3675\cdot\left( 1-\dfrac{1}{3}\right)\cdot \left(
1-\dfrac{1}{5}\right)\cdot \left(
1-\dfrac{1}{7}\right)=1680.
\end{equation*}
Ejercicio 3.6.7.
Calcule \(\varphi(2019)\text{.}\)
Nuevamente Sage nos proporcionará una herramienta para calcular la función \(\varphi\) de Euler para un número entero positivo \(n\text{.}\)
Gracias a la función \(\varphi\) de Euler, es posible introducir el teorema de Euler-Fermat.
Teorema 3.6.8.
(Euler - Fermat) Sea \(a \in \mathbb{Z}\) y \(n \in \mathbb{Z}\text{,}\) tales que \((a,n)=1\text{.}\) Entonces
\begin{equation*}
a^{\varphi(n)}\equiv 1 \ (\text{mod } n)\text{.}
\end{equation*}
Demostración.
Sea \((\mathbb{Z}/n\mathbb{Z})^{*}=\left\lbrace \left[ a_{1}\right]_{n},
\left[ a_{2}\right]_{n},...,\left[ a_{r}\right]_{n}
\right\rbrace\text{.}\) Por lo tanto, \(\varphi(n)=\left| (\mathbb{Z}/n\mathbb{Z})^{*}\right|=r\text{.}\) Considere \(\left[ a\right]_{n} \in (\mathbb{Z}/n\mathbb{Z})^{*}\text{.}\) Así
\begin{equation*}
\left[ a\right]_{n}\cdot
(\mathbb{Z}/n\mathbb{Z})^{*}=\left\lbrace \left[ aa_{1}\right]_{n},
\left[ aa_{2}\right]_{n},...,\left[ aa_{r}\right]_{n} \right\rbrace=
(\mathbb{Z}/n\mathbb{Z})^{*}.
\end{equation*}
Por lo tanto
\begin{equation*}
\left[ a_{1}\right]_{n}\cdot \left[
a_{2}\right]_{n}\cdot...\cdot\left[ a_{r}\right]_{n}=\left[
aa_{1}\right]_{n}\cdot \left[ aa_{2}\right]_{n}\cdot...\cdot\left[
aa_{r}\right]_{n}.
\end{equation*}
Equivalentemente (por Proposición 3.2.4)
\begin{equation*}
a_{1}\cdot a_{2}\cdot... \cdot a_{r}\equiv aa_{1}\cdot
aa_{2}\cdot...\cdot aa_{r} \ (\text{mod } n).
\end{equation*}
Reordenando, se consigue \(a_{1}\cdot a_{2}\cdot... \cdot a_{r}\equiv a^{r}\cdot a_{1}\cdot
a_{2}\cdot...\cdot a_{r} \ (\text{mod } n).\) Como \((a_{1}\cdot a_{2}\cdot... \cdot a_{r},n)=1\text{,}\) por ley de cancelación en congruencias (Proposición 3.1.10) y simetría: \(a^{r}\equiv 1 \ (\text{mod } n).\) Dado que \(r=\varphi(n)\text{,}\) entonces
\begin{equation*}
a^{\varphi(n)}\equiv 1 \ (\text{mod } n).
\end{equation*}
Veamos algunos ejemplos de como utilizar el Teorema de Euler - Fermat.
Ejemplo 3.6.9.
Encontraremos las últimas dos cifras de \(3333^{4444}\text{.}\) Buscaremos un número entero \(x\) (con \(0 \le x \le 99\)), tal que \(3333^{4444} \equiv x\) (mod \(100\)). Como \((100,3333)=1\text{,}\) por el Teorema de Euler - Fermat
\begin{equation*}
3333^{\varphi(100)}\equiv 1 \ (\text{mod } 100).
\end{equation*}
Se sigue que
\begin{equation*}
\varphi(100)=\varphi(2^{2}\cdot 5^{2})=\varphi(2^{2})\cdot
\varphi(5^{2})=2\cdot 4 \cdot 5 =40\text{.}
\end{equation*}
Por lo tanto, \(3333^{40}\equiv 1 \ (\text{mod } 100)\text{.}\) Elevando a \(111\text{,}\) se consigue \(3333^{4440}\equiv 1 \ (\text{mod } 100).\)Por otro lado, \(3333\equiv 33 \ (\text{mod } 100)\) y \(3333^{2}\equiv -11 \ (\text{mod } 100) \text{.}\) Esto implica que \(3333^{4}\equiv 121\equiv 21 \ (\text{mod } 100) \text{.}\) Finalmente
\begin{equation*}
3333^{4444} \equiv 21 \ (\text{mod } 100).
\end{equation*}
Por lo tanto, las últimas dos cifras de \(3333^{4444}\) son \(2\) y \(1\text{.}\)
Ejercicio 3.6.10.
Calcule el resto de la división entre \(23^{65}\) y \(60\text{.}\)
Del Teorema 3.6.8 se deriva una consecuencia muy interesante y útil.
Corolario 3.6.11.
Sean \(a,b,c \in \mathbb{Z}\) y \(n\in \mathbb{N}\) tales que \((c,n)=1\text{.}\) Si \(a\equiv b \ (\text{mod } \varphi(n))\text{,}\) entonces
\begin{equation*}
c^{a}\equiv c^{b} \ (\text{mod } n)\text{.}
\end{equation*}
Demostración.
Por hipótesis, \(a\equiv b \ (\text{mod } \varphi(n))\text{.}\) Es decir, existe un único entero \(t\) tal que \(\varphi(n)t+b=a\text{.}\) Por consiguiente
\begin{equation*}
c^{a}=c^{\varphi(n)t+b}=(c^{\varphi(n)})^{t}\cdot c^{b}\equiv
c^{b} \ (\text{mod } n),
\end{equation*}
por el Teorema de Euler - Fermat; ya que si \((c,n)=1\text{,}\) entonces \(c^{\varphi(n)}\equiv 1 \ (\text{mod } n).\)
Ejemplo 3.6.12.
Si hoy es jueves, ¿qué día será dentro de \(10^{10^{100}}\) días más? Buscamos un número entero \(x\text{,}\) tal que \(10^{10^{100}} \equiv x\) (mod \(7\)). Adicionalmente, \(\varphi(7)=6\text{.}\) Trabajaremos con el exponente de \(10^{10^{100}}\) en módulo 6. Es decir, con \(10^{100}\) y \(6\text{.}\)
Note que \(10\equiv 4 \ (\text{mod } 6)\text{,}\) por lo que \(10^{100}\equiv 4^{100} \ (\text{mod } 6)\text{.}\) Pero \(4^{k}\equiv 4 \ (\text{mod } 6)\text{,}\) para todo \(k\) natural. Por lo tanto, \(10^{100} \equiv 4\) (mod \(6\)).
Por Corolario 3.6.11, como \((7,10)=1\text{;}\) entonces
\begin{equation*}
10^{10^{100}} \equiv 10^{4} \ (\text{mod } 7).
\end{equation*}
Pero \(10^{2}\equiv 2 \ (\text{mod } 7)\text{.}\) De esta manera, \(10^{4}\equiv 4 \ (\text{mod } 7)\text{.}\) Por transitividad, \(10^{10^{100}} \equiv 4 \ (\text{mod } 7).\)Finalmente, si hoy es jueves; entonces en \(10^{10^{100}}\) días más será lunes (si el resto es 1, entonces será viernes; y así sucesivamente).
Ejemplo 3.6.13.
Calcularemos el resto de la división entre \(2^{11001^{11^{1100001}}}\) y \(23\text{.}\) Note que \((2,23)=1\text{.}\) Adicionalmente, \(\varphi(23)=22\) y \(\varphi(22)=10\text{.}\) Por consiguiente
\begin{equation*}
11^{1100001}\equiv 1 \ (\text{mod } 10).
\end{equation*}
Por Corolario 3.6.11
\begin{equation*}
11001^{11^{1100001}}\equiv 11001^{1}\equiv 1 \ (\text{mod }
22).
\end{equation*}
Nuevamente, por Corolario 3.6.11
\begin{equation*}
2^{11001^{11^{1100001}}}\equiv 2^{1}=2 \ (\text{mod } 23).
\end{equation*}
Por lo tanto, el resto de la división entre \(2^{11001^{11^{1100001}}}\) y \(23\) es \(2\text{.}\)
Ejercicio 3.6.14.
Encuentre el resto al dividir \(1^{1^{1}}+2^{2^{2}}+3^{3^{3}}+4^{4^{4}}+5^{5^{5}}+6^{6^{6}}+7^{7^{7}}\) por \(13\text{.}\)
El siguiente interact de Sage permite verificar si se verifica el Teorema de Euler-Fermat (debe seleccionar \(a\) y \(n\)).