"Алгебра", Мерзляк А.Г., Поляков В.М. / Под ред. Подольского В.Е.
Деление с остатком позволяет представить число через делитель, неполное частное и остаток: a = bq + r. Остаток всегда неотрицателен и меньше делителя. Сравнение a ≡ b (mod m) означает, что числа дают одинаковый остаток при делении на m, или, что то же самое, их разность делится на m. Эти записи помогают проверять делимость и находить остатки больших выражений, например степеней.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Деление с остатком — представление числа a в виде a = bq + r, где b — делитель, q — неполное частное, а r — остаток. Например, в записи 157 = 12 · 13 + 1 число 13 — неполное частное, а 1 — остаток. Такая запись показывает, сколько раз делитель помещается в делимом и что остаётся после этого.
Остаток от деления — неотрицательное число r, меньшее делителя b. Это значит, что остаток может быть равен нулю, но не может «набрать» ещё одну полную группу величиной b. Условие 0 ≤ r < b помогает отличать правильное деление с остатком от записи, в которой частное ещё можно увеличить.
Сравнение по модулю — запись a ≡ b (mod m), означающая, что числа a и b имеют одинаковые остатки при делении на m. Например, 17 ≡ 5 (mod 12): оба числа дают остаток 5. Такая запись не утверждает, что сами числа равны, а сообщает об их общем остатке.
Модуль сравнения — натуральное число m, относительно которого устанавливается сравнение. В записи a ≡ b (mod m) именно m задаёт, на сколько делят числа или их разность. Если изменить модуль, сравнение может стать неверным, поэтому его всегда указывают.
При делении натурального числа a на положительное b можно отложить от a как можно больше полных групп по b. Число таких групп — неполное частное q, а то, что не вошло в группы, — остаток r, поэтому a = bq + r. Если остаток оказался не меньше b, в него помещается ещё одна группа: частное увеличивается, а остаток уменьшается на b. Так получают r < b; частное и остаток единственны, потому что два разных остатка меньше b не могут отличаться на целое число b.
Чтобы найти остаток по равенству a = bq + r, нужно выделить слагаемое, не содержащее множитель b: это и есть r. Например, 157 = 12 · 13 + 1, значит, остаток равен 1. Остаток не бывает равен делителю: тогда bq + b = b(q + 1), и частное можно увеличить на единицу. Отрицательный остаток также не подходит принятому условию деления натуральных чисел: остаток показывает количество, которое осталось, и должен быть неотрицательным.
Числа a и b имеют одинаковые остатки при делении на m тогда и только тогда, когда разность a − b делится на m. Если остатки равны, то при вычитании общая часть, кратная m, сокращается, и остаётся разность кратных m. И наоборот: если a − b делится на m, то числа отличаются на целое число полных групп по m, поэтому их остатки совпадают. Это даёт удобный способ переходить от сравнения остатков к проверке делимости.
Связь с разностью позволяет проверять сравнение, не выполняя два деления. Для проверки a ≡ b (mod m) достаточно вычислить a − b и убедиться, что разность делится на m. Например, если разность равна 3m, сравнение верно; если при делении разности на m остаётся ненулевой остаток, оно неверно. При необходимости можно проверить то же сравнение, найдя остатки обоих чисел и сравнив их.
Сравнения можно складывать, вычитать и перемножать, потому что разности сравнимых чисел кратны одному и тому же модулю, а после этих действий разность результатов также делится на модуль. Поэтому вместо больших чисел часто используют их более удобные сравнимые значения. Деление и сокращение требуют осторожности: например, из ac ≡ bc (mod m) сокращать c без дополнительных условий нельзя. Если c и m взаимно просты, сокращение допустимо; в иных случаях нужно проверить, какой вывод действительно следует из сравнения.
| Признак | Деление с остатком | Сравнение по модулю |
|---|---|---|
| Основная запись | a = bq + r | a ≡ b (mod m) |
| Условие на остаток | 0 ≤ r < b | Остатки чисел равны |
| Что показывает запись | Сколько полных групп b содержится в a и что осталось | Числа дают одинаковый остаток при делении на m |
| Связь с делимостью | a − r делится на b | a − b делится на m |
| Пример | 17 = 3 · 5 + 2 | 17 ≡ 2 (mod 5) |
| Допустимые действия | Проверить равенство и условие на остаток | Складывать, вычитать и перемножать сравнения |
Сначала определите, что именно требуется: представить число как сумму кратного и остатка или сравнить остатки двух чисел. Затем проверьте условие на остаток либо делимость разности на модуль. В последней строке таблицы перечислены действия, допустимые без дополнительных условий; при сокращении сравнения условия нужно проверять отдельно.
Задача 1. Разделить 157 на 12 с остатком и записать результат в виде равенства. Нужно найти наибольшее целое число раз, которое 12 помещается в 157, а затем проверить, что оставшаяся часть меньше 12. Если взять частное слишком маленьким, остаток можно будет уменьшить, увеличив частное.
Ответ: 157 = 12 · 13 + 1; неполное частное — 13, остаток — 1. Проверка показывает, что произведение с частным 14 уже превысило бы делимое. Поэтому найденное частное действительно наибольшее, а остаток допустим.
Задача 2. Проверить, верно ли сравнение 245 ≡ 101 (mod 12), двумя способами. При первом способе сравним остатки чисел, при втором проверим делимость их разности. Оба метода должны привести к одному выводу, поскольку равенство остатков равносильно делимости разности на модуль.
Ответ: сравнение 245 ≡ 101 (mod 12) верно. В первом способе совпали остатки, во втором обнаружилась разность, кратная 12. Если бы остатки различались или разность не делилась на модуль, сравнение было бы неверным.
Задача 3. Найти остаток от деления числа 7⁴ + 3 · 7² − 5 на 6, используя сравнения по модулю. Вычислять степени полностью необязательно: достаточно заменить 7 удобным числом, которое даёт такой же остаток при делении на 6. После этого применяем свойства сравнений к возведению в степень, умножению и вычитанию.
Ответ: остаток равен 5. Отрицательное число −1 здесь не является остатком: оно лишь представляет результат сравнения. Чтобы получить остаток, равный 0 или больше и меньше 6, прибавляем модуль 6.
Иногда записывают остаток, равный делителю или больший его. Это происходит, если после вычитания не проверяют условие 0 ≤ r < b. Для самопроверки разделите остаток на делитель: если в остатке помещается ещё одна полная группа, увеличьте частное и уменьшите остаток.
Другая ошибка — путать неполное частное и остаток, например считать остатком последнее число, полученное при делении. Это случается, когда не проверяют роли слагаемых в равенстве a = bq + r. Подставьте числа обратно: частное умножается на делитель, а остаток прибавляется; затем проверьте, что он меньше делителя.
Числа могут быть близки или иметь одинаковую последнюю цифру, но это само по себе не доказывает сравнимость по модулю. Для конкретного модуля важна делимость разности, а не расстояние между числами и не вид их записи. Вычислите разность и разделите её на модуль: только нулевой остаток подтверждает сравнение.
Нельзя без проверки сокращать общий множитель в сравнении по модулю: сокращение может быть недопустимым, если множитель и модуль имеют общий делитель. Ошибка возникает из-за привычки переносить правило сокращения из обычных равенств на сравнения. Перед сокращением проверьте, взаимно просты ли множитель и модуль; если нет, не делайте такой вывод без отдельного обоснования.
Для этой темы нужны понятия делителя и кратного, признаки делимости, письменное деление и свойства равенств. Деление с остатком связывает число с кратным делителя и оставшейся частью. Сравнения по модулю пригодятся при изучении свойств натуральных и целых чисел, а также при доказательстве делимости выражений. С их помощью удобно искать последние цифры и остатки степеней; те же идеи используют в задачах теории чисел.
Может ли остаток быть отрицательным или равным делителю?
Нет: при делении с остатком выполняется 0 ≤ r < b. Если остаток равен делителю или больше него, можно выделить ещё одно целое неполное частное; отрицательный остаток не соответствует принятому правилу деления натуральных чисел.
Чем сравнение по модулю отличается от обычного равенства?
Равенство означает, что числа совпадают. Сравнение по модулю m означает, что разность чисел делится на m, поэтому сами числа могут быть разными, но иметь одинаковый остаток при делении на m.
Как быстро проверить, сравнимы ли два числа по заданному модулю?
Вычти одно число из другого и проверь, делится ли разность на модуль без остатка. Можно также разделить оба числа на этот модуль и сравнить остатки.
Можно ли делить или сокращать обе части сравнения?
Не всегда. Если обе части имеют общий множитель c, сокращать его по модулю m можно, когда c и m взаимно просты; иначе сокращение может изменить модуль или привести к неверному выводу.
Как с помощью сравнений находить остаток от деления большой степени?
Заменяют основание степени числом, сравнимым с ним по нужному модулю, а затем возводят в степень и выполняют действия с остатками. Например, если 7 ≡ 1 (mod 6), то и любая положительная степень 7 сравнима с 1 по модулю 6.
§ 27. Деление с остатком. Сравнения по модулю и их свойства
