EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#кольцо вычетов#модульная арифметика#классы вычетов#делители нуля#обратный элемент
Кольцо вычетов по модулю: операции и примеры

Кольцо вычетов по модулю nn - это система из nn классов целых чисел, в которой два числа считаются представителями одного класса, если их разность делится на nn. Классы складывают и умножают, а результат снова записывают как остаток от 00 до n−1n-1. Например, по модулю 6 числа −1-1, 55 и 1111 принадлежат одному классу.

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

От целых чисел к классам

Пусть n≥2n \geq 2. Запись a≡b(modn)a\equiv b\pmod n означает, что nn делит a−ba-b. Это сравнение по модулю, а не равенство самих целых чисел. Например, 11≡5(mod6)11\equiv 5\pmod 6, поскольку 11−5=611-5=6; в то же время 11≠511\ne5 как целые числа.

Класс [a][a] состоит из всех чисел вида a+kna+kn, где kk - целое. Для модуля 6 класс [5][5] содержит …,−7,−1,5,11,17,…\ldots,-7,-1,5,11,17,\ldots. Все целые разбиваются на шесть непересекающихся классов [0],…,[5][0],\ldots,[5]. Это частный случай разбиения на классы эквивалентности: внутри класса представители равносильны для вычислений по выбранному модулю.

Обозначение кольца - Z/nZ\mathbb Z/n\mathbb Z, иногда Zn\mathbb Z_n. Короткую запись 55 вместо [5][5] используют, когда модуль понятен из контекста. Однако один и тот же символ может обозначать разные классы при разных модулях: модуль всегда нужно указывать.

Представитель не обязан быть наименьшим неотрицательным числом. В вычислении можно выбрать тот, с которым легче работать: по модулю 6 класс [5][5] удобно заменить на [−1][-1]. Например, квадрат последнего сразу равен [1][1]. Для итогового ответа обычно возвращаются к стандартным представителям, чтобы разные записи одного результата было проще сравнивать.

Сложение и умножение

Правила определяются через представителей:

[a]+[b]=[a+b],[a][b]=[ab].[a]+[b]=[a+b],\qquad [a][b]=[ab].

По модулю 6 получаем [4]+[3]=[7]=[1][4]+[3]=[7]=[1] и [4][5]=[20]=[2][4][5]=[20]=[2]. При сложении можно представить шесть классов как позиции на круге: от 4 три шага вперёд ведут через 5 и 0 к 1. Ролик возвращает маркер назад, чтобы тот же переход можно было рассмотреть снова.

Маркер проходит от класса 4 три шага по кругу модуля 6 и достигает класса 1, затем возвращается к исходной позиции.

Результат не зависит от выбора представителей. Если заменить aa на a+kna+kn, а bb на b+lnb+ln, сумма изменится на кратное nn. Для произведения разность равна n(al+bk+kln)n(al+bk+kln), тоже кратному nn. Поэтому, например, [5]+[3][5]+[3] и [−1]+[3][-1]+[3] дают один класс [2][2].

Эта независимость и делает операции над классами корректными. Они наследуют от целых чисел ассоциативность, коммутативность и распределительный закон. Класс [0][0] - ноль, [1][1] - единица, а противоположный к [a][a] элемент есть [−a][-a]. Таким образом, получается коммутативное кольцо с единицей.

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

Обратимые элементы и деление

Класс [a][a] обратим, если существует [b][b] с [a][b]=[1][a][b]=[1]. Тогда [b][b] обозначают [a]−1[a]^{-1}. Точный критерий: обратимый элемент существует тогда и только тогда, когда gcd⁡(a,n)=1\gcd(a,n)=1. Например, по модулю 6 обратимы [1][1] и [5][5]; причём [5]−1=[5][5]^{-1}=[5], поскольку 25≡1(mod6)25\equiv1\pmod 6.

Почему важен наибольший общий делитель? Если gcd⁡(a,n)=1\gcd(a,n)=1, тождество Безу даёт целые u,vu,v такие, что au+nv=1au+nv=1. Значит, au≡1(modn)au\equiv1\pmod n, и класс [u][u] обратен к [a][a]. Обратно, из ab−1=knab-1=kn следует, что общий делитель aa и nn делит 1. Расширенный алгоритм Евклида находит подходящий коэффициент uu даже для больших чисел.

