[skip-to-content]

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*}
Observación 3.6.2.
Note que \(\varphi(n)=\left| (\mathbb{Z}/n\mathbb{Z})^{*}\right|\text{.}\) Es decir, \(\varphi(n)\) es la cantidad de elementos invertibles en \(\mathbb{Z}/n\mathbb{Z}\text{.}\)
\(\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.

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*}
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*}
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.

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.

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{.}\)

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.

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).\)
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).

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{.}\)

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\)).