Найти остаток от деления $%2^{100}$% на $%101$%, $%8^{900}$% на $%29$%, $%3^{2000}$% на $%43$%.

задан 4 Май '15 23:25

изменен 5 Май '15 21:24

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Можете дать ответ только на третье

(4 Май '15 23:37) guru

Книгу Скопенкова читаете?)))

(22 Окт '21 21:00) Antontina
10|600 символов нужно символов осталось
2

Числа 101, 29, 43 простые. Поэтому достаточно применить малую теорему Ферма: число $%a^{p-1}$% даёт в остатке 1 при делении на простое число $%p$% для любого $%a$% не делящегося на $%p$%.

В первом случае сразу ясно, что ответом будет 1. Во втором случае $%900$% делим с остатком на $%p-1=28$%. Получается 4. Поэтому $%8^{900}$% даёт тот же остаток, что и $%8^4=2^{12}$%. Делим 4096 на 29 "столбиком" и получаем 7.

В последнем примере делим 2000 с остатком на 42. Получается 26. Значит, надо найти остаток от деления $%3^{26}$% на 43. Это делается последовательным возведением в квадрат. Число $%3^2$% даёт в остатке 9. Число $%3^4$% -- то же остаток, что и $%9^2=81$%, что удобно заменить на $%-5$%. Тогда $%3^8$% даст 25, а $%3^{16}$% даст 23 (остаток числа 625 от деления на 43). Теперь замечаем, что $%26=16+8+2$%, то есть надо перемножить числа 23, 25 и 9, и найти остаток для произведения. Сначала перемножаем 23 и 25, получаем 575; остаток 16. После умножения на будет 144, где остаток равен 15.

ссылка

отвечен 4 Май '15 23:44

10|600 символов нужно символов осталось
1

Согласно Малой теоремы Ферма $$a^{p-1}\equiv 1 (\mod p)$$ $$2^{100} \equiv 1 (\mod 101)$$

В третьем случае $$3^{42} \equiv 1 (\mod 43)$$ $$3^{2000}=3^{42 \cdot 47 + 26} \equiv 3^{26} (\mod 43)$$

ссылка

отвечен 4 Май '15 23:37

изменен 4 Май '15 23:40

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×5,148

задан
4 Май '15 23:25

показан
1671 раз

обновлен
22 Окт '21 21:00

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

по почте:

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

по RSS:

Ответы

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

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