Деление на [a][a] определено как умножение на [a]−1[a]^{-1} только при обратимости. Например, 5x≡2(mod6)5x\equiv2\pmod 6 даёт x≡5⋅2≡4(mod6)x\equiv5\cdot2\equiv4\pmod 6. Проверка: 5⋅4=20≡25\cdot4=20\equiv2. Нельзя автоматически делить на произвольный ненулевой класс, как в поле действительных чисел.

Делители нуля и таблица произведений

Делитель нуля - ненулевой элемент, который при умножении на некоторый другой ненулевой элемент даёт ноль. В кольце по модулю 6 это видно на примере [2][3]=[0][2][3]=[0]: произведение 6 кратно модулю, хотя ни один множитель не принадлежит нулевому классу. В таблице строка - первый множитель, столбец - второй, а выделенная ячейка показывает результат.

Таблица умножения по модулю 6: пересечение строки 2 и столбца 3 равно нулю
Таблица умножения по модулю 6: пересечение строки 2 и столбца 3 равно нулю

В строке [2][2] стоят 0,2,4,0,2,40,2,4,0,2,4: разные входы дают одинаковый результат. Поэтому из 2x≡2y(mod6)2x\equiv2y\pmod 6 нельзя заключить, что x≡y(mod6)x\equiv y\pmod 6: достаточно взять x=1x=1 и y=4y=4. Сокращение допустимо, если множитель обратим; тогда обе части можно умножить на его обратный класс.

Для ненулевого класса по составному модулю критерий прост: он является делителем нуля тогда и только тогда, когда его представитель не взаимно прост с модулем. В примере делители нуля - [2][2], [3][3] и [4][4]. Сам нулевой класс по этому определению в их число не включают.

Это свойство видно и в калькуляторе: поставьте модуль 6 и множитель 2. Для входов 0 и 3 столбцы имеют нулевую высоту, а другие высоты повторяются. Теперь выберите множитель 5: результаты станут перестановкой всех классов. Обратимость и отсутствие повторов связаны: умножение на обратный элемент позволяет восстановить единственный исходный класс по результату.

Когда кольцо становится полем

Если модуль pp прост, каждый ненулевой представитель от 1 до p−1p-1 взаимно прост с pp. Значит, каждый ненулевой класс обратим, и Z/pZ\mathbb Z/p\mathbb Z - поле. Для p=7p=7 интерактив показывает, что умножение на 2 даёт все семь остатков по одному разу: 0,2,4,6,1,3,50,2,4,6,1,3,5.

Если nn составное, его можно представить как n=rsn=rs, где 1<r,s<n1<r,s<n. Тогда [r][r] и [s][s] ненулевые, но [r][s]=[0][r][s]=[0]. Следовательно, поле получается ровно при простом модуле. Например, число классов 6 само по себе не мешает сложению или умножению, но мешает делению на каждый ненулевой класс. Связь полей с более общей конструкцией обсуждается в статье о максимальных идеалах.

Как решить линейное сравнение

Для ax≡b(modn)ax\equiv b\pmod n положим d=gcd⁡(a,n)d=\gcd(a,n). Решения существуют тогда и только тогда, когда dd делит bb; если существуют, различных классов решений по модулю nn ровно dd. Этот критерий и вывод через тождество Безу приведены в учебном разборе линейных сравнений.

Решим 4x≡2(mod6)4x\equiv2\pmod 6. Здесь d=2d=2 делит правую часть. Делим числа 44, 22 и модуль 6 на 2: получаем 2x≡1(mod3)2x\equiv1\pmod 3, откуда x≡2(mod3)x\equiv2\pmod 3. Среди классов по исходному модулю это два ответа: x≡2x\equiv2 и x≡5(mod6)x\equiv5\pmod 6. Оба проходят проверку. Если бы справа стояла 3, решений не было бы, так как 2 не делит 3.

