Как тут применить китайскую теорему об остатках?

Question

[MuffinLover3]

Вычислить две последние цифры в десятичной записи 7^9^9

Answer 1

[galaxy]

Мм, для начала, (7^9)^9 или 7^(9^9)?

Насчет китайской теоремы не соображу, но степени семерки имеют остатки от деления на 100 (две последние цифры то есть): 01, 07, 49, 43 и далее по кругу. Надо определить остаток от деления на 4 показателя степени - он в любом случае равен 1, как у любой степени 9. Значит, ответ - 07

Answer 2

[Wataru]

Найдите остаток от деления искомой штуки на 4 и на 25. Далее примените китайскую теорему об остатках.

Так проще, потому что остаток от деления a^(b^c) на степень простого числа можно найти по малой теореме Эйлера:

a^(b^c) = a ^ (b^c % (p-1)p^(n-1)) mod p^k.

Т.е. 7^9^9 = 7^((9^9) % 20) mod 25

9^9 % 20 уже можно вычеслить через логарифмическое возведение в степень.

Аналогично для 4.

Правда, тут можно и без теоремы об остатках. Надо просто сразу применить теорему ейлера. фи(100) надо только аккуратно вычислить. И числа будут чуть больше, но все-равно подъемные.