Дискретка, степень в степени по модулю

[Dexter_Fl]

Добрый день!

Есть задача:
Найти $ 2^{5^{239}} \mod 17 $

Мой вариант решения:

Смотрим остатки от основания (2) по $ \mod 17 $. Замечаем зацикливание, т.е. имеем 8 оригинальных остатков, а дальше зацикливание. Далее, рассматриваем $ {5^{239}} по \mod k$, где $k$ - количество оригинальных остатков в предыдущем действии, т.е. 8. Смотрим остатки и ищем зацикливание. Здесь их 2, дальше зацикливание. Т.о. для нечетной степени остаток 5. Далее рассматриваем выражение: $ 2^{8k + 5} \mod 17 $ , что не трудно.

Пожалуйста, подскажите, правильны ли рассуждения и есть ли более удачные решения?

[Legioner93]

Я такие примеры решал с помощью теоремы Эйлера, строго алгоритмично - искать зацикливания не надо.

[Sonic86]

Теорема Эйлера немного погрубее, чем рассуждения ТС. ТС просто выражается не на языке ТЧ.
Кратко, $a^b \bmod m = a^{b \bmod P_m(a)}\bmod m$, где $P_m(a)$ - порядок $a$ по модулю $m$, т.е. минимальный показатель, для которого $a^{P_m(a)}\equiv 1 \pmod m$, при этом $P_m(a)$ делит $\varphi(m)$.
Просто применяете эту формулу до самого верха степенной башни и уже считаете.

Dexter_Fl в сообщении #733980 писал(а):

Далее, рассматриваем $ {5^{239}} по \mod k$, где $k$ - количество оригинальных остатков в предыдущем действии, т.е. 8.

Короче говоря, рассматриваем $5^{239}\bmod 8$ - вот и считайте ее также, ее легче считать. А потом обратно спускайтесь вниз.

[Legioner93]

Ну я всё же покажу.
1) $2^{\varphi(19)}=2^{18}=1 \pmod{19}$
2) $5^{\varphi(18)}=5^6=1 \pmod {18}$
3) $239 = 5 \pmod{6}$ - это можно и руками уже посчитать
4) из п.2) $5^{239}=5^{6k+5}=5^5 \pmod {18}$. Такие штуки можно посчитать как-нибудь так (для больших чисел конечно, тут можно и уголком поделить): $5^2 = 7 \pmod {18}$, $5^4= 49 \pmod {18}=13 \pmod {18}$, $5^5=5\cdot 13 \pmod {18} = 11 \pmod {18}$
5) из п.1) и 4) $2^{5^{239}}=2^{18k+11}=2^{11} \pmod {19}$. Считаем снова как п.4 ($2^{11}=2^{2^3+2+1}$) или уголком, получаем $15$.

[iifat]

Legioner93 в сообщении #734003 писал(а):

$2^{\varphi(19)}=2^{18}=1 \pmod{19}$

Имелось в виду, наверное, $2^{\varphi(17)}=2^{16}=1 \pmod{17}$ с соответствующими правками далее?

[Legioner93]

iifat
Ага, спасибо. Это я нашел $2^{5^{239}} \pmod{19}$. Невнимательность:)
Ну, принцип всё равно понятен.

[Dexter_Fl]

Большое спасибо за ответы!
А как можно себя проверить на предмет верности ответа?

[ИСН]

Проверить простыми средствами - возможно, никак. Да и зачем.
А для уверенности в себе - найти то же самое mod 51; если сойдётся - ОК.

[Legioner93]

ИСН в сообщении #734225 писал(а):

Проверить простыми средствами - возможно, никак. Да и зачем.

Да есть одно народное средство...
http://www.wolframalpha.com/input/?i=2%5E5%5E239+mod+17

[ИСН]

А, ну да.