Ejemplo: Dado \(n=71\cdots 71\), donde la pareja 71 se repite 10 veces, ¿cuál es su resto al dividirlo por 17?
El número en cuestión es \(71717171717171717171\) y el problema nos plantea: encontrar la solución de la ecuación \[71717171717171717171\equiv X\pmod{17}.\] Para resolverlo tendremos que calcular su resto al dividirlo por 17. Utilicemos las propiedades de divisibilidad:\[71717171717171717171=71717\cdot 10^{15}+17171\cdot 10^{10}+71717\cdot 10^5+17171\] Sabemos que \(71717=\dot{17}+11\), \(17171=\dot{17}+1\), luego \[71717171717171717171\equiv r\pmod{17}\] donde \(r\) es el mismo resto que \[11\cdot 10^{15}+1\cdot 10^{10}+11\cdot 10^5+1\equiv r\pmod{17}\] Realicemos lo mismo para \(10^{i}\), con \(i=5,10,15\) y tendremos \[11\cdot 12+1\cdot 2+11\cdot 6+1\equiv r\pmod{17},\] obteniendo que \(r=14\).
Para resolverlo hemos tenido que calcular \( 10^i\pmod{17}\) para \(i=5,10,15\). Si lo analizamos desde el punto de vista de resolver \( 10^i\pmod{17},\, \forall i\in\mathbb{Z}^+\) estaremos planteando un problema de restos potenciales. Los restos potenciales son los residuos positivos que resultan de dividir las potencias sucesivas de un número entero (base) por otro número positivo (módulo). Estos restos se repiten cíclicamente (periodo) o se vuelven cero, formando secuencias periódicas puras o mixtas menores que el módulo, útiles para resolver problemas complejos de divisibilidad.
Definición: Sean \(a,n\in\mathbb{Z}^+\), llamamos restos potenciales de \(a\) módulo \(n\) a los restos \[a^i\equiv r_i\pmod{n},\, \forall i\in\mathbb{Z}^+\]
Como veremos, estos restos son cíclicos y, por tanto, el número de restos distintos es finito.
Ejercicio: Determinar el resto de la división de \(751^{157}\) entre 22.
Observemos que el problema es equivalentes a resolver la ecuación \(751^{157}\equiv X {\pmod {22}} \). Como \(751\equiv 3 {\pmod {22}} \), resultará \[751^{157}\equiv 3^{157} {\pmod {22}}\] Por tanto, tendremos que calcular los restos potenciales de 3 módulo 22:
\[\begin{align*} 3^{5n}&\equiv 1 {\pmod {22}} \\ 3^{5n+1}&\equiv 3 {\pmod {22}} \\ 3^{5n+2}&\equiv 9 {\pmod {22}} \\ 3^{5n+3}&\equiv 5 {\pmod {22}} \\ 3^{5n+4}&\equiv 15 {\pmod {22}} \end{align*}\]
Si tenemos en cuenta que \(157=5n+2\Leftrightarrow 157\equiv 2\pmod{5}\), será
\[3^{157}=3^{5n+2}\equiv 3^{2}\equiv 9 {\pmod {22}}\]
Estos restos cumplen las siguientes propiedades: \[\begin{align*} a^0 &\equiv 1{\pmod{n}} \\ a &\equiv a{\pmod{n}} \\ a^k&\equiv r_k{\pmod{n}}\Rightarrow a^{k+1}\equiv a\cdot r_k{\pmod{n}} \end{align*}\]
Además a partir de un resto que se repiten, se repiten todos en forma cíclica.
Ejercicio: Verifica si es cierta o no la afirmación: «Para todo \(n\) natural \(6^{n}-1\) es divisible entre 5».
Calculemos los restos potenciales de 6 módulo 5:
\[\begin{align*} 6^{0}&\equiv 1 {\pmod {5}} \\ 6^{1}&\equiv 1 {\pmod {5}} \end{align*},\]
luego para todo \(n\in\mathbb{Z}^+\) \[6^n\equiv 1\pmod{5}\Rightarrow 5|(6^n-1)\]
Ejercicio: Crear una función,\(\mathbf{restos}(a,n)\), que devuelva los restos potenciales de \(a\) módulo \(n\).
(%i2)
restos(n,m):=block([r,proximo,repetido], r:[1], proximo:mod(n,m), repetido:false, whilenotrepetidodo( /* Primero añadimos el número, sea cual sea */ r:append(r,[proximo]), /* Calculamos el que vendría después */ proximo:mod(proximo·n,m), /* Comprobamos si ese «proximo» ya existe en nuestra lista */ ifmember(proximo,r)then( /* Si ya existe, lo añadimos UNA última vez para ver el cierre */ r:append(r,[proximo]), repetido:true ) ), r )$ restos(10,16);
\[\left[ 1{,}10{,}4{,}8{,}0{,}0\right] \]
Observar que la función devuelve el último valor que se repite. Si el último es igual al penúltimo no dice que a partir del penúltimo, todos son iguales. Si no coincide, entonces es cíclico.
Ejercicio: Calcular el resto potencial de \(4^{68}\pmod{57}\)
Primero calcularemos los restos potenciales de 4 módulo 57, utilizando la función anterio.
mod(68,ciclo);/* este es el exponente de 4 modulo 57 */ r[%+1];/* la posición que ocupa en los restos potenciales de 4 modulo 57*/
\[{ }5\]
\[{ }55\]
Uno de los problemas es determinar cuándo se produce el ciclo. Para resolverlo no ayudaremos de la función fi de Euler:
Teorema de Euler: Si \(a,n\in\mathbb{Z}\) con \(\mathbf{mcd}(n,a)=1\), entonces \(a^{\varphi (n)}\equiv 1{\pmod {p}}\)
Ecuación de congruencias
Nuestro propósito principal es resolver la ecuación de congruencias \(aX\equiv b {\pmod {n}}\). Si \(mcd(n,a)=1\), vimos que podemos utilizar la solución de Bezout para resolverlo:
Ejemplo: Resolver la ecuación \[7X\equiv 3 {\pmod {103}}\]
(%i5)
ex:eucl_ext(7,103); if ex[1]<0 then inv:mod(ex[1],103) else inv:ex[1]$ sol:mod(inv*3,103)$ print(«Solución X=»,sol,«(103)»)$
Verifiquémoslo:
(%i6)
mod(7*sol,103);
Sin embargo, si \(mcd(n,a)=1\) tenemos una herramienta poderosa: el teorema de Euler. Utilizándolo, tendremos
Necesitamos encontrar el inverso de 5 en \(\mathbb{Z}_{21}\), ya para ello utilizamos el teorema de Euler: \[5\cdot 5^{(\varphi(21)-1)}\equiv 1{\pmod {21}}\] Ahora \(\varphi(21)=(3-1)(7-1)=12\), de modo que \[5^{11}\equiv 17{\pmod {21}}.\]
Solo nos falta aplicarlo \[5X\equiv 12 {\pmod {21}}\to X\equiv 17\cdot 12\equiv 15{\pmod {21}}\]
Ejemplo: Resolver \(6X\equiv 22 {\pmod {77}}\)
Necesitamos encontrar el inverso de 6 en \(\mathbb{Z}_{77}\), que existe pues \(\mathbf{mcd}(6,77)=1\). Por el teorema de Euler: \[6\cdot 6^{(\varphi(77)-1)}\equiv 1{\pmod {77}}\] Ahora \(\varphi(77)=(7-1)(11-1)=60\), de modo que tenemos que determinar \[6^{59}\equiv X_0 {\pmod {77}}.\]
El teorema de Euler nos garantizaba que \(6^{60}\equiv 1 {\pmod {77}}\), pero no nos garantiza que 60 sea el primer entero, \(n\), tal que \(6^{n}\equiv 1 {\pmod {77}}\); es decir, puede existir un entero más pequeño que lo cumpla. Ahora si \(n\) es tal que \(6^{n}\equiv 1 {\pmod {77}}\), entonces \(n|60\). Probemos con los divisores de 60: [1, 5, 3, 15, 2, 10, 6, 30, 4, 20, 12, 60]
Solo nos falta aplicarlo: \[6X\equiv 22 {\pmod {77}}\to X\equiv 13\cdot 22\equiv 55{\pmod {77}}\]
Si el módulo en cuestión es primo, la ecuación es más simple:
Teorema de Fermat: Si \(p\) es primo y \(p\not\,\!|\,a\) entonces, \(a^{ (p-1)}\equiv 1{\pmod {p}}\)
Aunque anterior, este resultado se puede demostrar como consecuencia del Teorema de Euler y será muy importante a la hora de encontrar los restos potenciales y ver cuándo se reproduce el ciclo.
Ejemplo: Resolver \(7X\equiv 22 {\pmod {31}}\)
Necesitamos encontrar el inverso de 7 en \(\mathbb{Z}_{31}\), ya para ello podemos utilizar el teorema de Fermat: \[7\cdot 7^{29}\equiv 1{\pmod {31}}\] Ahora simplificamos como creamos conveniente; por ejemplo, 29=5*5+4, luego \[7^{29}\equiv (7^5)^57^4\equiv 5^5\cdot 14\equiv 25\cdot 14\equiv 9{\pmod {31}}\]
Solo nos falta aplicarlo \[7X\equiv 22 {\pmod {31}}\to X\equiv 9\cdot 22\equiv 12{\pmod {31}}\]
Recordemos que si \(n\in\mathbb{Z}\) es \({\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}\), entonces \[\varphi (n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)\]
Ejemplo: Utilizar la fórmula anterior para construir un algoritmo que calcule \(\varphi(87)\)
(%i1)
fiEuler(n):=block([result,d,p], result:n, p:n, d:2, while d < sqrt(p) do ( if mod(p,d) =0 then ( result:result·(d−1)/d, while mod(p,d)=0 do ( p:p/d ) ), d:d+1 ), if p>1 then result:result·((p−1)/p), return(result) )$
(%i2)
fiEuler(87);
\[56\]
Ejercicio: Resolver la ecuación de congruencias \(3X\equiv 16 \pmod{22}\).
(%i1)
mcd(a,b):=block([r,i], r:[mod(a,b)], r:append(r,mod(b,r)), id:2, for i:2 while r[i]>0 do ( r:append(r,[mod(r[i−1],r[i])]) ), r[length(r)−1] )$
(%i3)
fiEuler(n):=block([f,i,m], f:1, for i:2 thru n−1 do ( if(mcd(i,n)=1) then f:f+1 ), f )$ fi:fiEuler(22);
\[\operatorname{ }10\]
Sabemos que \(3^{10-1}\pmod{22}\) es el inverso de 3, luego
Ejercicio: Sea \(0<X<161\), la mayor de las soluciones de \(28X\equiv 35 {\pmod {161}}\). ¿Cuánto suman sus dígitos?
Siguiendo el procedimiento, primero vemos que \(\mathbf{mcd}(28,161)=7\), y como 7|35, la ecuación tiene solución y esta depende de \[4X_0\equiv 5 {\pmod {23}}.\] Resolvamos esta ecuación. Como 23 es primo, resulta \(\varphi(23)=(23-1)=22\), luego necesitamos \[4^{21}\equiv Y {\pmod {23}}.\]
Calculemos los restos potenciales:
\[\begin{align*}
4^0 &\equiv 1\pmod{23} \\
4^1 &\equiv 4\pmod{23} \\
4^2 &\equiv 16\pmod{23} \\
4^3 &\equiv 18\pmod{23} \\
4^5 &\equiv 12\pmod{23} \\
4^{10} &\equiv 6\pmod{23} \\
4^{20} &\equiv 13\pmod{23} \\
4^{21} &\equiv 6\pmod{23}
\end{align*}\]
Ahora solo falta aplicarlo:\[4X_0\equiv 5 {\pmod {23}}\Rightarrow X_0\equiv 6\cdot 5 {\pmod {23}}\Rightarrow X_0\equiv 7 {\pmod {23}}.\]
La solución general será: \[X\equiv \left[7+23k\right]\pmod{161},\ k\in\{0,\ldots,6\}.\]
La soluciones menores de 161 serán:\[7,30,53,76,99,122,145.\] La mayor de las soluciones es 145, y la respuesta al ejercicio 1+4+5=10.
Criterio de divisibilidad
La utilización de los restos potenciales nos sirve para establecer un criterio de divisibilidad que permite saber las propiedades de un número para que sea divisible por otro:
Sea dados \(m,n\in\mathbb{Z}^+\) para todo entero \[a=a_kn^k+a_{k-1}n^{k-1}+…+a_1n+a_0\] si \(n^i\equiv r_i{\pmod {m}}\) entonces \[a\equiv a_kr_k+…+a_0r_0{\pmod {m}}\]
Esto nos permite justificar, por ejemplo, que un número es divisible por 3 si la suma de sus dígitos es divisible por 3.
Ejemplo: Crear una criterio de divisibilidad para el 4.
Primero calculamos los restos potenciales de 10 módulo 4:
\[\begin{align*} 10^{0}&\equiv 1 {\pmod {4}} \\ 10^{1}&\equiv 2 {\pmod {4}}\\ 10^{2}&\equiv 0 {\pmod {4}}\end{align*}\] Luego si \(N=\sum_{i=0}^kd_i10^i\) resultará \[N\equiv (2d_1+d_0) {\pmod {4}}.\] Es decir, un número es divisible por 4 si lo es la suma de su última cifra más el doble de la penúltima.
Ejemplo: ¿Cuál es el resto de la división de 10655871899 entre 6?
Primero calculamos los restos potenciales
(%i1)
makelist(mod(10^i,6),i,0,5);
\[\left[ 1,4,4,4,4,4\right] \]
Como vemos, a partir del segundo dígito se repiten. Luego \[4\left ( \sum_{i=1}^k d_i \right )+d_0\equiv n(\textbf{mod}\,6)\Leftrightarrow 4\left ( \sum_{i=0}^k d_i \right )-3d_0\equiv n(\textbf{mod}\,6)\]
Ejemplo: Crear una criterio de divisibilidad para el 7 y determinar \[12345678910987654321\equiv X {\pmod {7}}\]
Para este ejercicio crearemos dos funciones previamente: restos(\(n,m\)), nos proporciona los restos potenciales de \(n\) módulo \(m\). digitos(\(n\)), nos devuelve un vector con los dígitos del número \(n\).
Ahora, veamos los restos de 10 módulo 7:
(%i3)
r10:restos(10,7);
Luego, tenemos un ciclo de longitud 6 desde 0. Apliquemos el teorema: