Задачка

[shukshin]

Добрый вечер, участники форума!
Есть задача
найти $2^{98765432100003}\mod 401$
решить не используя компьютерных вычислений.

Разложил руками
$98765432100003 = 32921810700001 \cdot 3$
$32921810700001 $- простое (это уже компьютер так считает, хоть и можно юзнуть какой-нибудь тест простоты и вручную)
что дальше?

смотрел на это число под разными основаниями - ничего удобного для человека ($32921810700001$ близко к $ 2^{45}$, $45$ цифр в двоичной)
(хоть и к основанию можно руками привести)
что делать-то?

[AV_77]

Теорема Ферма (которая малая).

[shukshin]

AV_77
разные основания(т.е. разные простые числа)

[AV_77]

Какие разные основания? О чем теорема Ферма говорит?

[shukshin]

AV_77
$a^p = a(\mod p )$

[AV_77]

И какие вы в этой формулировке разные простые числа видите?

[shukshin]

AV_77
абсолютно никаких. оно одно - p.
$2^{401} = 2(\mod 401)$
вы предлагаете сей факт использовать для ускорения вычислений?

[AV_77]

Именно так. Там все очень просто получится.

[shukshin]

AV_77
хорошо, попробую

[AV_77]

shukshin в сообщении #1085219 писал(а):

хорошо, попробую

Попробуйте. Только другую формулировку возьмите.