Арифметика остатков (арифметика сравнений) — раздел теории чисел, который рассматривает остатки от деления чисел на определённое число (модуль). Вместо работы с числами можно проделывать арифметические операции с их остатками по определённому модулю.
Это мощный инструмент, который помогает:
- упрощать большие числа,
- решать задачи на делимость и остатки,
- понимать, как работают компьютеры и шифры.
Что значит «a ≡ b (mod m)»?
Это значит: если разделить a и b на m, то остатки будут одинаковые.
Примеры:
- 17 ≡ 5 (mod 6) — потому что 17 : 6 = 2 остаток 5, и 5 : 6 = 0 остаток 5.
- 25 ≡ 1 (mod 4) — 25 : 4 = 6*4=24 → остаток 1, и 1 : 4 → остаток 1.
- 100 ≡ 0 (mod 10) — 100 делится на 10 без остатка, как и 0.
Как считать ?
Любое число можно «привести по модулю», найдя его остаток от деления.
Пример:
Найдём 47 mod 5 → 47 : 5 = 9*5 = 45 → остаток 2 → значит, 47 ≡ 2 (mod 5)
Теперь можешь заменять числа на их остатки — это упрощает вычисления!
Операции по модулю — калькулятор
Можно складывать, вычитать и умножать — и делать это по модулю.
Пример 1: Сложение
14 + 9 (mod 6)
→ 14 ≡ 2 (mod 6), 9 ≡ 3 (mod 6)
→ 2 + 3 = 5 → 14 + 9 ≡ 5 (mod 6)
Проверим: 14 + 9 = 23 → 23 : 6 = 3*6=18 → остаток 5. ✅
Пример 2: Умножение
7 × 8 (mod 5)
→ 7 ≡ 2 (mod 5), 8 ≡ 3 (mod 5)
→ 2 × 3 = 6 ≡ 1 (mod 5) → ответ: 1
Проверим: 7×8=56 → 56 : 5 = 11*5=55 → остаток 1. ✅
| Сложение | (a + b) mod m = (a mod m + b mod m) mod m | (15 + 18) mod 7 = (1 + 4) mod 7 =5 |
| Умножение | (a × b) mod m = (a mod m × b mod m) mod m | (6 × 9) mod 5 = (1 × 4) mod 5 =4 |
| Возведение в степень | aⁿ mod m = (a mod m)ⁿ mod m | 7¹⁰⁰ mod 6 = 1¹⁰⁰ mod 6 =1 |
Деление
Делить по модулю можно, только если есть обратный элемент .
Что такое обратный элемент?
Обратный элемент к числу a по модулю m — это такое число b, что a × b ≡ 1 (mod m)
Тогда мы можем “делить” на a, умножая на b.
Обозначается: a⁻¹ ≡ b (mod m)
Пример: найдём обратный к 3 по модулю 7
Ищем x, чтобы 3 × x ≡ 1 (mod 7)
Перебираем x от 1 до 6:
- 3×1 = 3 ≡ 3
- 3×2 = 6 ≡ 6
- 3×3 = 9 ≡ 2
- 3×4 = 12 ≡ 5
- 3×5 = 15 ≡ 1 ← Нашли!
→ Значит, обратный к 3 по модулю 7 — это 5
→ Пишем: 3⁻¹ ≡ 5 (mod 7)
Теперь можешь «делить на 3», умножая на 5.
А всегда ли есть обратный элемент?
Нет! Обратный элемент существует только если a и m — взаимно просты (то есть НОД(a, m) = 1).
Примеры:
- Есть обратный к 3 mod 7? → НОД(3,7)=1 → да
- Есть обратный к 4 mod 8? → НОД(4,8)=4 → нет
- Есть обратный к 5 mod 12? → НОД(5,12)=1 → да
Решение уравнений
Теперь ты можешь решать уравнения типа: ax ≡ b (mod m)
Шаги:
- Найди обратный к a → a⁻¹
- Умножь обе части на a⁻¹ → x ≡ b × a⁻¹ (mod m)
Пример. 4x ≡ 3 (mod 9)
- Найдём 4⁻¹ mod 9 → мы уже знаем: 7 (см. выше)
- Умножим обе части на 7:
x ≡ 3 × 7 = 21 ≡ 3 (mod 9)
(21 — 2×9 = 21-18=3)
✅ Ответ: x ≡ 3 (mod 9)
Зачем это нужно?
- Задачи на остатки:
Какой остаток даёт 2025 при делении на 7? → 2025 mod 7 = ? - Олимпиадные задачи:
Доказать, что n² + n всегда чётно. → Решается через mod 2. - Программирование:
%— оператор «остаток от деления».if (x % 2 == 0)— проверка на чётность. - Шифрование:
В сложных системах (например, RSA) всё строится на модулярной арифметике. - Расписание, календари:
Дни недели: 7 дней → mod 7.
Если сегодня понедельник (0), то через 10 дней: 10 mod 7 = 3 → четверг.
Простая задачка для тренировки
Задача: Найди остаток от деления 3¹⁰ на 5.
Решение:
- Посчитаем степени 3 по модулю 5:
- 3¹ = 3 → 3 mod 5 = 3
- 3² = 9 → 9 mod 5 = 4
- 3³ = 27 → 27 mod 5 = 2
- 3⁴ = 81 → 81 mod 5 = 1 ← важный момент!
- 3⁵ = 3⁴ × 3 ≡ 1 × 3 = 3 (mod 5) — и цикл повторяется!
Цикл: 3, 4, 2, 1 → длина 4.
- 10 : 4 = 2 остаток 2 → значит, 3¹⁰ ≡ второй элемент цикла → 4
✅ Ответ: 4
Задачи для самостоятельной работы
1. Найди остаток от деления:
а) 47 на 6
б) 100 на 7
в) 2025 на 10
2. Верно ли, что:
а) 23 ≡ 3 (mod 5)
б) 50 ≡ 0 (mod 8)
в) 17 ≡ -1 (mod 9)
3. Вычисли:
а) (15 + 22) mod 7
б) (8 × 6) mod 5
в) (100 — 33) mod 9
4. Сегодня среда. Какой день недели будет через 100 дней? (Пн=0, Вт=1, …, Вс=6)
5. Докажи, что сумма двух нечётных чисел — чётна, используя mod 2.
6. Найди последнюю цифру числа 7²⁰. (Подсказка: последняя цифра — это mod 10)
7. Найди остаток от деления 2¹⁰⁰ на 3.
8. Реши уравнение: 3x ≡ 1 (mod 7).
9. Проверь, делится ли число 123456789 на 3, используя mod 3 и сумму цифр.
10. Докажи, что для любого целого n: n³ — n делится на 6.
Ответы и решения
1.
а) 47 : 6 = 76=42 → остаток 5
б) 100 : 7 = 147=98 → остаток 2
в) 2025 : 10 → остаток 5 (последняя цифра!)
2.
а) 23 : 5 = 45=20 → остаток 3 → да, верно
б) 50 : 8 = 68=48 → остаток 2 → нет, неверно
в) 17 : 9 = 1*9=9 → остаток 8. А -1 mod 9 = 8 → да, верно
3.
а) 15+22=37 → 37 : 7 = 57=35 → остаток 2
б) 8×6=48 → 48 : 5 = 95=45 → остаток 3
в) 100-33=67 → 67 : 9 = 7*9=63 → остаток 4
4.
Среда = 2 (если Пн=0).
100 mod 7 = 2 (т.к. 98 делится на 7, 100-98=2)
→ 2 + 2 = 4 → пятница
5.
Нечётное число ≡ 1 (mod 2)
1 + 1 = 2 ≡ 0 (mod 2) → чётное. Доказано!
6.
Ищем 7²⁰ mod 10.
Цикл последних цифр у 7:
7¹=7 → 7
7²=49 → 9
7³=343 → 3
7⁴=2401 → 1
7⁵=…7 → цикл длины 4: 7, 9, 3, 1
20 : 4 = 5 → без остатка → последний в цикле → 1
✅ Ответ: 1
7.
2¹⁰⁰ mod 3
Заметим:
2 ≡ -1 (mod 3) → 2¹⁰⁰ ≡ (-1)¹⁰⁰ = 1 (mod 3)
✅ Ответ: 1
8.
3x ≡ 1 (mod 7)
Перебираем x от 0 до 6:
x=0 → 0
x=1 → 3
x=2 → 6
x=3 → 9 ≡ 2
x=4 → 12 ≡ 5
x=5 → 15 ≡ 1 ← ✅ нашли!
Ответ: x = 5
(Это и есть «обратный элемент» к 3 по модулю 7)
9. Сумма цифр: 1+2+3+4+5+6+7+8+9 = 45
45 mod 3 = 0 → значит, число делится на 3. ✅
10.
n³ — n = n(n² — 1) = n(n-1)(n+1) — произведение трёх последовательных чисел.
Среди трёх последовательных:
- хотя бы одно чётное → делится на 2
- хотя бы одно делится на 3
Значит, произведение делится и на 2, и на 3 → делится на 6.
Можно и через модули:
Проверь все остатки n mod 2 и mod 3 — везде n³ — n ≡ 0.
✅ Доказано!
Типовые задачи
1. Найдите остаток от деления числа 2025 на 7.
Решение:
Делим 2025 на 7:
7 × 289 = 2023 → 2025 – 2023 = 2
✅ Ответ: 2
2. Сегодня среда. Какой день недели будет через 1000 дней?
Решение:
Дни недели повторяются каждые 7 дней → работаем по модулю 7.
1000 : 7 = 142 × 7 = 994 → остаток 6
Среда + 6 дней = вторник
(Четверг, пятница, суббота, воскресенье, понедельник, вторник)
✅ Ответ: вторник
3. Электронные часы показывают время от 00:00 до 23:59. Сейчас 18:00. Что покажут часы через 100 часов?
Решение:
Часы работают по модулю 24.
100 : 24 = 4×24 = 96 → остаток 4
18:00 + 4 часа = 22:00
✅ Ответ: 22:00
4. Число при делении на 8 даёт остаток 5. Какой остаток даст квадрат этого числа при делении на 8?
Решение:
Пусть число: a ≡ 5 (mod 8)
Тогда:
a² ≡ 5² = 25 (mod 8)
25 : 8 = 3×8 = 24 → остаток 1
✅ Ответ: 1
5. Известно, что a + b делится на 5, а a при делении на 5 даёт остаток 3. Какой остаток даёт b при делении на 5?
Решение:
a ≡ 3 (mod 5)
a + b ≡ 0 (mod 5) → значит, b ≡ -a ≡ -3 ≡ 2 (mod 5)
(потому что -3 + 5 = 2)
✅ Ответ: 2
6. Найдите остаток от деления числа 7¹⁰⁰ на 6.
Решение:
Заметим, что 7 ≡ 1 (mod 6) → тогда 7¹⁰⁰ ≡ 1¹⁰⁰ = 1 (mod 6)
✅ Ответ: 1
7. Найдите остаток от деления 3²⁰²⁴ на 8.
Решение:
Посмотрим на степени 3 по модулю 8:
- 3¹ = 3 → 3 mod 8 = 3
- 3² = 9 → 1
- 3³ = 27 → 3
- 3⁴ = 81 → 1
👉 Видим цикл длины 2: 3, 1, 3, 1…
Чётная степень → остаток 1
2024 — чётное → 3²⁰²⁴ ≡ 1 (mod 8)
✅ Ответ: 1
8. Найдите последнюю цифру числа 13²⁰²⁵.
Решение:
Последняя цифра = остаток от деления на 10 → mod 10
13 ≡ 3 (mod 10) → задача свелась к 3²⁰²⁵ mod 10
Цикл последних цифр у степеней 3:
- 3¹ = 3
- 3² = 9
- 3³ = 27 → 7
- 3⁴ = 81 → 1
- 3⁵ = 243 → 3 → цикл: 3, 9, 7, 1 — длина 4
2025 : 4 = 506×4 = 2024 → остаток 1 → первое число в цикле → 3
✅ Ответ: 3
9. Найдите наименьшее натуральное число, которое при делении на 3 даёт остаток 2, а при делении на 5 — остаток 3.
Решение:
Ищем x такое, что:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
Переберём числа, дающие остаток 3 при делении на 5:
3, 8, 13, 18, 23…
Проверим, какие из них ≡ 2 mod 3:
- 3 : 3 → остаток 0 → нет
- 8 : 3 → 2 → ✅ подходит!
✅ Ответ: 8
10. Найдите остаток от деления 2¹⁰⁰ на 100.
Решение:
Нужно 2¹⁰⁰ mod 100 — последние две цифры числа.
💡 Здесь поможет теорема Эйлера или цикличность по модулю 100.
Посчитаем последние две цифры степеней двойки:
- 2¹ = 02
- 2² = 04
- 2³ = 08
- 2⁴ = 16
- 2⁵ = 32
- 2⁶ = 64
- 2⁷ = 28
- 2⁸ = 56
- 2⁹ = 12
- 2¹⁰ = 24
- 2¹¹ = 48
- 2¹² = 96
- 2¹³ = 92
- 2¹⁴ = 84
- 2¹⁵ = 68
- 2¹⁶ = 36
- 2¹⁷ = 72
- 2¹⁸ = 44
- 2¹⁹ = 88
- 2²⁰ = 76
- 2²¹ = 52
- 2²² = 04 ← повтор! (совпало с 2²)
👉 Цикл длины 20, начиная с 2².
Значит, степени с 2², 2²², 2⁴², … — одинаковые последние 2 цифры.
100 – 2 = 98 → 98 : 20 = 4×20 = 80 → остаток 18 → значит, 2¹⁰⁰ соответствует 2²⁺¹⁸ = 2²⁰ → последние цифры 76
✅ Ответ: 76
Шпаргалка
| Модуль | Пример | |
|---|---|---|
| День недели | 7 | Через 100 дней: 100 mod 7 = 2 → +2 дня |
| Время на часах (сутки) | 24 | 18:00 + 100 ч → 100 mod 24 = 4 → 22:00 |
| Последняя цифра | 10 | 13²⁰²⁵ → 3²⁰²⁵ mod 10 → цикл 4 →3 |
| Последние 2 цифры | 100 | 2¹⁰⁰ mod 100 → цикл 20 →76 |
Примеры
- 7¹⁰⁰ mod 6 → 7 ≡ 1 → 1¹⁰⁰ = 1
- 3²⁰²⁴ mod 8 → 3² = 9 ≡ 1 → (3²)¹⁰¹² ≡ 1 → 1
- 13²⁰²⁵ mod 10 → 3 в степени → цикл 4 → 2025 mod 4 = 1 → 3
- 2¹⁰⁰ mod 100 → цикл 20 → 100 – 2 = 98 → 98 mod 20 = 18 → 2²⁰ → 76
Проверь себя
- Найдите остаток от деления 3000 на 13.
- Сегодня понедельник. Какой день будет через 365 дней?
- Найдите последнюю цифру числа 7⁷⁷.
- Найдите остаток от деления 5¹⁰⁰ на 4.
- Найдите наименьшее число, которое при делении на 4 даёт остаток 3, а на 6 — остаток 5.
Ответы :
- 3000 : 13 = 230×13 = 2990 → остаток 10
- 365 : 7 = 52×7 = 364 → остаток 1 → понедельник + 1 = вторник
- Цикл 7: 7, 9, 3, 1 → длина 4. 77 : 4 = остаток 1 → 7
- 5 ≡ 1 (mod 4) → 5¹⁰⁰ ≡ 1¹⁰⁰ = 1
- x ≡ 3 (mod 4), x ≡ 5 (mod 6). Перебор: 5, 11, 17… → 11: 11 mod 4 = 3 → ✅ 11