¿Cuál es el resto cuando 347 ^ 347 se divide por 100?

Answer 1

347 es primo, por lo que, en particular, es relativamente primo a 100.

Eso significa que puede usar el teorema de Euler (teorema de Euler – Wikipedia).

Esto dice que

[matemáticas] 347 ^ {347} \ equiv 347 ^ {347 \% \ phi (100)} \ equiv 347 ^ {347 \% 40} \ equiv 47 ^ {27} \, \ text {mod} \, 100 [ /matemáticas]

Computación que todavía es mucho trabajo, por lo que podría ir más allá y utilizar el Teorema del resto chino (Teorema del resto chino – Wikipedia).

Por líneas similares a las anteriores,

[matemáticas] 47 ^ {27} \ equiv 47 ^ {27 \% \ phi (4)} \ equiv 47 ^ {27 \% 2} \ equiv 47 \ equiv 3 \, \ text {mod} \, 4 [/ matemáticas]

y

[matemáticas] 47 ^ {27} \ equiv 47 ^ {27 \% \ phi (25)} \ equiv 47 ^ {27 \% 20} \ equiv 47 ^ 7 \ equiv 22 ^ 7 \ equiv 13 \, \ text { mod} \, 25 [/ matemáticas]

Ahora usamos CRT para traer [math] (3,13) \ in \ mathbb {Z} _4 \ times \ mathbb {Z} _ {25} [/ math] de nuevo a [math] \ mathbb {Z} _ {100 }. [/ math] La fórmula para esto es un poco complicada, así que solo usaré Sage.

Sage Cell Server

La respuesta es 63.

Si quieres pasar de (3,13) a 63 a mano, puedes usar la fórmula de Garner:

[matemáticas] x = (((ab) (q ^ {- 1} \, \ text {mod} \, p)) \, \ text {mod} \, p) q + b [/ math]

donde [math] x \ equiv a \, \ text {mod} \, p [/ math] y [math] x \ equiv b \, \ text {mod} \, q. [/ math]

Answer 2

Primero, 347 ^ 347 (mod 100) será igual a 47 ^ 347 (mod 100) porque solo importan los dos últimos dígitos en cada resultado intermedio.

A continuación, busque un patrón en los últimos dos dígitos de algunas potencias fácilmente calculadas de 47: 47 ^ 1, 47 ^ 2, etc. Para facilitar el cálculo de estas potencias, simplemente mantenga los dos últimos dígitos de cada resultado intermedio, y tirar el resto.

Cuando haga esto, verá que obtiene un ciclo: 47, 09, 23, 81, 07, 29, 63, 61, 67, 49, 03, 41, 27, 69, 43, 21, 87, 89, 83, 01, 47, … son los dos últimos dígitos de todas las potencias de 47 desde 47 ^ 1 a 47 ^ 21. Cuando llegas a 47 ^ 21, ves que el ciclo comienza a repetirse.

Ahora sabe que 47 ^ 347 (mod 100) = 47 ^ 327 (mod 100) = 47 ^ 307 (mod 100), etc. Continúe, y pronto se dará cuenta de que 47 ^ 347 (mod 100) = 47 ^ 7 (mod 100), que ya sabemos de la lista anterior, termina en 63.

Nunca está de más comprobarlo en Wolfram Alpha. 🙂