Математика · объяснение и практика

Когда в сравнении по модулю можно сократить множитель

Сокращаем множитель в сравнении по модулю с проверкой НОД и понимаем, почему обычное деление обеих сторон может потерять классы решений.

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

Главная мысль

Из ca ≡ cb по модулю m следует a ≡ b по модулю m/НОД(c,m). Сохранить прежний модуль при сокращении можно, если c взаимно просто с m. Без этого условия сравнение слабее обычного равенства и деление требует изменения модуля.

Почему одинаковый остаток не равен одинаковому числу

Запись a ≡ b по модулю m означает, что разность a−b делится на m. Числа могут различаться на много полных модулей. Поэтому операция, привычная для равенств, должна проверяться через эту делимость. Например, 2·1 и 2·4 имеют одинаковые остатки по модулю шесть, но сами числа один и четыре не сравнимы по модулю шесть.

В этом примере сокращение двойки сохраняет сравнение только по модулю три: разность четырёх и одного делится на три. Полученное условие не хуже и не приблизительнее исходного — оно ему равносильно. Потеря возникает, если после деления неправомерно оставить шесть и тем самым требовать более сильного совпадения, чем было задано.

Как НОД определяет новый модуль

Пусть g = НОД(c,m). Из m, делящего c(a−b), после деления общей части получаем m/g, делящее (c/g)(a−b). Числа c/g и m/g взаимно просты, поэтому оставшийся множитель можно сократить по лемме о делителе произведения. Получается делимость a−b на m/g. Именно здесь видно, почему общий множитель влияет на модуль.

Например, 4x ≡ 8 по модулю двенадцать равносильно x ≡ 2 по модулю три. В пределах одного исходного модуля подходят x = 2, 5, 8 и 11. Если записать только x ≡ 2 по модулю двенадцать, останется лишь одна из четырёх допустимых серий. Проверка этих небольших значений делает цену неверного сокращения наглядной.

Пример

Корректно разделите 6x ≡ 12 по модулю пятнадцать на общий множитель три.

Делим обе части и модуль: получаем 2x ≡ 4 по модулю пять. Сокращать тройку, сохраняя модуль пятнадцать, нельзя. Далее двойка обратима по модулю пять, и можно получить x ≡ 2 по модулю пять.

Когда исходный модуль действительно сохраняется

Если НОД(c,m) = 1, новый модуль равен старому. Тогда у c существует обратный элемент, и умножение на него даёт обычное сокращение в системе остатков. Например, семёрку можно сократить по модулю десять, поскольку общих делителей больше единицы нет. Простота самого c не является достаточным условием: простая двойка не обратима по чётному модулю.

Модуль в этой статье положителен, а сравнения относятся к целым числам. Деление на дробь как в действительной арифметике не заменяет понятия обратимости. Полезная проверка после каждого сокращения — выписать, на какой именно модуль теперь должна делиться разность. Она удерживает логический смысл преобразования и помогает отличить потерю решений от правильного изменения записи.

От чтения к действию

А теперь — вы

На какой модуль нужно перейти при делении 9x ≡ 18 по модулю двенадцать на общий множитель три?

Частые вопросы

Если множитель простой, его всегда можно сократить?

Нет. Важно, взаимно прост ли он с модулем. Например, двойка простая, но имеет общий делитель с модулем шесть.

Изменение модуля делает решение менее точным?

Нет. При корректном сокращении получается равносильное условие для целых чисел. Ошибка возникает при сохранении слишком большого модуля без основания.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться