Найти остаток от деления числа 3^3^3000 на 297

Предыдущий
вопрос Следующий
вопрос

Для нахождения остатка от деления числа (3^{3^{3000}}) на 297, можно воспользоваться теоремой Эйлера.

Сначала находим остаток от деления (3^{3000}) на (\varphi(297)), где (\varphi) – функция Эйлера. Так как 297 = 3 3 3 11, то (\varphi(297) = 297 (1 - \frac{1}{3}) * (1 - \frac{1}{11}) = 162).

Теперь находим остаток от деления 3000 на 162:

3000 = 162 * 18 + 36

Таким образом, (3^{3000} \equiv 3^{36} \pmod{297}).

Теперь находим остаток от деления (3^{36}) на 297:

(3^{36} = (3^{2})^{18} = 9^{18} = (9^{2})^{9} = 81^{9}).

(81^{9} \pmod{297}) = (81 81 81...* 81) (\pmod{297}) = 21.

Наконец, найдем остаток от деления (3^{21}) на 297 (здесь мы используем свойство того, что (3^3 \equiv 27 \pmod{297})):

(3^{21} = 3^{18} 3^{3} \equiv 1 27 \pmod{297}).

Ответ: искомый остаток равен 27.