Найдите остаток от деления на 7 числа 10^10 + 10^100 + 10^1000 + ... + 10^10000000000.

задан 31 Окт '16 23:47

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

Основание степени 10 можно заменить на 3. Мы знаем, что 3^6 = 1 (mod 7). Поэтому числа 10^1, 10^2, ... , 10^{10} в показателях можно рассматривать по модулю 6. Очевидно, что все они чётны, а при делении на 3 дают в остатке 1 (за счёт того, что 10 = 1 (mod 3)). Поэтому у них у всех остаток от деления на 6 равен 4. Следовательно, каждое из слагаемых при делении на 7 даёт тот же остаток, что и 3^4 = 81 = 4 (mod 7). Складывая 10 таких чисел, мы имеем 40, что даёт остаток 5 от деления на 7.

ссылка

отвечен 1 Ноя '16 5:12

@falcao Извините за тупой вопрос. "Мы знаем, что 3^6 = 1 (mod 7). Поэтому числа 10^1, 10^2, ... , 10^{10} в показателях можно рассматривать по модулю 6".. Почему?

(1 Ноя '16 16:37) Антон Коваль

@Антон Коваль: это здесь как раз основной момент, который надо понять. Допустим, я хочу возвести 3 с степень 1000. Я знаю, что возведение в 6-ю степень, а также в 12-ю, 18-ю, ... даёт 1. Значит, я 1000 делю на 6 с остатком: 1000=6k+4, где k целое. Тогда 3^{1000}=(3^6)^k*3^4=3^4 (mod 7). Это и значит, что в показателе можно брать вместо самого числа (1000) его остаток от деления на 6 (т.е. 4).

(1 Ноя '16 19:45) falcao

@falcao спасибо

(1 Ноя '16 20:29) Антон Коваль
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×5,186
×1,005
×68

задан
31 Окт '16 23:47

показан
2452 раза

обновлен
1 Ноя '16 20:29

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

по почте:

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

по RSS:

Ответы

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

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