Найти остаток от деления:
1) числа 39^46 на 5;
2) числа 64^29 на 7;
3) числа 103^15 на 17;
4) числа 10^10 + 28^3 - 1 на 3;
5) числа 7*10^30 на 9
Помогите пожалуйста

Заметим, что дает такой же остаток при делении на s, что и . (Доказывается, например, так. Раскрываем скобки:

Очевидно, на каждом шаге будет образовываться слагаемое, делящееся на qs, и степень умноженная на r. Все слагаемые первого типа на остаток не влияют, так что остается только )

Кроме того, остаток от деления от суммы равен остатку от деления от суммы остатков (as + b + cs + d = (a + c)s + (b + d) дает такой же остаток при делении на s, что и b + d), а так же произведение можно менять на произведение остатков

Применяем наблюдения: