"Алгебра (в 3 частях)", Петерсон Л.Г., Абраров Д.Л., Чуткова Е.В.
Сравнение по модулю помогает понять, одинаковые ли остатки дают два числа при делении на одно и то же число. Запись a ≡ b (mod m) равносильна тому, что разность a − b делится на m. Благодаря этому большие числа можно заменять меньшими, сравнимыми с ними по заданному модулю, а затем складывать, вычитать, умножать и возводить в степени. Так проще находить остатки и доказывать некоторые свойства целых чисел.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сравнением по модулю называют запись a ≡ b (mod m), которая означает, что числа a и b дают одинаковые остатки при делении на m. Например, 17 и 5 при делении на 6 дают остаток 5, поэтому 17 ≡ 5 (mod 6). Такая запись позволяет объединять числа, которые отличаются на целое число модулей.
Модуль сравнения — натуральное число m, относительно которого сравнивают числа. Он указывается в скобках после знака сравнения: без модуля запись неполна, потому что остатки зависят от делителя. Один и тот же набор чисел может быть сравнимым по одному модулю, но не по другому.
Знак сравнения — символ ≡; он отличается от знака равенства =. Равенство утверждает, что числа одинаковы, а сравнение — что их разность делится на указанный модуль. Знак ≡ помогает сразу увидеть, что речь идёт об остатках и делимости, а не о совпадении самих чисел.
Для сравнения есть два равносильных условия: числа имеют одинаковые остатки при делении на m и m делит разность a − b. Равносильность означает, что можно пользоваться любым из этих способов проверки. Условие с разностью часто удобнее, когда делимость заметна сразу.
Пусть при делении a и b на m получается один и тот же остаток r. Тогда числа можно представить как a = mq + r и b = mp + r, где q и p — целые частные. При вычитании остатки r уничтожаются, и получается a − b = m(q − p), то есть разность кратна модулю. Обратно, если a − b делится на m, то числа отличаются на целое число полных групп по m и потому имеют одинаковый остаток.
Деление с остатком раскладывает число на полные группы по m и оставшуюся часть. Если у двух чисел оставшаяся часть одинакова, то их остатки совпадают; поэтому проверять сравнение можно либо по остаткам, либо по разности. Например, чтобы проверить сравнение по модулю 7, достаточно найти остатки чисел при делении на 7. Удобнее выбрать тот способ, где вычисления короче.
При сложении сравнимых чисел разность новых сумм равна сумме исходных разностей: (a + c) − (b + d) = (a − b) + (c − d). Если каждая из разностей делится на m, их сумма тоже делится на m; при вычитании работает такое же рассуждение. Поэтому сравнения с одинаковым модулем можно складывать и вычитать почленно. Модуль при этом сохраняется.
При умножении разность произведений можно представить так: ac − bd = a(c − d) + d(a − b). Если a ≡ b и c ≡ d (mod m), обе разности в скобках делятся на m, значит, делится и вся сумма. Так получается ac ≡ bd (mod m), а многократное применение умножения даёт aⁿ ≡ bⁿ (mod m) для натурального n. Значение многочлена с целыми коэффициентами тоже сохраняет сравнение: его составляют сложением, умножением и умножением на целые числа.
Деление устроено иначе: из делимости разности на m не следует, что после деления она останется кратной m. Например, 6 ≡ 0 (mod 6), но после деления обеих частей на 2 получаем 3 и 0, которые не сравнимы по модулю 6. Сокращение обычно можно обосновать, если сокращаемый множитель взаимно прост с модулем, то есть не имеет с ним общих делителей, кроме 1. Поэтому прежде чем делить, нужно проверить условия.
В таблице собраны свойства, которые помогают преобразовывать сравнения, не меняя модуль.
| Свойство | Запись | Условия применения | Практический смысл |
|---|---|---|---|
| Рефлексивность | a ≡ a (mod m) | Всегда | Число сравнимо само с собой |
| Симметричность | Если a ≡ b (mod m), то b ≡ a (mod m) | Всегда | Можно менять местами числа |
| Транзитивность | Если a ≡ b и b ≡ c (mod m), то a ≡ c (mod m) | Один и тот же модуль | Сравнения можно объединять |
| Сложение и вычитание | Если a ≡ b и c ≡ d (mod m), то a ± c ≡ b ± d (mod m) | Одинаковый модуль | Сравнения складываются и вычитаются почленно |
| Умножение | Если a ≡ b и c ≡ d (mod m), то ac ≡ bd (mod m) | Одинаковый модуль | Можно перемножать сравнимые числа |
| Возведение в натуральную степень | Если a ≡ b (mod m), то aⁿ ≡ bⁿ (mod m) | n — натуральное число | Можно заменять число в степенном выражении его сравнением |
При преобразованиях сначала проверь, что модуль во всех сравнениях один и тот же. Затем выбери свойство, соответствующее действию в выражении. Для деления подходящего свойства в таблице нет: его нужно обосновывать отдельно.
Проверим разность: по определению сравнения она должна делиться на указанный модуль. Это избавляет от необходимости выписывать частные и остатки обоих чисел. Выполним проверку по шагам.
Ответ: 47 ≡ 5 (mod 7) — верно.
Для вычисления остатка заменим основания квадратов их остатками при делении на 5. Такая замена сохраняет сравнение, а возведение в степень и сложение разрешены для сравнений с одинаковым модулем. Сначала найдём небольшие остатки.
Ответ: остаток равен 3.
Большие степени считать напрямую неудобно. По модулю 4 число 7 даёт остаток 3, а 3 можно заменить числом −1, поскольку их разность 4 делится на 4. После замены степени становятся простыми.
Ответ: остаток равен 2.
Не путай знак сравнения ≡ со знаком равенства =. Например, 47 ≡ 5 (mod 7), хотя 47 и 5 не равны: сравнение говорит лишь об одинаковых остатках. Ошибка возникает из-за похожего смысла знаков в записи. Проверь себя, подставив числа: если они различны, это не равенство, но сравнение всё ещё может быть верным.
При проверке по разности важно вычесть числа в одном порядке и проверить делимость именно на указанный модуль. Если поменять порядок, разность изменит знак, но её делимость не изменится; опасно скорее забыть модуль или проверить делимость на другое число. Например, для сравнения по модулю 7 нужно проверить делимость на 7. Пересчитай разность и сверь делитель со скобками.
Складывать или умножать сравнения с разными модулями напрямую нельзя: свойства требуют одного общего модуля. Ошибка возникает, когда замечают нужное действие, но не проверяют условие применения. Перед преобразованием просмотри все модули; если они различаются, сначала обоснуй переход к подходящему общему модулю.
Нельзя автоматически делить или сокращать обе части сравнения на общий множитель. После деления разность может перестать делиться на прежний модуль, поэтому сравнение нарушится. Это действие часто кажется естественным по аналогии с обычными равенствами, но условия здесь другие. Проверь делимость на конкретном примере и выясни, взаимно ли прост множитель с модулем, прежде чем сокращать.
Для работы со сравнениями нужны делимость, понятия делителя и кратного, а также деление с остатком. Помогают и свойства равенств и степеней, хотя деление в сравнении требует отдельной осторожности. Сравнение обобщает знакомую идею одинаковых остатков: числа с одним остатком образуют группу по выбранному модулю.
Позже сравнения пригодятся для нахождения остатков больших степеней, доказательства признаков делимости и решения задач на целые числа. Вместо громоздкого вычисления можно работать с небольшими числами, сохраняя нужный остаток. Это превращает вычисления в короткую цепочку проверяемых преобразований.
Чем сравнение отличается от обычного равенства?
Равенство означает, что числа одинаковы. Сравнение по модулю означает, что они дают одинаковые остатки при делении на указанный модуль, поэтому сами числа могут быть разными: 47 ≡ 5 (mod 7).
Как быстро проверить, сравнимы ли два числа по заданному модулю?
Можно разделить оба числа на модуль и сравнить остатки. Или вычесть одно число из другого и проверить, делится ли разность на модуль.
Можно ли складывать и умножать сравнения?
Да, если у сравнений один и тот же модуль. Сравнения можно складывать, вычитать и перемножать почленно; также из сравнения можно получить сравнение натуральных степеней.
Почему в сравнении нельзя просто разделить обе части на общий множитель?
Деление может изменить делимость разности на модуль, поэтому после него сравнение не всегда сохранится. Сокращать множитель допустимо лишь при дополнительных условиях, например если этот множитель не имеет общих делителей с модулем, кроме 1.
Как сравнения помогают находить остаток большой степени?
Основание степени заменяют меньшим числом с тем же остатком по нужному модулю. Затем используют свойства сравнений и вычисляют остаток от более простого выражения.
2.2.3. Сравнения и их свойства
