|
Найдите остаток от деления на 7 числа 10^10 + 10^100 + 10^1000 + ... + 10^10000000000. задан 31 Окт '16 23:47 
Антон Коваль |
|
Основание степени 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 @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)
Антон Коваль
|