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

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Из 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 не является достаточным условием: простая двойка не обратима по чётному модулю.
Модуль в этой статье положителен, а сравнения относятся к целым числам. Деление на дробь как в действительной арифметике не заменяет понятия обратимости. Полезная проверка после каждого сокращения — выписать, на какой именно модуль теперь должна делиться разность. Она удерживает логический смысл преобразования и помогает отличить потерю решений от правильного изменения записи.
От чтения к действию
А теперь — вы
Частые вопросы
Если множитель простой, его всегда можно сократить?
Нет. Важно, взаимно прост ли он с модулем. Например, двойка простая, но имеет общий делитель с модулем шесть.
Изменение модуля делает решение менее точным?
Нет. При корректном сокращении получается равносильное условие для целых чисел. Ошибка возникает при сохранении слишком большого модуля без основания.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Обратный элемент по модулю: условие существования и проверка
Находим обратный множитель по модулю, проверяем условие взаимной простоты и отличаем обратный остаток от обычной дроби.
Открыть темуКак НОД определяет число решений линейного сравнения
Проверяем существование целых решений линейного сравнения через НОД, считаем классы по исходному модулю и восстанавливаем их после сокращения.
Открыть тему