Question

найдите последние две цифры 13^47^19​

Answer 1

Ответ:

97

Пошаговое объяснение:

$\displaystyle 13^{47^{19}} \ mod \ 100$

Заметим, что 13 и 100 взаимно просты, значит выполняется теорема Эйлера:

$\displaystyle 13^{\phi(100)} \equiv 1 \ mod \ 100\\\phi(100) = \phi(2^2 * 5 ^ 2) = \phi(2^2) * \phi(5^2) = (4 - 2)*(25 - 5) = 40\\13^{40} \equiv 1 \ mod \ 100$

$47^{19} \equiv y \ mod \ 40\\7^{19} \equiv y \ mod \ 40$

Заметим, что 7 и 40 взаимно просты, значит выполняется теорема Эйлера:

$\displaystyle 7^{\phi(40)} \equiv 1 \ mod \ 40\\\phi(40) = \phi(2^3 * 5) = \phi(2^3) * \phi(5) = (8 - 4)*4 = 16\\7^{16} \equiv 1 \ mod \ 40$

$7^{19} \ mod \ 40 \equiv 7^3 \ mod \ 40 \equiv 343 \ mod \ 40 \equiv 23 \ mod \ 40 \rightarrow y = 23$

$13^{47^{19}} \ mod \ 100 \equiv 13^{23} \ mod \ 100 \equiv 69 ^{11} * 13 \ mod \ 100 \equiv (-31) * 31^{10} * 13 \ mod \ 100 \equiv (-3) * 961^5 \ mod \ 100 \equiv (-3) * (-39)^5 \ mod \ 100 \equiv 17 * 39 ^ 4 \ mod \ 100 \equiv 17 * 1521^2 \ mod \ 100 \equiv 17 * 41 \ mod \ 100 \equiv 697 \ mod \ 100 \equiv 97 \ mod \ 100$