¿Existe una fórmula general para calcular la n-ésima cifra de cualquier número grande?
Respuestas
¿Demasiados anuncios?Tras la pregunta del título,
3^{100}=9^{50}=(10-1)^{50}\equiv\binom{50}210^2-\binom{50}110+1\pmod{1000}
Ahora, \binom{50}210^2-\binom{50}110=\frac{50\cdot49}210^2-500 =2500\cdot49-500=2500\cdot48+(2500-500)\equiv0\pmod{1000}
Alternativamente, utilizando Función de Carmichael , \lambda(1000)=100
Nos gustaría calcular 3^{100}\pmod{100} . Esto nos dirá los dos últimos dígitos de 3^{100} que incluye la cifra de las decenas.
Procedemos de la siguiente manera: 3^4 = 81 Así que..:
\begin{align} 3^8 & \equiv (81)^2 \equiv 61 \pmod{100} \\ 3^{16} & \equiv (61)^2 \equiv 21\pmod{100} \\ 3^{24} & \equiv 61\cdot 21 \equiv 81\pmod{100}\\ 3^{48} & \equiv (81)^2 \equiv 61 \pmod{100} \\ 3^{50} & \equiv 9\cdot 61 \equiv 49\pmod{100} \\ 3^{100} & \equiv (49)^2\equiv 01 \pmod {100} \end{align}
Así que los dos últimos dígitos son 01
.
En general es muy rápido de calcular a^b\pmod n . Usted calcula a^{\lfloor b/2 \rfloor}\pmod n (utilizando este método de forma recursiva si es necesario) y elevarlo al cuadrado, de nuevo mod n ; si b es impar se multiplica el resultado por a y ya está.