Кольцо вычетов по модулю: операции и примеры

Кольцо вычетов по модулю - это система из классов целых чисел, в которой два числа считаются представителями одного класса, если их разность делится на . Классы складывают и умножают, а результат снова записывают как остаток от до . Например, по модулю 6 числа , и принадлежат одному классу.
Операции напоминают привычную арифметику, но деление работает иначе: ненулевой класс может не иметь обратного, а произведение двух ненулевых классов может оказаться нулём. В интерактиве выберите модуль и множитель, чтобы увидеть, когда умножение переставляет все остатки, а когда результаты повторяются.
От целых чисел к классам
Пусть . Запись означает, что делит . Это сравнение по модулю, а не равенство самих целых чисел. Например, , поскольку ; в то же время как целые числа.
Класс состоит из всех чисел вида , где - целое. Для модуля 6 класс содержит . Все целые разбиваются на шесть непересекающихся классов . Это частный случай разбиения на классы эквивалентности: внутри класса представители равносильны для вычислений по выбранному модулю.
Обозначение кольца - , иногда . Короткую запись вместо используют, когда модуль понятен из контекста. Однако один и тот же символ может обозначать разные классы при разных модулях: модуль всегда нужно указывать.
Представитель не обязан быть наименьшим неотрицательным числом. В вычислении можно выбрать тот, с которым легче работать: по модулю 6 класс удобно заменить на . Например, квадрат последнего сразу равен . Для итогового ответа обычно возвращаются к стандартным представителям, чтобы разные записи одного результата было проще сравнивать.
Сложение и умножение
Правила определяются через представителей:
По модулю 6 получаем и . При сложении можно представить шесть классов как позиции на круге: от 4 три шага вперёд ведут через 5 и 0 к 1. Ролик возвращает маркер назад, чтобы тот же переход можно было рассмотреть снова.
Результат не зависит от выбора представителей. Если заменить на , а на , сумма изменится на кратное . Для произведения разность равна , тоже кратному . Поэтому, например, и дают один класс .
Эта независимость и делает операции над классами корректными. Они наследуют от целых чисел ассоциативность, коммутативность и распределительный закон. Класс - ноль, - единица, а противоположный к элемент есть . Таким образом, получается коммутативное кольцо с единицей.
Полезная практическая проверка - сократить промежуточные числа сразу после каждого действия. Если нужно найти остаток большого произведения, сначала замените каждый множитель его остатком, перемножьте полученные значения и снова возьмите остаток. Такой приём сохраняет математический результат и упрощает ручной счёт. Порядок действий при этом остаётся обычным: сначала умножение, затем сложение, если скобки не задают иного.
Обратимые элементы и деление
Класс обратим, если существует с . Тогда обозначают . Точный критерий: обратимый элемент существует тогда и только тогда, когда . Например, по модулю 6 обратимы и ; причём , поскольку .
Почему важен наибольший общий делитель? Если , тождество Безу даёт целые такие, что . Значит, , и класс обратен к . Обратно, из следует, что общий делитель и делит 1. Расширенный алгоритм Евклида находит подходящий коэффициент даже для больших чисел.
Деление на определено как умножение на только при обратимости. Например, даёт . Проверка: . Нельзя автоматически делить на произвольный ненулевой класс, как в поле действительных чисел.
Делители нуля и таблица произведений
Делитель нуля - ненулевой элемент, который при умножении на некоторый другой ненулевой элемент даёт ноль. В кольце по модулю 6 это видно на примере : произведение 6 кратно модулю, хотя ни один множитель не принадлежит нулевому классу. В таблице строка - первый множитель, столбец - второй, а выделенная ячейка показывает результат.

