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$

Answer 2

Для нахождения последних двух цифр числа, возведенного в степень, можно воспользоваться тем, что числа по модулю 100 (последние две цифры) повторяются с определенным периодом. Например, последние две цифры числа 13 в разных степенях имеют следующий период:

13^1 = 13 13^2 = 169 13^3 = 2197 13^4 = 28561 13^5 = 371293

Мы видим, что последние две цифры меняются следующим образом: 13, 69, 97, 61, 93. Период равен 5.

Теперь нам нужно вычислить остаток от деления 47^19 на 5. Это можно сделать, вычислив остаток от деления 47 на 5:

47^1 = 47 (остаток от деления на 5 - 2) 47^2 = 2209 (остаток от деления на 5 - 4) 47^3 = 103823 (остаток от деления на 5 - 3) 47^4 = 4882421 (остаток от деления на 5 - 1) 47^5 = 229996859 (остаток от деления на 5 - 4)

Таким образом, остатки от деления степеней 47 на 5 дают последовательность: 2, 4, 3, 1, 4.

Теперь мы можем возвести 13 в степень, равную остатку от деления 47^19 на 5:

13^(47^19) = 13^(5k + остаток) = 13^(5k) * 13^остаток

Поскольку 13^(5k) заканчивается на 1 (по периодичности), нам нужно вычислить 13^остаток. В данном случае остаток равен 4, и мы видели выше, что 13^4 заканчивается на 61. Таким образом, последние две цифры числа 13^(47^19) равны 61.