Остатки
Остаток суммы или произведения можно найти по остаткам слагаемых и множителей. Так огромные числа превращаются в маленькие.
Главное
- (a + b) mod m = ((a mod m) + (b mod m)) mod m.
- То же для произведений: заменяй каждый множитель его остатком.
- Остатки степеней повторяются циклом.
Пример
Остаток от деления 2¹⁰ на 7
- 2³ = 8, остаток 1.
- 2¹⁰ = (2³)³ · 2 даёт остаток 1 · 1 · 1 · 2 = 2.
Проверь себя
Остаток от деления 23 · 17 на 5
- 2
- 3
- 1
Показать ответ
Правильно: 1. 23 даёт 3, 17 даёт 2; 3 · 2 = 6, а 6 даёт 1.
Решать задания по теме бесплатно →
Тема входит в: Олимпиадная математика.