Teoría de números (nivel 1) Lección 5. El teorema de Euler-Fermat
En la sección anterior, hemos visto propiedades básicas de las congruencias y el teorema pequeño de Fermat. Una consecuencia muy importante (que se ha analizado en un ejercicio resuelto) es que encontrar un exponente pequeño $n$ tal que $a^n\equiv 1\ (\text{mod}\ m)$ nos permite calcular otras potencias de $a$ módulo $m$ más fácilmente. Veamos otro ejemplo, porque esta idea es fundamental.
Sean $a=5$ y $m=32$. Estamos interesados en encontrar $n\in\mathbb{N}$ tal que $5^n\equiv 1\ (\text{mod } 32)$, para lo que calculamos las primeras potencias de $5$ multiplicando sucesivamente por $5$ y tomando restos módulo $32$:
\begin{align*}
5^1&=5\equiv 5\ (\text{mod }32),&
5^5&\equiv 17\cdot 5\equiv 85\equiv 21\ (\text{mod }32),\\
5^2&=25\equiv 25\ (\text{mod }32),&
5^6&\equiv 21\cdot 5\equiv 105\equiv 9\ (\text{mod }32),\\
5^3&=125\equiv 29\ (\text{mod }32),&
5^7&\equiv 9\cdot 5\equiv 45\equiv 13\ (\text{mod }32),\\
5^4&\equiv 29\cdot 5\equiv 145\equiv 17\ (\text{mod }32),&
5^8&\equiv 13\cdot 5\equiv 65\equiv 1\ (\text{mod }32).
\end{align*}
Podemos decir entonces que $n=8$ es el número buscado. Si ahora queremos calcular el resto de dividir $5^{100}$ entre $32$ no tenemos más que dividir $100$ entre $8$. Esto nos da la división $100=8\cdot 12+4$, luego podemos escribir
$$5^{100}=5^{8\cdot 12+4}=(5^8)^{12}\cdot 5^4\equiv 1^{12}\cdot 5^4\equiv 5^4\equiv 17\ (\text{mod }32).$$
Podríamos decir que hemos tenido suerte ya que sólo ha hecho falta calcular ocho potencias de $5$. ¿Qué hubiera pasado si hubiéramos necesitado calcular muchas más? En esta lección veremos cómo obtener un exponente (y luego también veremos cómo obtener el menor exponente) tal que la potencia da resto $1$.
La función $\varphi$ de Euler
Para cada número natural $n$, consideremos todos los números entre $1$ y $n$ y nos quedamos con los que sean primos relativos con $n$. Por ejemplo,
\[\begin{array}{c|l}
n&\text{números primos relativos con }n\text{ entre }1\text{ y }n\\\hline
8 & 1, 3, 5, 7\\
15 & 1, 2, 4, 7, 8, 11, 13, 14 \\
44 & 1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43 \\
48 & 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47\\
100& 1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49,\\
&\quad 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99
\end{array}\]
Definición de la función $\varphi$ de Euler
Para cada número natural $n$, se define $\varphi(n)$ como la cantidad de números entre $1$ y $n$ primos relativos con $n$.
Por lo tanto, a la vista de la tabla anterior, podemos escribir
$$\varphi(8)=4,\quad \varphi(15)=8,\quad\varphi(44)=20,\quad\varphi(48)=16,\quad\varphi(100)=40.$$
A continuación, mostramos una forma de calcular estos números sin necesidad de contarlos uno por uno.
Cálculo de la función $\varphi$ de Euler
Si descomponemos en factores primos $n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$, entonces se cumple que
$$\varphi(n)=p_1^{e_1-1}p_2^{e_2-1}\cdots p_r^{e_r-1}(p_1-1)(p_2-1)\cdots(p_r-1).$$
Demostración
Vamos a comenzar probando que, si $a$ y $b$ son primos entre sí, entonces $\varphi(ab)=\varphi(a)\varphi(b)$. Consideremos los números del $1$ al $ab$ dispuestos en forma de tabla:
$$\begin{array}{ccccc}
1&2&3&\ldots&b\\
b+1&b+2&b+3&\ldots&2b\\
2b+1&2b+2&2b+3&\ldots&3b\\
\vdots&\vdots&\vdots&&\vdots\\
(a-1)b+1&(a-1)b+2&(a-1)b+3&\ldots&ab
\end{array}$$
Ahora bien, si $r$ no es primo con $b$, entonces todos los números de la $r$-ésima columna no son primos con $b$ y, por tanto, tampoco lo son con $ab$. De esta forma, nos quedamos sólo con $\varphi(b)$ columnas. Veamos que en cada una de ellas hay $\varphi(a)$ números primos relativos con $a$ y habremos terminado. Cada una de estas columnas tiene a los números $r,b+r,2b+r,\ldots,(a-1)b+r$ para cierto $r$, de forma que cada uno se obtiene del anterior sumando $b$. Estos números dan todos resto distinto módulo $a$. Para ver esto último, por reducción al absurdo, si hubiera dos iguales, tendríamos que $ub+r\equiv vb+r\ (\text{mod }a)$ para $u$ y $v$ entre $0$ y $a-1$, de donde $ub\equiv vb\ (\text{mod }a)$ y, por tanto, $u\equiv v\ (\text{mod }a)$ ya que $\mathrm{mcd}(a,b)=1$. Como $u$ y $v$ están entre $0$ y $a-1$, necesariamente $u=v$.
Como $r,b+r,2b+r,\ldots,(a-1)b+r$ son $a$ números y dan todos resto distinto módulo $a$, tienen que ser congruentes con $0,1,\ldots,a-1$ módulo $a$ (aunque posiblemente desordenados). Esto nos dice que exactamente $\varphi(a)$ de ellos son primos relativos con $a$, como queríamos demostrar.
Esta propiedad demostrada nos dice que $\varphi(n)=\varphi(p_1^{e_1})\varphi(p_2^{e_2})\cdots\varphi(p_r^{e_1r})$ ya que $p_1^{e_1},p_2^{e_2},\ldots,p_r^{e_r}$ son primos entre sí. Ahora sólo necesitamos probar que $\varphi(p_i^{e_i})=p_i^{e_i-1}(p_i-1)$, pero esto es consecuencia de que de los números que no son primos relativos con $p_i^{e_i}$ son los múltiplos de $p_i$ y, por tanto, hay $p_i^{e_i-1}$ de ellos entre $1$ y $p_i^{e_i}$. Por tanto, $\varphi(p_i^{e_i})=p_i^{e_i}-p_i^{e_i-1}=p_i^{e_i-1}(p_i-1)$.
Volviendo a los ejemplos anteriores, tenemos que
$$\begin{align*}
\varphi(8)&=\varphi(2^3)=2^2(2-1)=4,\\ \varphi(15)&=\varphi(3\cdot 5)=3^0\cdot5^0\cdot(3-1)(5-1)=8,\\
\varphi(44)&=\varphi(2^2\cdot 11)=2^1\cdot11^0\cdot(2-1)(11-1)=20,\\
\varphi(48)&=\varphi(2^4\cdot3)=2^3\cdot3^0\cdot(2-1)(3-1)=16,\\
\varphi(100)&=\varphi(2^2\cdot 5^2)=2^1\cdot 5^1\cdot(2-1)(5-1)=40.
\end{align*}$$
Esto debería bastar para convencernos de que la fórmula simplifica considerablemente los cálculos. Es fácil ver que esta también se puede escribir como
$$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right).$$
Ejercicio propuesto
Responde razonadamente a las siguientes preguntas:
- ¿Para qué valores de $n$ se tiene que $\varphi(n)$ es impar?
- ¿Qué valores de $n$ cumplen que $\varphi(n)=n-1$?
- ¿Qué valores de $n$ verifican que $\varphi(n)=2$? ¿Y $\varphi(n)=4$? ¿Y $\varphi(n)=6$?
- ¿Qué valores de $n$ cumplen que $\varphi(n)$ es un divisor de $n$?
El teorema de Euler-Fermat
Teorema de Euler-Fermat
Si $\mathrm{mcd}(a,m)=1$, entonces $a^{\varphi(m)}\equiv 1\ (\text{mod }m)$.
Demostración
Sean $x_1,x_2,\ldots,x_{\varphi(m)}$ los números primos relativos con $n$ que están entre $1$ y $n$. Consideremos, además, los números $y_1=ax_1$, $y_2=ax_2$,... $y_{\varphi(m)}=ax_{\varphi(m)}$. Entonces, tenemos que $y_i\equiv y_j\ (\text{mod }m)$ si y sólo si $x_i\equiv x_j\ (\text{mod }m)$ (ya que $a$ se puede cancelar por ser $\mathrm{mcd}(a,m)=1$) y esto equivale a que $i=j$ (ya que $x_i$ y $x_j$ son números distintos entre $1$ y $n$.
Teniendo en cuenta que $\mathrm{mcd}(y_i,m)=1$ para todo $i$, lo anterior nos dice que que $y_1,y_2,\ldots,y_{\varphi(m)}$ dan los mismos restos módulo $m$ que $x_1,x_2,\ldots,x_{\varphi(m)}$ (aunque posiblemente en otro orden). Por tanto, se tiene que
$$x_1x_2\cdots x_{\varphi(m)}\equiv y_1y_2\cdots y_{\varphi(m)}=a^{\varphi(m)}x_1x_2\cdots x_{\varphi(m)}\ (\text{mod }m).$$
Finalmente, vemos que $\mathrm{mcd}(x_1x_2\cdots x_{\varphi(m)},m)=1$, luego podemos cancelar el factor común y llegamos a que $1\equiv a^{\varphi(m)}\ (\text{mod }m)$.
Este resultado ya es lo más general posible, puesto que si $\mathrm{mcd}(a,m)\neq 1$, entonces no puede existir un exponente $n$ tal que $a^n\equiv 1\ (\text{mod }m)$. Es interesante también darse cuenta de que si $a^n\equiv 1\ (\text{mod }m)$, entonces el inverso de $a$ módulo $m$ existe y es igual a $a^{n-1}$. Veremos a continuación algunos problemas donde se usa este resultado.
Ejercicio resuelto
Demostrar que todo número que no es multiplo de $2$ ni de $5$ tiene un múltiplo cuya expresión decimal sólo tiene nueves.
Solución
Si un número $a$ no es múltiplo de $2$ ni de $5$, entonces $\mathrm{mcd}(a,10)=1$, luego se tiene que $10^{\varphi(a)}\equiv 1\ (\text{mod }a)$. Esto quiere decir que $10^{\varphi(a)}-1$, que se escribe sólo con nueves, es múltiplo de $a$.
Ejercicio propuesto
Demostrar que todo número que no es multiplo de $2$ ni de $5$ tiene un múltiplo cuya expresión decimal es de la forma $10101...01$.
Ejercicio resuelto
Dados números naturales $a$ y $n$, demostrar que $a^{4n+1}$ tiene la misma última cifra que $a$.
Solución
Las última cifra es el resto de dividir el número entre $10$. En este sentido, el teorema de Euler-Fermat nos dice que $a^4=a^{\varphi(10)}\equiv 1\ (\text{mod }10)$ si $\mathrm{mcd}(a,10)=1$
Obtención del exponente óptimo
Si $\mathrm{mcd}(a,m)=1$ y $n$ es el mínimo exponente mayor o igual que $2$ que cumple $a^n\equiv 1\ (\text{mod }m)$, entonces $n$ divide a $\varphi(m)$.
Demostración
Observamos en primer lugar que $\varphi(m)$ es un número que cumple esa propiedad por el Teorema de Euler-Fermat. Si el exponente buscado $n$ no fuera un divisor de $\varphi(m)$ y llamamos $d=\text{mcd}(n,\varphi(m))$, se tiene que existen $u,v\in\mathbb{N}$ tales que $d=nu+\varphi(m)v$ según la identidad de Bézout luego $a^d=(a^n)^v(a^\varphi(m))^v\equiv 1\cdot 1\ (\text{mod }m)$. Ahora bien, si $n$ no es un divisor de $\varphi(m)$, entonces $d\lt n$ lo que contradice que $n$ es el mínimo exponente que cumple $a^n\equiv 1\ (\text{mod }m)$.
Para terminar, veamos cómo encontrar el exponente óptimo en un ejemplo concreto.
Ejercicio resuelto
Es fácil ver que $17^2=289$. ¿Cuál es el menor entero $n\geq 3$ tal que las tres últimas cifras de $17^n$ vuelven a ser $289$?
Solución
Vamos a encontrar el menor entero $k\geq 2$ tal que $17^k\equiv 1\ (\text{mod }1000$ ya que $n=k+2$ será el entero buscado. Para ello, observamos que $\varphi(1000)=400$ y $\mathrm{mcd}(17,1000)=1$, luego el teorema de Euler-Fermat nos dice que $k=400$ es una posible solución, pero puede que no sea la menor. Sin embargo, el menor exponente es un divisor de $400$. Los divisores de $400$ (distintos de $1$ y $400$) son
$$\{2,4,5,8,10,16,20,25,40,50,80,100,200\}$$
y entre estos debe estar el exponente óptimo. Ahora podemos ir buscando el exponente usando las relaciones de múltiplo entre estos divisores. Por ejemplo, para exponentes potencia de $2$, tenemos que
\begin{align*}
17^2&\equiv 289\ (\text{mod }1000),&
17^4&\equiv (289)^2\equiv 521\ (\text{mod }1000),\\
17^8&\equiv (521)^2\equiv 441\ (\text{mod }1000),&
17^{16}&\equiv (441)^2\equiv 481\ (\text{mod }1000).
\end{align*}
Aquí no hemos encontrado nada, luego vamos a probar con los divisores de $400$ que tienen un solo factor $5$:
\begin{align*}
17^5&=1419857\equiv 857\ (\text{mod }1000),&
17^{10}&\equiv (857)^2\equiv 449\ (\text{mod }1000),\\
17^{20}&\equiv (449)^2\equiv 601\ (\text{mod }1000),&
17^{40}&\equiv (601)^2\equiv 201\ (\text{mod }1000).
\end{align*}
Todavía no lo hemos encontrado, así que vamos a probar finalmente con los divisores que tienen un factor $5^2$:
\begin{align*}
17^{25}&=(857)^5\equiv 57\ (\text{mod }1000),&
17^{50}&\equiv (57)^2\equiv 249\ (\text{mod }1000),\\
17^{100}&\equiv (249)^2\equiv 1\ (\text{mod }1000).&
\end{align*}
Por tanto, $100$ es el menor exponente buscado y deducimos que $17^{102}$ es la menor potencia de $17$ (después de $17^2$) cuyas tres últimas cifras son $289$.
Aunque los cálculos anteriores son un poco aburridos, es importante darse cuenta de que hemos tenido que calcular muy pocos productos (sólo 8 cuadrados y 2 potencias quintas) quedándonos siempre con las tres últimas cifras del resultado. Si crees que esto no es tanta mejora, intenta calcular todas las potencias de $17$ desde $17^3$ hasta $17^{102}$.
Problema 41★★★☆☆
Encontrar el menor número natural $n$, si existe, tal que $64$ divide a $5^n-1$.
Pista. El teorema de Euler nos dice que $5^{32}-1$ es divisible entre $64$, por lo que $n=32$ es un número que cumple la condición del enunciado. Demuestra que el número buscado es un divisor de $32$.
PistaSolución 1Solución. Dado que $5$ y $64$ son primos entre sí, el teorema de Euler nos asegura que $5^{\varphi(64)}=5^{32}\equiv 1\ (\text{mód }64)$ luego $n=32$ es un número que cumple la condición del enunciado (aquí $\varphi(n)$ representa la función de Euler que indica cuántos números enteros entre $1$ y $n$ son primos relativos con $n$). Si llamamos $a$ al número que se pide en el enunciado, $a$ tiene que ser un divisor de $32$ ya que, en caso contrario, si llamamos $d=\text{mcd}(a,32)$, se tiene que existen $u,v\in\mathbb{N}$ tales que $d=au-32v$ según la identidad de Bézout luego $5^d(5^{32})^v=(5^a)^u$. Tomando restos módulo $64$ tenemos que $5^d\ \equiv 1\ (\text{mód }64)$ pero si $a$ no es un divisor de $32$, entonces $d\lt a$ lo que contradice que $a$ es el mínimo que cumple esta propiedad. Esto prueba que el número buscado es una potencia de $2$ y podemos desarrollar
\[5^{2^k}-1=(5-1)(5+1)(5^2+1)\cdots(5^{2^{k-1}}+1)\]
Ahora observemos que $5^m+1\ \equiv 2\ (\text{mód }4)$ luego cada factor de la forma $5^{2^j}+1$ es múltiplo de $2$ pero no de $4$ y el exponente de $2$ en el miembro de la derecha es $k+2$. Como queremos que sea divisible por $64$, tendrá que ser $k+2\geq 6$ luego $k\geq 4$ y, por tanto, $n=2^4=16$ es el menor número que cumple la propiedad.
Informar InfoSi crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 167★★★☆☆
Demostrar que si $p\geq 7$ es un número primo y $k$ es un número natural cualquiera, entonces existe una potencia de $p$ cuya representación decimal tiene $k$ ceros consecutivos.
Pista. Una forma de hacerlo es encontrar $n$ tal que los últimos $k+1$ dígitos de $p^n$ sean $0\stackrel{(k)}{\ldots}01$.
PistaSolución 1Solución. El truco está en probar que existe $n\in\mathbb{N}$ tal que los últimos $k+1$ dígitos de $p^n$ son $0\stackrel{(k)}{\ldots}01$, o lo que es lo mismo tal que $p^n\equiv 1 (\mathrm{mod}\ 10^{k+1})$. Usando el teorema de Euler y el hecho de que $p$ y $10^{k+1}$ son primos entre sí (ya que $p$ es primo distinto de $2$ y $5$), bastará tomar $n=\varphi(10^{k+1})$, siendo $\varphi$ la función de Euler.
Nota. Para $p=3$ y, más general, para cualquier natural $p$ (no necesariamente primo) tal que $\mathrm{mcd}(p,10)=1$ la demostración es la misma.
Informar InfoSi crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 436★★★☆☆
Sean $m$ y $n$ enteros positivos tales que $1\leq m\lt n$. En su representación decimal, $1978^n$ tiene los mismos últimos tres dígitos que $1978^m$. Encontrar $m$ y $n$ tales que su suma $m+n$ sea la menor posible.
Pista. Utiliza congruencias módulo $1000$ y el teorema de Euler-Fermat para hallar el menor exponente $k$ tal que $1978^k\equiv 1\ (\text{mod }1000)$.
PistaSolución 1Solución. Que los tres últimos dígitos coincidan equivale a que
$$1978^n-1978^m=1978^m(1978^{n-m}-1)\equiv 0\ (\text{mod }1000).$$
Esto implica que $m\geq 3$ ya que $1000=2^35^3$ y nos bastará trabajar módulo $5^3=125$. Vamos a buscar, por tanto, el menor entero $k$ tal que $1978^k\equiv 1\ (\text{mod }125)$. El teorema de Euler-Fermat nos dice que $1978^{\varphi(125)}\equiv 1\ (\text{mod }125)$ ya que $\mathrm{mcd}(125,1978)=1$, siendo $\varphi(125)=5^2(5-1)=100$. El menor exponente $k$ que estamos buscando debe ser un divisor de $100$ (ver nota), lo que nos da las posibilidades $k=1,2,4,5,10,20,25,50,100$. Ahora bien, como $1978\equiv 103\ (\text{mod }125)$, tenemos que
$$1978^{2}\equiv 103^2=10609\equiv 109\ (\text{mod }125),\quad 1978^4\equiv 109^2=11881\equiv 6\ (\text{mod }125),$$
luego podemos calcular
$$1978^{20}\equiv 103^4(103^4)^4=6\cdot 6^4\equiv 6\cdot 36^2\equiv 6\cdot 46\equiv 26\ (\text{mod }125).$$
Esto nos dice que el $k$ buscado no es igual a ninguno de los números $1,2,3,4,10,20$ (divisores de $20$). Probemos ahora $k=50$, lo que nos permitirá descartar también $25$ y $50$:
$$1978^{50}\equiv 103^2((103^4)^4)^3=109\cdot 46^3\equiv 109\cdot 86\equiv 124\ (\text{mod }125).$$
Esto nos deja sólo la posibilidad $k=100$, que nos da $m=3$ y $n=103$. Por tanto, la menor suma posible es $m+n=106$.
Nota. La afirmación de que $k$ debe ser un divisor de $100$ es un hecho conocido, pero vamos a demostrarlo. Si tomamos $d=\mathrm{mcd}(k,100)$, entonces la identidad de Bézout nos dice que existen $u$ y $v$ tales que $d=ku+100v$, luego $1978^d=(1978^k)^u(1978^{100})^v\equiv 1\ (\text{mod }125$. Si $k$ es el menor entero positivo que cumple $1978^k\equiv 1\ (\text{mod }125)$, entonces tiene que ser $d=k$, es decir, $k$ es un divisor de $100$.
Informar InfoOlimpiada Matemática Internacional, 1978 problema 1
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problema