Помогите найти последние 4 цифры числа 17^(26^(39)). Не могу понять как правильно тут использовать теорему Эйлера.

задан 8 Ноя 20:41

Поскольку 17 и 10^4 взаимно просты, достаточно знать остаток от деления показателя на ф(10^4)=4000. Далее получается задача аналогичного типа, только там 4000 надо представить как произведение 2^5 и 5^3. Остаток от деления 26^39 на 2^5 равен нулю, и остаётся найти остаток от деления на 5^3, что делается при помощи "быстрого" возведения в степень. Потом применяем китайскую теорему об остатках.

По ходу дела тут кое-какие упрощения возможны, но это можно отдельно обсудить.

(8 Ноя 20:51) falcao

Маленькое добавление: 26^39=(1+5^2)^39, и с учётом биномиальной формулы получается 1+39*5^2=101 mod 5^3. Это несколько упрощает вычисления. Правда, в конце надо будет находить 17^476 mod 5^4, и вручную это не очень легко. Ответ получится 9281.

(8 Ноя 22:24) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×670
×613

задан
8 Ноя 20:41

показан
38 раз

обновлен
8 Ноя 22:24

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru