_Hallar el resto de la división de \( 2004^{16949687} \) por \( 1373 \)
De comienzo tenemos :
\( 2004^{16949687} \)\( \equiv{Xmod(1373)} \)
Usando el Teorema de Fermat:
\( a^{p-1}\equiv{1mod(p)} \) confirmando que \( MCD\longrightarrow{}(a:p)=1 \)
Supongo que comprobaste que 1373 es primo.
Nos quedaría así:
\( 2004^{1372\times{12353+1371}}\equiv{Xmod(1373)} \)
Aplicando el teorema sabemos que:
\( 2004^{1372\times{12353}}\equiv{1mod(1373)} \)
Por lo tanto me quedaría resolver esto:
\( 2004^{1371}\equiv{Xmod(1373)} \)
Y aquí no se como podría seguir resolviendo...
Podemos reducir la base módulo \( 1373 \):
\( 2004^{1371}\equiv{631^{1371}}\equiv{X}\;(mod\;1373) \)
Aunque tampoco no es imprescindible, es más cómodo trabajar con un número más pequeño.
Tenemos ahora dos caminos:
i) \( 631^{1371}·631 = 631^{1372}\equiv{1}\,(mod\;1373) \)
Luego \( X \equiv{ 631}^{-1} (mod\; 1373) \)
\( 631·X \equiv{1}\; (mod\;1373) \Rightarrow{} 631·X - k·1373 = 1 \)
Entonces se puede calcular \( X \) resolviendo mediante el algoritmo de Euclides la ecuación diofántica lineal.
ii) Se puede calcular por sucesivas elevaciones al cuadrado. Para ello, se expresa 1372 como suma de potencias de 2,
\( 1372 = 1024 + 256 + 64 + 16 + 8 + 4 \Rightarrow{} 631^{1372} = 631^{1024}·631^{256}·631^{64}·631^{16}·631^{8}·631^4 \)
Estas potencias \( mod\; 1373 \) se calculan muy fácilmente elevando al cuadrado la anterior, y luego se multiplican reduciendo de cada vez \( mod \;1373 \).
Si necesitas que te desarrolle algo más cualquiera de los dos métodos, dímelo.
Saludos,
