2
1

Найдите остаток при делении числа 111...11 (69 единиц) на а) 71 б) 70

задан 6 Ноя '16 11:45

По очень простой причине: 10 и 3 по модулю 7 -- это совершенно одно и то же. Это вещь "базовая", на ней основана сама идея сравнений по модулю. Скажем, число 100 я бы заменил на 2, то есть на остаток от деления.

(6 Ноя '16 20:21) falcao
10|600 символов нужно символов осталось
0

Рассматриваемое число равно $%\dfrac{10^{69}-1}9$%. В пункте а) применяем малую теорему Ферма, согласно которой $%10^{70}\equiv1\pmod{71}$%. Пусть $%r$% -- искомый остаток. Тогда $%90r\equiv10^{70}-10\equiv-9\pmod{71}$%. Сокращаем на 9, и далее решаем линейное сравнение $%10r\equiv-1\pmod{71}$%. После домножения на 7 оно даёт $%70r\equiv-7\pmod{71}$%, откуда $%r\equiv7\pmod{71}$%. То есть остаток равен $%7$%.

Нахождение остатка по модулю 70 сводится к нахождению остатков по модулю 2, 5, 7. Здесь можно вместо этого рассмотреть остатки от деления на 10 и на 7. Для первого случая остаток равен 1 (последняя десятичная цифра). По модулю 7 всё также просто: если $%r$% -- искомый остаток, то $%9r\equiv10^{69}-1\equiv3^{69}-1\equiv3^3-1\equiv26\equiv-2\pmod7$%. Здесь также была использована малая теорема Ферма, согласно которой $%3^6\equiv1\pmod7$%, и тогда $%3^{69}=(3^6)^{11}3^3\equiv3^3\pmod7$%.

Теперь $%2r\equiv9r\equiv-2\pmod7$%, то есть $%r\equiv-1\equiv6\pmod7$%. То число, которое мы ищем, даёт остаток 1 при делении на 10 и остаток 6 при делении на 7. Можно решить систему линейных сравнений, но проще найти его подбором: согласно китайской теореме об остатках, число с таким свойством по модулю 70 существует и единственно. И тогда ясно, что если прибавить к числу 1, то оно будет оканчиваться на 2 и делиться на 7. Из таблицы умножения мы видим, что это 42. Значит, остаток в пункте б) равен $%41$%.

ссылка

отвечен 6 Ноя '16 12:26

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

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

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

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

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

отмечен:

×3,924
×170
×49

задан
6 Ноя '16 11:45

показан
1195 раз

обновлен
6 Ноя '16 20:21

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

по почте:

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

по RSS:

Ответы

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

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