¿Cuáles son las 2 últimas cifras de $31^{41}$ ?

Question

Usando un truco astuto, descubrí que los dos últimos dígitos eran $31.$ Sin embargo, quiero verificarlo utilizando el pequeño teorema de Fermat o alguno alternativo. ¿Cómo aplicaría el pequeño teorema de Fermat?

Answer 1

Desde $\phi(100) = 40$ tenemos por el teorema de Euler $$31^{40}\equiv 1 \pmod{100}$$

Así que la respuesta es $31$ .

Answer 2

Tenga en cuenta que $$ a^{\varphi(100)}=1 $$ donde $\varphi$ es la función totiente de Euler. $$ \varphi(100)=\varphi(2^2)\varphi(5^2)=2(20)=40 $$ ya que es multiplicativo en números relativamente primos. Obsérvese también que $$ \varphi(p^2)=p(p-1) $$ ahora es fácil concluir.

Answer 3

El planteamiento de John Watson es el que yo seguiría, pero para añadir una alternativa, podemos plantear $31^{41}\pmod{100}$ utilizando el Algoritmo de cuadrado y multiplicación . En primer lugar, tenga en cuenta que $41=101001_{\text{two}}$ $$ \begin{array}{r|r|rl} n&\text{base two}&31^n\pmod{100}\\ 0&0&1\\ 1&1&31&\text{multiply}\\ 2&10&61&\text{square}\\ 4&100&21&\text{square}\\ 5&101&51&\text{multiply}\\ 10&1010&1&\text{square}\\ 20&10100&1&\text{square}\\ 40&101000&1&\text{square}\\ 41&101001&31&\text{multiply} \end{array} $$

Answer 4

Me has cambiado el problema después de responder. Así que..:

Dos encontrar los dos últimos dígitos, sólo tiene que trabajar en $\mathbb Z\bmod100.$ \begin{align} 33^1 & \equiv 31 \\ 31^2 & \equiv 31\times 31 \equiv 61 \\ 31^3 & \equiv 31\times61 \equiv 91 \\ 31^4 & \equiv 31\times91 \equiv 21 \\ 31^5 & \equiv 31\times21 \equiv 51 \\ 31^6 & \equiv 31\times51 \equiv 81 \\ 31^7 & \equiv 31\times81 \equiv 11 \\ 31^8 & \equiv 31\times11 \equiv 41 \\ 31^9 & \equiv 31\times41 \equiv 71 \\ 31^{10} & \equiv 31\times71 \equiv 1 \end{align} Por lo tanto $$ 31^{41} = 31^{10}\times31^{10}\times31^{10}\times31^{10}\times31^1 \equiv 1\times1\times1\times1\times31 \equiv 31. $$

Dos encontrar los dos últimos dígitos, sólo tiene que trabajar en $\require{cancel}\xcancel{\mathbb Z\bmod100.}$ $$ \xcancel{ \begin{align} 32^1 & \equiv 32 \\ 32^2 & \equiv 32\times 32 \equiv 24 \\ 32^3 & \equiv 32\times24 \equiv 68 \\ 32^4 & \equiv 32\times68 \equiv 76 \\ 32^5 & \equiv 32\times76 \equiv 32 \end{align}} $$ Después de cinco pasos vuelves a $32.$

Cada vez que des cuatro pasos más allá de donde tenías $32,$ tienes $32$ de nuevo. Así que $41 = 1 + (1\times4)$ así que pasas por ese ciclo $10$ veces, volviendo a $32.$

Answer 5

Pista:

$$(1+10n)^m\equiv1+\binom m1(10n)^1\pmod{100}$$

Ahora, $41\cdot3\equiv3\pmod{10}$

$\implies41\cdot30\equiv30\pmod{100}$