Класс вычетов

Класс вычетов — это множество всех целых чисел, дающих одинаковый остаток при делении на фиксированное натуральное число (модуль). Понятие является фундаментальным в теории чисел, алгебре и комбинаторике, лежит в основе модульной арифметики и конструкции кольца вычетов.

Определение

Пусть \(m\) — натуральное число, большее единицы. Для любого целого числа \(a\) существует единственное представление \(a = mq + r\), где \(q\) — целое частное, а \(r\) — остаток, удовлетворяющий условию \(0 \le r < m\). Классом вычетов по модулю \(m\), обозначаемым \(\overline{a}\) или \(a \pmod m\), называется множество всех целых чисел, которые при делении на \(m\) дают тот же остаток \(r\), что и \(a\):

\[ \overline{a} = \{ x \in \mathbb{Z} \mid x \equiv a \pmod m \} \]

Здесь запись \(x \equiv a \pmod m\) означает, что разность \(x - a\) делится на \(m\) без остатка.

Свойства

• Количество классов. По модулю \(m\) существует ровно \(m\) различных классов вычетов, соответствующих возможным остаткам от 0 до \(m-1\). Их обычно обозначают \(\overline{0}, \overline{1}, \dots, \overline{m-1}\).
• Эквивалентность. Отношение «иметь одинаковый остаток при делении на \(m\)» является отношением эквивалентности на множестве целых чисел. Классы вычетов — это классы эквивалентности, разбивающие \(\mathbb{Z}\) на \(m\) непересекающихся подмножеств.
• Арифметика. На множестве классов вычетов можно ввести операции сложения и умножения: \(\overline{a} + \overline{b} = \overline{a+b}\), \(\overline{a} \cdot \overline{b} = \overline{ab}\). Эти операции корректны, то есть результат не зависит от выбора представителей классов.

Кольцо вычетов

Множество всех классов вычетов по модулю \(m\) с определёнными выше операциями образует коммутативное кольцо, обозначаемое \(\mathbb{Z}/m\mathbb{Z}\) или \(\mathbb{Z}_m\). Оно называется кольцом вычетов по модулю \(m\).

• Нулевой элемент — класс \(\overline{0}\).
• Единичный элемент — класс \(\overline{1}\).
• Обратимые элементы. Класс \(\overline{a}\) обратим в кольце \(\mathbb{Z}/m\mathbb{Z}\) тогда и только тогда, когда \(\gcd(a, m) = 1\) (наибольший общий делитель равен 1). Множество обратимых классов образует мультипликативную группу, обозначаемую \((\mathbb{Z}/m\mathbb{Z})^\times\).
• Свойства кольца. Кольцо \(\mathbb{Z}/m\mathbb{Z}\) является полем тогда и только тогда, когда \(m\) — простое число. В этом случае оно обозначается \(\mathbb{F}_p\) (поле из \(p\) элементов).

История

Понятие класса вычетов в явном виде ввёл Карл Фридрих Гаусс в 1801 году в своём труде «Арифметические исследования». Гаусс систематически использовал сравнения по модулю и ввёл обозначение \(a \equiv b \pmod m\). Идея классов вычетов стала основой для развития модульной арифметики и теории колец.

Применение

В криптографии

Модульная арифметика и классы вычетов лежат в основе многих криптографических алгоритмов, включая RSA, Диффи-Хеллман и эллиптическую криптографию. Например, в RSA операции шифрования и дешифрования выполняются по модулю произведения двух больших простых чисел.

В вычислительной технике

• Арифметика по модулю используется в процессорах для выполнения операций с целыми числами фиксированной разрядности (например, 32-битные числа — это классы вычетов по модулю \(2^{32}\)).
• Контрольные суммы (CRC, хеш-функции) основаны на вычислении остатка от деления на фиксированный модуль.

В теории чисел

• Малая теорема Ферма: \(a^{p-1} \equiv 1 \pmod p\) для простого \(p\) и \(a\), не кратного \(p\).
• Теорема Эйлера: \(a^{\varphi(m)} \equiv 1 \pmod m\) для взаимно простых \(a\) и \(m\), где \(\varphi\) — функция Эйлера.
• Китайская теорема об остатках: система сравнений по взаимно простым модулям имеет единственное решение по модулю произведения.

В программировании

• Оператор % в языках программирования (C, Python, Java) возвращает остаток от деления, то есть представитель класса вычетов.
• Хеш-таблицы часто используют вычисление остатка для распределения ключей по корзинам.

Примеры

Пример 1: Классы по модулю 3

По модулю 3 существуют три класса:

• \(\overline{0} = \{ \dots, -6, -3, 0, 3, 6, \dots \}\)
• \(\overline{1} = \{ \dots, -5, -2, 1, 4, 7, \dots \}\)
• \(\overline{2} = \{ \dots, -4, -1, 2, 5, 8, \dots \}\)

Сложение: \(\overline{1} + \overline{2} = \overline{3} = \overline{0}\). Умножение: \(\overline{2} \cdot \overline{2} = \overline{4} = \overline{1}\).

Пример 2: Классы по модулю 4

По модулю 4 классы: \(\overline{0}, \overline{1}, \overline{2}, \overline{3}\). Класс \(\overline{2}\) необратим, так как \(\gcd(2,4)=2 \neq 1\). Класс \(\overline{3}\) обратим, так как \(\gcd(3,4)=1\), и \(\overline{3} \cdot \overline{3} = \overline{9} = \overline{1}\).

Интересные факты

• В кольце вычетов по составному модулю могут существовать делители нуля: например, \(\overline{2} \cdot \overline{2} = \overline{0}\) по модулю 4.
• Количество обратимых классов по модулю \(m\) равно значению функции Эйлера \(\varphi(m)\).
• Понятие класса вычетов обобщается до идеалов в кольцах — в алгебраической теории чисел.

Источники

• Гаусс К. Ф. «Арифметические исследования» (1801).
• Виноградов И. М. «Основы теории чисел» (1952).
• Айерлэнд К., Роузен М. «Классическое введение в современную теорию чисел» (1982).
• Кострикин А. И. «Введение в алгебру» (2004).