А почему остатки действительно можно складывать так, как было рассказано выше?

Докажем сделанное выше утверждение о том, что если число А дает остаток r, а число B дает остаток p от деления на какое-то число С, то число A+B дает от деления на С такой же остаток, как и число r+p.

Действительно, если A делится на C с остатком r, то A=C*m+r, где m – частное от этого деления. Аналогично, B=C*n+p (n – какое-то другое частное). Тогда A+B = C*m+r+C*n+p = C*(m+n)+r+p. То есть если r+p<C, то r+p как раз и будет остатком от деления A на C (а m+n – частным). Если же r+p≥C, то r+p – это сколько-то (скажем, k) раз по C плюс остаток от деления r+p на C (обозначим его q). Тогда и A+B=C*(m+n)+r+p – это (m+n) и плюс еще k раз по C и остаток q. Это и означает, что A+B делится на C с тем же остатком, что и r+p.

Их можно перемножать. Аналогично: если число А дает остаток r, а число B дает остаток p от деления на какое-то число С, то число A*B дает от деления на С такой же остаток, как и число r*p.

Пример: 35 дает остаток 2 от деления на 3, а 16 – остаток 1 от деления на 3. Тогда 35*16 должно давать такой же остаток, как и 2*1, то есть 2. И действительно, 35*16=560, а 560=186*3+2.

Умение перемножать остатки крайне полезно, поскольку считать огромное произведение нам совершенно не хочется (с суммой-то как-то еще можно смириться).

Пример: хотим посчитать остаток от деления 1002*1003*1004 на 7. Мы совершенно не имеем желания перемножать их и делить полученное число в столбик на 7. Вместо этого мы посчитаем нужные остатки: 1002 дает остаток 1 от деления на 7, 1003 – остаток 2 и 1004 – остаток 3. Значит, число 1002*1003*1004 дает такой же остаток от деления на 7, как и 1*2*3, то есть 6.

Делайте так же! Посчитайте (не вычисляя самого произведения) остаток:

7) 6021*1283*689 от деления на 6.

8*) Докажите, что произведение шести последовательных нечетных натуральных чисел не может быть точным квадратом.

А почему, почему остатки можно перемножать так, как было рассказано?

Докажем, что если число А дает остаток r, а число B дает остаток p от деления на какое-то число С, то число A*B дает от деления на С такой же остаток, как и число r*p.

Опять запишем A=C*m+r (где m – частное от деления A на C) и B=C*n+p. Тогда A*B = (C*m+r)*(C*n+p) = C*m*C*n+C*m*p+r*C*n+r*p (чтобы перемножить две скобки, мы умножаем все, что можно из первой скобки на все, что можно, из второй, и складываем получившееся). В этом выражении первые три слагаемых делятся на C, поэтому к остатку они ничего не добавляют. Получается, что остаток у A+B такой же, как у последнего слагаемого, то есть у r+p.

Их можно возводить в степень. Допустим, мы знаем остаток от деления числа А на число B. А хотим, например, узнать остаток от деления A¹⁰⁰ на B. Возведение в степень – это умножение числа самого на себя некоторое количество раз, в данном случае, 100. То есть A¹⁰⁰⁼A*A*…*A (100 раз). Раз так, то, как и в прошлом случае, мы можем заменить везде A на его остаток от деления на B. Иногда этого достаточно для решения задачи, например:

102 дает остаток 2 от деления на 5, значит, 102⁶ дает такой же остаток от деления на 5, как и 2⁶, а 2⁶=64, значит, искомый остаток от деления на 5 равен 4.

Но иногда даже остатки, возведенные в огромную степень, сложно посчитать. Допустим, нас интересует остаток от деления на 5 не числа 102⁶, а числа 102⁶⁶! Тогда мы не можем так же легко вычислить произведение 66 двоек. Что же делать?

А делать вот что. Мы уже поняли, что наша задача аналогична нахождению остатка от деления числа на 2⁶⁶ на 5. Как бы это сделать? Давайте искать последовательно остатки от деления на 5 у 2¹, 2², 2³ и так далее…

Итак, 2¹ дает остаток 2 от деления на 5.

2²=2¹*2 дает такой же остаток, как и 2*2 от деления на 5, то есть 4.

2³=2²*2 дает такой же остаток, как и 4*2 от деления на 5, то есть 3.

2⁴=2³*2 дает такой же остаток, как и 3*2 от деления на 5, то есть 1.

2⁵=2⁴*2 дает такой же остаток, как и 1*2 от деления на 5, то есть 2.

2⁶=2⁵*2 дает такой же остаток, как и 2*2 от деления на 5, то есть 4.

2⁷=2⁶*2 дает такой же остаток, как и 4*2 от деления на 5, то есть 3.

2⁸=2⁷*2 дает такой же остаток, как и 3*2 от деления на 5, то есть 1.

2⁹=2⁸*2 дает такой же остаток, как и 1*2 от деления на 5, то есть 2.

И так далее… чувствуете закономерность?

Остатки идут как бы по кругу: 2,4,3,1, 2,4,3,1… – ведь после появления в остатке двойки мы как бы начинаем сначала и выполняем те же действия, что и на предыдущем круге – с тем же самым результатом.

Получается, что каждая 4-я степень дает остаток 1 от деления на 5. Следовательно, к «моменту» 2⁶⁴ остаток будет равен 1, то есть 2⁶⁵ дает остаток 4, а 2⁶⁶ – остаток 3. Таким образом, искомый ответ - 3.

Таким образом, нахождение остатка от деления степени какого-то числа А на какое-то другое число B делается так:

1. Переходим к остатку А от деления на B, возведенному в ту же степень (от 102⁶⁶ к 2⁶⁶, например)

2. Вычисляем остатки первых нескольких степеней и находим цикл, по которому они «ходят».

3. Находим место цикла, в котором мы остановимся.

4. Ура!

9) Найдите остаток от деления на 11 числа 13⁴³.