В строке стоят : разные входы дают одинаковый результат. Поэтому из нельзя заключить, что : достаточно взять и . Сокращение допустимо, если множитель обратим; тогда обе части можно умножить на его обратный класс.
Для ненулевого класса по составному модулю критерий прост: он является делителем нуля тогда и только тогда, когда его представитель не взаимно прост с модулем. В примере делители нуля - , и . Сам нулевой класс по этому определению в их число не включают.
Это свойство видно и в калькуляторе: поставьте модуль 6 и множитель 2. Для входов 0 и 3 столбцы имеют нулевую высоту, а другие высоты повторяются. Теперь выберите множитель 5: результаты станут перестановкой всех классов. Обратимость и отсутствие повторов связаны: умножение на обратный элемент позволяет восстановить единственный исходный класс по результату.
Когда кольцо становится полем
Если модуль прост, каждый ненулевой представитель от 1 до взаимно прост с . Значит, каждый ненулевой класс обратим, и - поле. Для интерактив показывает, что умножение на 2 даёт все семь остатков по одному разу: .
Если составное, его можно представить как , где . Тогда и ненулевые, но . Следовательно, поле получается ровно при простом модуле. Например, число классов 6 само по себе не мешает сложению или умножению, но мешает делению на каждый ненулевой класс. Связь полей с более общей конструкцией обсуждается в статье о максимальных идеалах.
Как решить линейное сравнение
Для положим . Решения существуют тогда и только тогда, когда делит ; если существуют, различных классов решений по модулю ровно . Этот критерий и вывод через тождество Безу приведены в учебном разборе линейных сравнений.
Решим . Здесь делит правую часть. Делим числа , и модуль 6 на 2: получаем , откуда . Среди классов по исходному модулю это два ответа: и . Оба проходят проверку. Если бы справа стояла 3, решений не было бы, так как 2 не делит 3.
Уменьшенный модуль описывает тот же набор целых решений более короткой записью, но вопрос о количестве классов относится к исходному модулю. Поэтому после решения по модулю 3 нужно перечислить остатки от 0 до 5, которые дают остаток 2 при делении на 3. Это и есть 2 и 5. Подстановка каждого ответа в исходное сравнение помогает не потерять решение и не принять лишнее.
Где это встречается в программировании
Остаток помогает переводить неограниченный счётчик в ограниченный набор индексов. Например, в кольцевом буфере переход к следующей позиции часто записывают как . Это действие использует сложение классов; само по себе оно не означает, что в программе обязательно реализованы все операции кольца.
В криптографии модульная арифметика применяется и к произведениям и степеням; пример - обмен ключами Диффи - Хеллмана. Однако безопасность алгоритма не следует из одного наличия операции остатка: важны выбор группы, параметров и корректная реализация.
В коде отдельно проверьте соглашение языка об остатке отрицательного числа. Если оператор возвращает отрицательное значение, выражение при положительном приводит остаток к диапазону от 0 до . Также учитывайте переполнение при умножении до взятия остатка: математический класс не ограничен машинным типом.
Например, при длине буфера 6 позиция 5 после одного шага становится позицией 0. Если требуется шаг назад, математически ответ для позиции 0 - класс 5, однако конкретное выражение на языке программы следует проверить на отрицательном промежуточном значении. В тестах полезно охватить обе границы диапазона, нулевой сдвиг и сдвиг больше длины буфера.
Частые ошибки
- Путать сравнение с равенством целых чисел: , но .
- Считать всякий ненулевой класс обратимым. По модулю 6 у класса обратного нет.
- Сокращать на необратимый множитель без изменения модуля и проверки решений.
- Записывать только один ответ после деления сравнения и терять остальные классы по исходному модулю.
- Предполагать, что отрицательный операнд всегда даёт неотрицательный остаток в языке программирования.
FAQ
Сколько элементов в кольце по модулю ?
Ровно : каждый целый представитель попадает в один из классов . Каждый класс при этом содержит бесконечно много целых чисел.
Всегда ли ?
Да. Противоположный по сложению элемент существует для каждого класса. Его не следует путать с обратным по умножению, который есть не всегда.
Можно ли делить обе части сравнения на общий делитель?
Если он делит оба коэффициента и модуль, можно разделить все три числа и получить сравнение с меньшим модулем. Затем нужно вернуть все соответствующие классы решений по исходному модулю.
Коротко
Кольцо объединяет целые числа с одинаковым остатком и сохраняет корректные операции сложения и умножения. Обратимость класса определяется взаимной простотой с модулем; при составном модуле возможны делители нуля. Для решения сравнений сначала проверяют НОД, затем находят и проверяют все классы ответов.
Читайте также

Шифр Хилла: матричное шифрование по mod 26
Шифр Хилла простыми словами: ключевая матрица, умножение вектора открытого текста по mod 26, обратимость матрицы, шаги шифрования и дешифрования с примерами задач.

Абсолютно неупругий удар: сохранение импульса
Как найти скорость тел после абсолютно неупругого удара, применить закон сохранения импульса и вычислить потерю кинетической энергии на понятных примерах с формулами.

Абсолютное и избыточное давление: формулы и вакуум
Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

АЦП последовательного приближения: схема и принцип работы
Разберите схему АЦП последовательного приближения: как компаратор, ЦАП и регистр определяют код по битам, как вычислить шаг квантования и оценить погрешность.

Аддитивная и мультипликативная погрешность
Аддитивная и мультипликативная погрешность прибора: формулы сдвига нуля и ошибки масштаба, пример расчёта показания и поправки, калибровка прибора и пределы линейной модели.

Адиабатический процесс: уравнение Пуассона и расчёт
Уравнение Пуассона для адиабатического процесса: вывод через первое начало термодинамики, связь давления, объёма и температуры, пример и границы применения.