La ecuación de congruencias \(aX\equiv b {\pmod {m}}\)
Uno de nuestros cometido será resolver la ecuación de congruencias \[aX\equiv b {\pmod {m}}\]
Esta ecuación tiene una solución fácil de calcular si \(\mathbf{mcd}(a,m)=1\). En ese caso solo necesitamos encontrar el inverso de \(a\) en \(\mathbb{Z}_m\) y multiplicar la ecuación por él. Para encontrar este inverso necesitamos la solución de Bézout, que podemos hallar mediante el algoritmo extendido de euclides:
Algoritmo extendido de Euclides
(%i1) | eucl_ext(a,b):=block([s,t,r], s:[1,0,0], t:[0,1,0], r:[a,b], while (r[2]>0) do ( s[3]:s[1]–floor(r[1]/r[2])*s[2], t[3]:t[1]–floor(r[1]/r[2])*t[2], s:[s[2],s[3],0], t:[t[2],t[3],0], r:[r[2],mod(r[1],r[2])] ), [s[1],t[1],r[1]] )$ |
Ejemplo: Resolver la ecuación \[7X\equiv 3 {\pmod {103}}\]
Restos potenciales
Para comenzar trataremos los restos potenciales; es decir, \[a^i\equiv r_i(n).\]
Ejercicio: Determinar el resto de la división de \(751^{157}\) entre 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».
Ejercicio: Crear una función,\(\mathbf{restos}(a,n)\), que devuelva los restos potenciales de \(a\) módulo \(n\).
Ejercicio: Sea \(X_0\) el resto potencial de \(4^{68}\pmod{57}\), e \(Y_0=309\ X_0\). ¿Cuánto suman los dígitos de \(Y_0\)?
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.
Ejemplo: Crear una criterio de divisibilidad para el 7 y determinar \[12345678910987654321\equiv X {\pmod {7}}\]
Ejemplo: Cuántos números, \(0\leq N<100\), verifican \[123456789N987654321\equiv 5 {\pmod {7}}\]
Ejercicio: ¿Cuánto suman los dos últimos números de la potencia \(1313131313131313^{131313}\)? |
Verifiquémoslo: