Ecuación de congruencias simple
Para resolver la ecuación \(aX\equiv b {\pmod {n}}\), \((aX \equiv b (n))\), cuando \(\mathbf{mcd}(a,n)=1\), utilizamos bien solución de Bézout, bien la función \(\varphi\) de Euler. Veamos cómo la calculamos.
Definición: Para \(n\in\mathbb{Z}^+\), se define la función \(\varphi\) de Euler como \[\varphi (n)=|\{m\in\mathbb{Z}^+|m<n, mcd(n,m)=1\}|.\]
Veamos un algoritmo para calcularlo:
(%i1) | fi(n):=block([f,i], f:1, for i:2 thru n–1 do( if (mcd(i,n)=1) then f:f+1 ), f )$ |
Este algoritmo es deficiente, ya que para un \(n\) grande debe realizar demasiadas operaciones. Para reducirlo nos apoyamos en el siguiente resultado
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)\]
Observemos que si desarrollamos el producto anterior obtenemos:
\[\varphi (n)=\prod_{i=1}^rp_{i}^{k_{i}-1}(p_i-1)\]
Algoritmo
(%i2) | fiEuler(n):=block([p,d], d:descomp(n), p:1, for i:1 thru length(d) do( p:p*d[i][1]^(d[i][2]–1)*(d[i][1]–1) ), p )$ |
Factorización de un número entero
Como hemos visto, necesitamos la factorización de un número entero para conseguir de manera más eficiente el cálculo de \(\varphi ()\). Maxima nos proporciona una función que permite obtener esta factorización:
-
ifactors(n): evuelve la factorización del entero positivo \(n\). Si \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\) es la descomposición de \(n\) en números primos, ifactors devuelve \([[p_1, e_1], \ldots, [p_k, e_k]]\)
Algoritmo de factorización
La función ifactors nos devuelve la factorización de los número que habitualmente trabajamos. Pero su uso no estará permitido para números enteros de más de 10 dígitos. Para estos número utilizaremos el siguiente algoritmo de factorización:
\[\begin{array}{l}
\mathbf{input}: n,\ k;\\
m_1=\lfloor n/10^k\rfloor;\\
m_2=\mathbf{mod}(n,10^k);\\
\mbox{\* esto nos permite expresar } n=m_1\cdot 10^k+m_2 \mbox{ *\\}\\
d=\mathbf{mcd}(m_1,m_2);\\
\mathbf{if}(d< 1) \\
\qquad out=[d,(m_1/d)\cdot10^k+(m_2/d)];\\
\mathbf{else}\\
\qquad out:[1,n];\\
\mathbf{return}(out)\end{array} \]
De esta forma la función nos devolverá dos factores. Para que nos sirva la factorización \(1<out[1]\). Sin embargo, no todos los \(1<out[1]\) son adecuados, si el factor \(out[2]\) es de más de 10 dígitos no podremos hacer la factorización de él con la calculadora. En este caso, debemos volver a ejecutar el algoritmo con un \(k\) diferente, hasta que el factor \(out[2]\) sea de menos de 11 dígitos.
Ejercicio: Crear una función, \(\mathbf{fact10}(n,k)\), que devuelva la factorización de \(n\) mediante el algoritmo anterior.
Ejercicio: Utilizando lo anterior, crear una función, \(\mathbf{fact10t}(n)\), que devuelva la factorización de \(n\) si es posible o 1 en caso contrario.
Ejercicio: Sea \(N\)=9911536270272, ¿cuál es el valor de \(\varphi(N)\pmod{46}\)?.
Ecuación de congruencias
Ya estamos en condiciones de afrontar una solución general para la ecuación de congruencias \[aX\equiv b \pmod{n}\]
Ahora podemos establecer los criterios que nos permitirán conocer cuándo existe solución:
La ecuación \(aX \equiv b \pmod{n}\) tiene solución si, y sólo si, el \(\mathbf{mcd}(a,n)|b\)
El procedimiento más sencillo es cuando \(\mathbf{mcd}(a,n)=1\), que en cuyo caso siempre tiene solución y esta se obtiene buscando el inverso de \(a\) en \(\mathbb{Z}_n\).
¿Qué ocurre si \(\mathbf{mcd}(a,n)=d\) y \(d|b\)? En tal caso la solución que buscamos dependerá de la solución de
\[\frac{a}{d}X_0 \equiv \frac{b}{d} \left(\mathbf{mod}\ \frac{n}{d}\right)\]
En tal caso, las soluciones será varias y vendrás dadas por:
\[X\equiv \left[X_0+\frac{n}{d}k\right]\pmod{n}, \]
donde \(k\in \{0,1,2,\ldots,d-1\}\).
Ejercicio: Resolver la ecuación de congruencias \(4X\equiv 22 \pmod{46}\).
Ejercicio: Sea \(0<X<161\), la mayor de las soluciones de \(28X\equiv 35 {\pmod {161}}\). ¿Cuánto suman sus dígitos?
Ejercicio: ¿Cuáles son las dos últimas cifras de \(\phi(3698360937027861)\) |