Уменьшенный модуль описывает тот же набор целых решений более короткой записью, но вопрос о количестве классов относится к исходному модулю. Поэтому после решения по модулю 3 нужно перечислить остатки от 0 до 5, которые дают остаток 2 при делении на 3. Это и есть 2 и 5. Подстановка каждого ответа в исходное сравнение помогает не потерять решение и не принять лишнее.

Где это встречается в программировании

Остаток помогает переводить неограниченный счётчик в ограниченный набор индексов. Например, в кольцевом буфере переход к следующей позиции часто записывают как (i+1) mod n(i+1)\bmod n. Это действие использует сложение классов; само по себе оно не означает, что в программе обязательно реализованы все операции кольца.

В криптографии модульная арифметика применяется и к произведениям и степеням; пример - обмен ключами Диффи - Хеллмана. Однако безопасность алгоритма не следует из одного наличия операции остатка: важны выбор группы, параметров и корректная реализация.

В коде отдельно проверьте соглашение языка об остатке отрицательного числа. Если оператор возвращает отрицательное значение, выражение ((a%n)+n)%n((a\%n)+n)\%n при положительном nn приводит остаток к диапазону от 0 до n−1n-1. Также учитывайте переполнение при умножении до взятия остатка: математический класс не ограничен машинным типом.

Например, при длине буфера 6 позиция 5 после одного шага становится позицией 0. Если требуется шаг назад, математически ответ для позиции 0 - класс 5, однако конкретное выражение на языке программы следует проверить на отрицательном промежуточном значении. В тестах полезно охватить обе границы диапазона, нулевой сдвиг и сдвиг больше длины буфера.

Частые ошибки

  • Путать сравнение с равенством целых чисел: 11≡5(mod6)11\equiv5\pmod 6, но 11≠511\ne5.
  • Считать всякий ненулевой класс обратимым. По модулю 6 у класса [2][2] обратного нет.
  • Сокращать на необратимый множитель без изменения модуля и проверки решений.
  • Записывать только один ответ после деления сравнения и терять остальные классы по исходному модулю.
  • Предполагать, что отрицательный операнд всегда даёт неотрицательный остаток в языке программирования.

FAQ

Сколько элементов в кольце по модулю nn?

Ровно nn: каждый целый представитель попадает в один из классов [0],…,[n−1][0],\ldots,[n-1]. Каждый класс при этом содержит бесконечно много целых чисел.

Всегда ли [a]+[−a]=[0][a]+[-a]=[0]?

Да. Противоположный по сложению элемент существует для каждого класса. Его не следует путать с обратным по умножению, который есть не всегда.

Можно ли делить обе части сравнения на общий делитель?

Если он делит оба коэффициента и модуль, можно разделить все три числа и получить сравнение с меньшим модулем. Затем нужно вернуть все соответствующие классы решений по исходному модулю.

Коротко

Кольцо Z/nZ\mathbb Z/n\mathbb Z объединяет целые числа с одинаковым остатком и сохраняет корректные операции сложения и умножения. Обратимость класса определяется взаимной простотой с модулем; при составном модуле возможны делители нуля. Для решения сравнений сначала проверяют НОД, затем находят и проверяют все классы ответов.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Шифр Хилла: матричное шифрование по mod 26

Шифр Хилла: матричное шифрование по mod 26

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

11 июня 20268 минут
Абсолютно неупругий удар: сохранение импульса

Абсолютно неупругий удар: сохранение импульса

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

8 ноября 20268 минут
Абсолютное и избыточное давление: формулы и вакуум

Абсолютное и избыточное давление: формулы и вакуум

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

8 ноября 20268 минут
АЦП последовательного приближения: схема и принцип работы

АЦП последовательного приближения: схема и принцип работы

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

8 ноября 20268 минут
Аддитивная и мультипликативная погрешность

Аддитивная и мультипликативная погрешность

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

8 ноября 20268 минут
Адиабатический процесс: уравнение Пуассона и расчёт

Адиабатический процесс: уравнение Пуассона и расчёт

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

8 ноября 20268 минут