Truco con exponenciación

Question

Por ejemplo,

$$123^{25} \pmod{10}$$

$$ 123 \equiv 3 \pmod{10}$$

$$123^{2} \equiv 9 \pmod{10}$$

$$123^{3} \equiv 7 \pmod{10}$$

$$123^{4} \equiv 1 \pmod{10}$$

$$123^{5} \equiv 3 \pmod{10}$$

Es fácil ver:

$$123^n \equiv 123^{4(k) + n} \pmod{10}$$

$$4(6) = 4(k) = 24$ $ Por lo tanto,

$$123^{1} \equiv 123^{4(6) + 1} \equiv 123^{25} \pmod{10} \equiv 3 \pmod{10}$$

Mi pregunta es ¿por qué este trabajo?

Answer 1

Sí, $\,{\rm mod}\ 10\!:\ \color{#c00}{3^4\equiv 1}\,\Rightarrow\, 3^{J+4K}\!\equiv 3^J(\color{#c00}{3^4})^K\!\equiv 3^J\color{#c00}1^K\!\equiv 3^J $ $ $ Congruencia de Energía, Producto de las Reglas.

Si $\,a\,$ es coprime a $\,m\,$ $\ a^{\varphi(m)}\equiv 1\pmod{m}\ $ por el Teorema de Euler. Por lo tanto mod $\,m,\,$ la secuencia de potencias de $\,a\,$ será periódico. El período exacto de la longitud, es decir, el menos $\,n\,$ tal que $\,a^n\equiv 1\pmod m\,$ es conocida como la orden de $\,a\ {\rm mod}\ m.\,$ puede ser menos de $\,\varphi(m),\,$, pero debe ser divisor de $\,\varphi(m).$

Answer 2

La primera de todas las $123^n = (120+3)^n = (12\times10+3)^n = \sum_1^n \binom{n}{k}\times(12\times10)^k\times3^{n-k} \equiv 3^n \pmod {10}$, debido a que todos los múltiplos de $10 \equiv 0 \pmod {10}$. Tan solo es necesario solucionar $3^{25} \pmod {10}$

Esto reduce a $3^n \equiv 3^{n+4k} \pmod{10}$. Por qué $4$? Como @André Nicolas dicho, esto es debido a el teorema de Euler decir $a^{\varphi(m)}\equiv 1 \pmod m$ si $\mathrm{gcd}(a,m) = 1$. Esto significa $3^n \pmod {10}$ solo golpe números coprime a $10$, y estos son los cuatro números de $\{1,\,3,\,7,\,9\}$. Ninguno de estos números compartir un divisor con $10$. Esto también significa que $3^n \pmod {10}$ no puede golpear $\{0,\,2,\,4,\,5,\,6,\,8\}$, ya que por ejemplo, no hay ningún número $n$ tal que $3^n = 4 \pmod{10}$. Así que, ya que sólo pueden golpear a los cuatro números de $\{1,\,3,\,7,\,9\}$, sólo lo hará, y repito una vez que ha golpeado los cuatro números.