El pasado día analizamos la solución de la ecuación \(aX\equiv b {\pmod {n}}\), \((aX \equiv b (n))\), cuando \(\mathbf{mcd}(a,n)=1\), resolviéndola utilizando la solución de Bézout:
Ejemplo: Resolver \(5X\equiv 52 {\pmod {53}}\)
Como \(\mathbf{mcd}(53,5)=1\) entones existe \(a\) tal que \(5a\equiv 1 {\pmod {53}}\). Para hallar \(a\) buscamos la solución de Bézout de \(\mathbf{mcd}(53,5)=1\), que nos da (-3,32), luego \(5\cdot 32\equiv 1 {\pmod {53}}\). Por tanto \[X\equiv 32\cdot 52 {\pmod {53}}\to X\equiv 21 {\pmod {53}}.\]
Función \(\varphi\) de Euler
Veamos un resultado muy importante:
Teorema de Fermat: Si \(p\) es primo y \(p\not\,\!|\,a\) entonces, \(a^{ (p-1)}\equiv 1{\pmod {p}}\)
Este resultado será muy importante a la hora de encontrar los restos potenciales y ver cuando 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}}\]
El teorema de Fermat podemos aplicarlo para los primos; sin embargo, encontrarlo para cualquier entero resulta simple con la función que Euler ideó: la función \(\varphi \). Esta función se define como
Esta función cumple propiedades muy interesantes, como
Si \(p\) es primo, \(\varphi (p)=p-1\)
Si \(p\) es primo, \(\varphi (p^\alpha)=p^{\alpha -1}(p-1)\)
Si \(mcd(n,m)=1\) es \(\varphi (nm)=\varphi (n)\varphi (m)\)
Ejemplo: Calcular \(\varphi(197532939176)\)
Observemos que \[197532939176=197532\cdot 10^6+939176=2^2\cdot 31\cdot 1593\cdot 10^6+2^2\cdot 31\cdot 7574.\] Luego \[197532939176=(2^2\cdot 31)(1593\cdot 10^6+7574)=2^2\cdot 31 \cdot 1593007574.\] Completemos la factorización: \[197532939176=2^3\cdot 31\cdot 149 \cdot 5345663\] Por tanto,\[\varphi(197532939176)=2^2(2-1)\cdot (31-1) \cdot (149-1)\cdot (5345663-1)=94938957120\]
Estos resultados nos sirven para exponer el Teorema:
Teorema de Euler: Si \(a,n\in\mathbb{Z}\) con \(\mathbf{mcd}(n,a)=1\), entonces \(a^{\varphi (n)}\equiv 1{\pmod {p}}\)
Nuestro propósito principal es resolver la ecuación de congruencias \(aX\equiv b {\pmod {n}}\). Si \(mcd(n,a)=1\) podemos utilizar el teorema de Euler, y tendremos
Observar que esto no tiene por qué cumplirse, dependerá de que exista o no el inverso de \(\bar{a}\) en \(\mathbb{Z}_{n}\).
Ejemplo: Resolver \(5X\equiv 12 {\pmod {21}}\)
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}}\]
Producto de Euler
La descomposición de un número entero en sus factores primos nos permite formular un resultado práctico para calcular la función \(\varphi\)
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: Calcular \(\varphi(1433671404)\)
Observemos que \(1433671404=2^2\cdot 3\cdot 11^2\cdot 17\cdot 241^2\), luego
\[\begin{multline*}\varphi (1433671404)=1433671404\left(1-\frac{1}{2}\right) \left(1-\frac{1}{3}\right)\\ \left(1-\frac{1}{11}\right)\left(1-\frac{1}{17}\right)\left(1-\frac{1}{241}\right)=407193600\end{multline*}\]
Ejercicio:Sea \(N\)=31128897379021, ¿cuál es el valor de \(\varphi(N)\pmod{73}\)?
Primero necesitamos factorizar, para hacerlo busquemos una descomposición de esta forma:
\[31128897379021=m_1\cdot 10^k+m_2.\] Si \(\mathbf{mcd}(m_1,m_2)=d\) entonces \[31128897379021=d\left(\frac{m_1}{d}\cdot 10^k+\frac{m_2}{d}\right),\] reduciendo de tamaño \(\frac{m_1}{d}\cdot 10^k+\frac{m_2}{d}\). Por ejemplo, \[31128897379021=311288\cdot 10^8+97379021.\]
En este caso, \(\mathbf{mcd}(311288,97379021)=1\), con lo cual no tenemos factores comunes y debemos probar otra descomposición.